Mysterious Polynomial

You are given a polynomial P(x) of unknown degree with coefficients which are non-negative integers. You don’t know any of the coefficients, but you are allowed to evaluate the polynomial at any point you choose. What is the smallest number of evaluations you need to use, so that can find the degree and the coefficients of P(x)?

Just 2 evaluations are enough. First, get P(1). This will give you an upper bound on the number of digits of the largest coefficient of the polynomial, let’s say that is N. Now evaluate the polynomial at the point M = 10 to the power of N. This will make all of the coefficients of P appear in the number P(M), separated by strings of zeros.

10 Prisoners, 10 Keys, 2 Weeks

One day, the warden of a prison is, like most wardens in puzzles, feeling a little capricious and decides that he wants to get rid of his prisoners, one way or another. He gathers all the prisoners in the yard and explains to them – “Tonight, I will go to each of you, hand you a key, and tell you who has your key. Each day after that, while the others are out of the cells and no one is watching, I will allow each of you to place your key in someone else’s cell – and each night, you may collect the keys in your own cell. If at any point, you are certain that everyone has the key to their own cell, you may summon me, at which point each of you will open your own cell and walk free. If anyone has the wrong key, everyone will be executed then and there. You may discuss your strategy before tonight, but afterward, no communication will be allowed regarding my game. – Oh, and by the way, if you are still here two weeks from today, I will execute everyone – it’ll be a big birthday for me and I want to retire!”

That night, just as promised, the warden went to each cell and gave each prisoner a key. As he handed each prisoner the key, he whispered to them the name of the person possessing the key to their cell. The keys were entirely indistinguishable from one another, but that was okay, because the prisoners had not counted on being able to tell anything about them. Indeed, the prisoners all seemed confident.

What was their strategy? How could they beat the warden’s game?

We assume the cells in the prison are arranged in a circle. The prisoners agree every day each of them to pass the key they receive to their left neighbor, except for their own key which they keep. It is easy to figure out which key is their own since they can easily calculate when they will receive it. For example, if prisoner 8 knows that his key is at prisoner 3 in the beginning, then he will get it on the 5th day. Therefore, within 10 days, all prisoners will have their own keys.


Puzzling StackExchange

Wizards with Hats

There are 2 wizards and each of them has infinitely many hats on his head. Every hat has 50-50 chance to be white or black, and the wizards can see the hats of the other person, but not their own. Each wizard is asked to identify a black hat on his head without looking, and they win if both succeed to guess correctly. If the wizards are allowed to devise a strategy in advance, can they increase their chance of winning to more than 25%?

Each wizard guesses the position of the lowest black hat on the head of the other wizard. Then the chance of winning becomes 1/4 + 1/16 + 1/64 + … = 1/3. It can be shown that this is an optimal strategy as well.

NASA and the Meteor

NASA locates a meteor in outer space and concludes that it has either a cubical or spherical shape. In order to determine the exact shape, NASA lands a spacecraft on the meteor and lets a rover travel from the spacecraft to the opposite point on the planet. By measuring the relative position of the rover with respect to the spacecraft throughout its travel on the planet (in 3D coordinates), can NASA always determine the shape, no matter the route taken by the rover?

The answer is NO. 

The question is equivalent to analyzing the intersection of a cube and a sphere which share a common center. Thus the question gets reduced to figuring out whether such intersection, which is a curve, can connect two opposite points on the sphere/cube.

Let the edge of the cube has length 1. If you pick the radius of the sphere equal to √2/2, the intersection will consist of 6 circles inscribed in the sides of the cube. Then the rover can just move along these circles from one point to its opposite and NASA won’t be able to figure out the exact shape.

Remark: It is not hard to see that 2:√2 is the only edge-radius ratio, for which NASA can’t figure out the shape.

The Poisoned Glass

You are given 4 identical glasses, completely filled with transparent, odorless liquids. Three of the liquids are pure water, and the fourth is poison, which is slightly heavier. If the water glasses weigh 250 grams each, and the poisoned glass weighs 260 grams, how can you figure out which one is which, using a measuring scale just once?

Empty the first glass, fill around 1/4th of it with liquid from the second glass, and the rest 3/4ths with liquid from the third glass. Then, measure the first and fourth glasses simultaneously. If their total weight is:

– 500 grams -> the first glass is (was) the poisoned one
– between 500 and 505 grams -> the second glass is the poisoned one
– between 505 and 510 grams -> the third glass is the poisoned one
– 510 grams -> the fourth glass is the poisoned one


Puzzling StackExchange

Half Empty, Half Full

You have a glass with perfectly cylindrical shape which has some water in it. How can you figure out if the glass is exactly half full without using any measurement tools (like a ruler)?

Use the geometry of the cylinder. Start tilting the glass until the water surface gets either to the top or the bottom edge. If the glass is exactly half full, then the surface should touch both edges simultaneously.