Puzzles: Set 2
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 9
Coin Toss Guess

Alice and Bob are playing a game. They are teammates, so they will win or lose together. Before the game starts, they can talk to each other and agree on a strategy.

When the game starts, Alice and Bob go into separate soundproof rooms — they cannot communicate with each other in any way. They each flip a coin and note whether it came up Heads or Tails. (No funny business allowed — it has to be an honest coin flip and they have to tell the truth later about how it came out.) Now Alice writes down a guess as to the result of Bob’s coin flip; and Bob likewise writes down a guess as to Alice’s flip.

If either or both of the written-down guesses turns out to be correct, then Alice and Bob both win as a team. But if both written-down guesses are wrong, then they both lose.

Can you think of a strategy Alice and Bob can use that is guaranteed to win every time?

Solution
Cube Problems

Imagine a cube on a flat table, tantalizingly balanced on one of its vertices such that the vertex most distant from it is vertically above it.

(a) What is the length of the shortest path an ant could take to go from the topmost vertex to the bottommost vertex?

(b) What will be the projection on the table if there is a light source right above the cube?

(c) What would be the cross-section obtained if we slice the cube along a plane parallel to the table, passing through the midpoint of the topmost and the bottommost points of the cube?

(d) Split a large 3×3×3 cube into 27 small 1×1×1 cubes. An ant can burrow through one small cube to an adjacent small cube if these two cubes share a face. Can the ant burrow through all of the 27 small cubes, visiting each small cube exactly once? Can such a sequence have the additional property that the first and the last small cube share a face?

Solution
Truchet Tilings

An 8x8 square grid has to be covered with isosceles triangular tiles with two tiles per square. Tiles come in two colors: black and white. Such tilings are called Truchet tilings. A tiling is said to be "fine" if no two tiles sharing an edge have the same color. How many "fine" Truchet tilings are there?
Solution
Treasure Island

An old parchment has directions to a treasure chest buried in an island:
“There is an unmarked grave and two tall oak trees. Walk from the grave to the left tree, counting the number of steps. Upon reaching the left tree, turn left by 90 degrees and walk the same number of steps. Mark the point with a flag. Return to the grave. Now, walk towards the right tree, counting the number of steps. Upon reaching the right tree, turn right by 90 degrees and walk the same number of steps. Mark this point with another flag. The treasure lies at the midpoint of the two flags.”
A party of sailors reached the island. They find a pair of tall oak trees merrily swaying in the wind. However, the unmarked grave is nowhere to be found. They are planning to dig up the entire island. It'll take a month. Can they do any better?
Solution
Magician & Balls

A magician has a bag with B black balls and W white balls. He also has a large supply of white balls and black balls outside the bag.

At every step, the magician removes two balls from the bag chosen uniformly at random and tosses them away. If the colors of these two balls were identical, he puts one white ball in the bag, otherwise he puts a black ball in the bag.

Given B and W, what are the chances that the last ball left in the bag is white?

Solution
Six Colored Balls

We have two white, two red and two blue balls. For each color, one ball is heavy and the other is light. All heavy balls weigh the same. All light balls weigh the same. How many weighings on a beam balance are necessary to identify the three heavy balls?
Solution
Josephus Problem

There are n persons in a circle, numbered 1 thru n. Going around the circle, every second person is removed from the circle, starting with person number 2, 4, and so on. Show that the number of the last person remaining in the circle can be obtained by writing n in binary, then moving the leftmost 1 to the right. So for example, with n = 13 persons (1101 in binary), the last person is number 11 (1011 in binary).
Solution
Forty-Five Minutes

How do we measure forty-five minutes using two identical wires, each of which takes an hour to burn. We have matchsticks with us. The wires burn non-uniformly. So, for example, the two halves of a wire might burn in 10 minute and 50 minutes respectively.
Solution
Thousand Prisoners

A prison has 1000 cells. Initially, all cells are marked with - signs. From days 1 thru 1000, the jailor toggles marks on some of the cells: from + to - and from - to +. On the i-th day, the signs on cells that are multiples of i get toggled. On the 1001-th day, all cells marked with + signs are opened. Which cells are these?
Solution
Non-Transitive Dice

You and your opponent shall play a game with three dice: First, your opponent chooses one of the three dice. Next, you choose one of the remaining two dice. The player who throws the higher number with their chosen dice wins. Now, each dice has three distinct numbers between 1 and 9, with pairs of opposite faces being identical. Design the three dice such that you always win! In other words, no matter which dice your opponent chooses, one of the two remaining dice throws a number larger than your opponent, on average.
Solution
© Copyright 2008—2023, Gurmeet Manku.