All Puzzles

  • N prisoners get together to decide on a strategy.  Then, each prisoner is taken to his own isolated cell.  A prison guard goes to a cell and takes its prisoner to a room where there is a switch.  The switch can either be up or down.  The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch.  The prisoner is then taken back to his cell.  The prison guard repeats this process infinitely often, each time choosing fairly among the prisoners.  That is, the prison guard will choose each prisoner infinitely often.

    At any time, any prisoner can exclaim “Now, every prisoner has been in the room with the switch”.  If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed.  What strategy should the prisoners use to ensure their eventual freedom?

    (Just in case there’s any confusion:  The initial state of the switch is unknown to the prisoners.  The state of the switch is changed only by the prisoners.)

    As a warm-up, you may consider the same problem but with a known initial state of the switch.

    View Solution
    Submit Solution
    • 2611 views
    • 1 answers
    • 0 votes

  • 100 persons are standing in line, each facing the same way.  Each person is wearing a hat, either red or blue, but the hat color is not known to the person wearing the hat.  In fact, a person knows the hat color only of those persons standing ahead of him in line.

    Starting from the back of the line (that is, with the person who can see the hat colors of all of other 99 persons), in order, and ending with the person at the head of the line (that is, with the person who can see the hat color of no one), each person exclaims either “red” or “blue”.  These exclamations can be heard by all.  Once everyone has spoken, a score is calculated, equal to the number of persons whose exclamation accurately describes their own hat color.

    What strategy should the 100 persons use in order to get as high a score as possible, regardless of how the hat colors are assigned?  (That is, what strategy achieves the best worst-case score?)

    For example, if everyone exclaims “red”, the worst-case score is 0.  If the first 99 persons exclaim the color of the hat of the person at the head of the line and the person at the head of the line then exclaims the color he has heard, the worst-case score is 1.  If every other person exclaims the hat color of the person immediate in front and that person then repeats the color he has just heard, then the worst-case score is 50.  Can you do better?

    Hint: Instead of using just red and blue as the possible hat colors and exclamations, use N different colors.

    View Solution
    Submit Solution
    • 33822 views
    • 1 answers
    • 2 votes

  • A team of three people decide on a strategy for playing the following game.  Each player walks into a room.  On the way in, a fair coin is tossed for each player, deciding that player’s hat color, either red or blue.  Each player can see the hat colors of the other two players, but cannot see her own hat color.  After inspecting each other’s hat colors, each player decides on a response, one of: “I have a red hat”, “I had a blue hat”, or “I pass”.  The responses are recorded, but the responses are not shared until every player has recorded her response.  The team wins if at least one player responds with a color and every color response correctly describes the hat color of the player making the response.  In other words, the team loses if either everyone responds with “I pass” or someone responds with a color that is different from her hat color.

    What strategy should one use to maximize the team’s expected chance of winning?

    For example, one possible strategy is to single out one of the three players.  This player will respond “I have a red hat” and the others will respond “I pass”.  The expected chance of winning with this strategy is 50%.  Can you do better?  Provide a better strategy or prove that no better strategy exists.

    View Solution
    Submit Solution
    • 50393 views
    • 5 answers
    • -1 votes



  • You’re given a regular deck of 52 playing cards.  In the pile you’re given, 13 cards face up and the rest face down.  You are to separate the given cards into two piles, such that the number of face-up cards in each pile is the same.  In separating the cards, you’re allowed to flip cards over.  The catch:  you have to do this in a dark room where you cannot determine whether a card is face up or face down.

    View Solution
    Submit Solution
    • 4598 views
    • 1 answers
    • 1 votes

  • Warm-up:  You are given a box of matches and a piece of rope.  The rope burns at the rate of one rope per hour, but it may not burn uniformly.  For example, if you light the rope at one end, it will take exactly 60 minutes before the entire rope has burnt up, but it may be that the first 1/10 of the rope takes 50 minutes to burn and that the remaining 9/10 of the rope takes only 10 minutes to burn.  How can you measure a period of exactly 30 minutes?  You can choose the starting time.  More precisely, given the matches and the rope, you are to say the words “start” and “done” exactly 30 minutes apart.

    The actual problem:  Given a box of matches and two such ropes, not necessarily identical, measure a period of 15 minutes.

    View Solution
    Submit Solution
    • 29437 views
    • 1 answers
    • 0 votes

  • Boris and Natasha live in different cities in a country with a corrupt postal service.  Every box sent by mail is opened by the postal service, the contents stolen, and the box never delivered. Except: if the box is locked, then the postal service won’t bother trying to open it (since there are so many other boxes whose contents are so much easier to steal) and the box is delivered unharmed.

    Boris and Natasha each has a large supply of boxes of different sizes, each capable of being locked by padlocks.  Also, Boris and Natasha each has a large supply of padlocks with matching keys.  The padlocks have unique keys.  Finally, Boris has a ring that he would like to send to Natasha.  How can Boris send the ring to Natasha so that she can wear it (without either of them destroying any locks or boxes)?

    View Solution
    Submit Solution
    • 3696 views
    • 1 answers
    • 0 votes

  • Think of a positive integer, call it X.  Shuffle the decimal digits of X, call the resulting number Y.  Subtract the smaller of X,Y from the larger, call the difference D.  D has the following property:  Any non-zero decimal digit of D can be determined from the remaining digits.  That is, if you ask someone to hide any one of the non-zero digits in the decimal representation of D, then you can try to impress the other person by figuring out the hidden digit from the remaining digits.  How is this done?  Why does it work?

    View Solution
    Submit Solution
    • 3399 views
    • 2 answers
    • 1 votes



  • Two players are playing a game.  The game board is a circular table.  The players have access to an ample supply of equal-sized circular coins.  The players alternate turns, with each turn adding a single coin to the table.  The coins are not allowed to overlap.  Once a coin is placed on the table, it is not allowed to be moved. The player who has no place to put his next coin loses.  Develop a winning strategy for the player who starts.  (The table is large enough to accommodate at least one coin.)

    View Solution
    Submit Solution
    • 5267 views
    • 1 answers
    • 0 votes

  • A rubber band (well, a rubber string, really) is 10 meters long.  There’s a worm that starts at one end and crawls toward the other end, at a speed of 1 meter per hour.  After each hour that passes, the rubber string is stretched so as to become 1 meter longer than it just was.  Will the worm ever reach the other end of the string?

    Also know as – Ant on a rubber rope Puzzle
    An ant starts to crawl along a taut rubber rope 1 km long at a speed of 1 cm per second (relative to the rubber it is crawling on). At the same time, the rope starts to stretch uniformly by 1 km per second, so that after 1 second it is 2 km long, after 2 seconds it is 3 km long, etc. Will the ant ever reach the end of the rope?

    View Solution
    Submit Solution
    • 9395 views
    • 2 answers
    • 0 votes

  • Find two positive integers that together with 23 are the lengths of a right triangle.

    Hint: There’s a simple technique that, given any odd positive integer, allows you to figure out the other two integer sides of a right triangle in your head (or with pen and paper if the numbers get too large).  Find this technique.

    View Solution
    Submit Solution
    • 3010 views
    • 1 answers
    • 1 votes