Delightful Puzzles

Puzzles that would appeal to computer scientists and mathematicians.

Easy Puzzles

---

E1. Blind Man and Cards: A blind man is handed a deck of 52 cards with exactly 10 cards facing up. How can he divide it into two piles, not necessarily of equal size, with each pile having the same number of cards facing up? Solution

E2. Tossing with One-Third Probability: At a restaurant, how can Veronica choose one out of three desserts with equal probability with the help of a coin? What if the coin is biased and the bias is unknown? Solution

E3. Ant in a Room: An ant has to crawl from one corner of a room to the diametrically opposite corner as quickly as possible. If the dimensions of the room are 3 x 4 x 5, what distance does the ant cover? Solution

E4. Breaking a Chocolate: How many steps are required to break an m x n bar of chocolate into 1 x 1 pieces? We may break an existing piece of chocolate horizontally or vertically. Stacking of two or more pieces is not allowed. Solution

E5. Divide 100 Marbles into Two Piles: How would you divide 50 black and 50 white marbles into two piles so that the probability of picking a white marble as follows is maximized: we first pick one of the piles uniformly at random, then we pick a marble in that pile uniformly at random? Solution

E6. Coins in a Row: 30 coins of arbitrary denominations are laid out in a row. Simran and Tavleen alternately pick one of the two coins at the ends of the row so as to pick up as much money as possible. Could Tavleen ever collect more money than Simran? Solution

E7. Rope Escape: Rajeev is trapped atop a building 200m high. He has with him a rope 150m long. There is a hook at the top where he stands. Looking down, he notices that midway between him and the ground, at a height of 100m, there is a ledge with another hook. In his pocket lies a Swiss knife. Hmm… how might he be able to come down using the rope, the two hooks and the Swiss knife? Solution

E8. Three Boxes and a Ruby: Alice places three identical boxes on a table. She has concealed a precious ruby in one of them. The other two boxes are empty. Bob is allowed to pick one of the boxes. Among the two boxes remaining on the table, at least one is empty. Alice then removes one empty box from the table. Bob is now allowed to open either the box he picked, or the box lying on the table. If he opens the box with the ruby, he gets a kiss from Alice (which he values more than the ruby, of course). What should Bob do? Solution

E9. 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

E10. 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

E11. Six Colored Balls: We have two red, two green and two yellow 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

E12. Three Heavy and Three Light Balls: Three out of six lookalike balls are heavy. The other three are light. How many weighings on a beam balance are necessary to identify the heavy balls? Solution

E13. Kirkman’s Schoolgirl Problem: Nine schoolgirls are to be arranged in three rows and three columns on four different days so that any pair of schoolgirls is in the same row on exactly one of the four days. Solution

E14. Cube Cutting: Imagine a 3×3x3 wooden cube. How many cuts do we need to break it into twenty-seven 1×1x1 cubes? A cut may go through multiple wooden pieces. Solution

E15. 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 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 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

E16. Cake Cutting: Mary baked a rectangular cake. Merlin secretly carved out a small rectangular piece, ate it and vanished! The remaining cake has to be split evenly between Mary’s two kids. How could this be done with only one cut through the cake? Solution

E17. 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) Is there a way to repeatedly hop from a small cube to an adjacent small cube (sharing a surface) within the large 3×3x3 cube such that there is a closed path covering all small cubes, without ever passing through a small cube twice? Solution

E18. Three Boxes with Two Balls Each: The first box has two white balls. The second box has two black balls. The third box has one white and one black ball. Boxes are labeled but all labels are wrong! You are allowed to open one box, pick one of its balls at random, see its color and put it back into the box (you do not get to know the color of the other ball). How many such operations are necessary to correctly label the boxes? Solution

E19. 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

E20. Chameleons: On an island live 13 purple, 15 yellow and 17 maroon chameleons. When two chameleons of different colors meet, they both change into the third color. Is there a sequence of pairwise meetings after which all chameleons have the same color? Solution

E21. Pebble Piles: You are given three piles with 5, 49 and 51 pebbles respectively. Two operations are allowed: (a) merge two piles together or (b) divide a pile with an even number of pebbles into two equal piles. Is there a sequence of operations that would result in 105 piles with one pebble each? Solution

E22. Truchet Tilings: An 8×8 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

E23. Absent-Minded Professor: N women stand in a queue to take seats in an auditorium. Seating is pre-assigned. However, the first woman is an absent-minded professor who chooses any of the N seats at random. Subsequent women in the queue behave as follows: if the seat assigned to her is available, she takes it. Otherwise, she chooses an unoccupied seat at random. What are the chances that the last woman in the queue shall get the seat assigned to her? Solution

E24. 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

E25. Fox in a Hole: Consider five holes in a line. One of them is occupied by a fox. Each night, the fox moves to a neighboring hole, either to the left or to the right. Each morning, you get to inspect a hole of your choice. What strategy would ensure that the fox is eventually caught? Solution

E26. What’s the Color of My Probabilistic Hat?: Three wizards are seated at a circular room. A magician shall make hats appear on their heads, one hat per wizard. Hats are either black or white, chosen uniformly at random. A wizard cannot see his own hat. At the sound of a bell, all wizards react simultaneously. A wizard reacts by either announcing a color or keeping quiet. If at least one wizard makes an announcement and if all the announcements are correct, the wizards have collectively won the game! Wizards are allowed to confer beforehand to devise a strategy. On average, can they win more than half the times the game is played?

Moderate Puzzles

---

M1. Tiling a Chessboard with Dominoes: (A) An 8×8 chessboard has had two of its diagonally opposite squares removed, leaving it with sixty-two squares. Can we tile it with 31 non-overlapping 2×1 rectangles (dominoes) such that all squares are covered? (B) Under what circumstances would removal of two squares from an 8×8 chessboard allow such a tiling? For example, if we remove an arbitrary white square and an arbitrary black squre, can the remaining board be tiled? Solution

M2. Loop in a Linked List: Given the head of a linked list, find if it contains a loop or not, in linear time. Can you accomplish it with only O(1) extra space? Can you do it without modifying the list in any way? Solution

M3. Four Points, Two Distinct Distances: Find all configurations of 4 points in a plane with only 2 distinct values for distances between pairs of points. Solution

M4. Card Shuffling: A perfect in-shuffle of a deck of 52 cards is defined as follows. The deck is cut in half followed by interleaving of the two piles. So if the cards were labeled 0, 1, 2, …, 51, the new sequence is 0, 26, 1, 27, 2, 28, … With repeated in-shuffles, shall we ever get back the original order? In how many iterations? Solution

M5. Tiling A Chessboard with Trominoes: Show that a chessboard of size 2^n by 2^n can be tiled with L-shaped figures of 3 squares, such that only one square remains uncovered. In fact, the uncovered square may be any square — for every choice, there exists a tiling. In fact, the puzzle may be extended to 3D: Eight unit cubes make a cube with edge length two. We will call such a cube with one unit cube removed a “piece”. A cube with edge length 2n consists of (2n)³ unit cubes. Prove that if one unit cube is removed from T, then the remaining solid can be decomposed into pieces. Solution

M6. Cap Colors: An evil troll once captured a bunch of gnomes and told them, “Tomorrow, I will make you stand in a file, ordered by height such that the tallest gnome can see everybody in front of him. I will place either a white cap or a black cap on each head. Then, starting from the tallest, each gnome has to declare aloud what he thinks the color of his own cap is. In the end, those who were correct will be spared; others will be eaten, silently.” The gnomes set thinking and came up with a strategy. How many of them survived? Solution

M7. Working Computer: A room has n computers, less than half of which are damaged, others are good. It is possible to query a computer about the status of any computer. A damaged computer could give wrong answers. The goal is to discover a good computer in as few queries as possible. Solution

M8. Duplicate Integer: An array of length n+1 is populated with integers in the range [1, n]. Find a duplicate integer (just one, not all) in linear time with O(1) space. The array is read-only and may not be modified. Variation: what if the array may be written into but must be left unmodified by the algorithm? Solution

M9. Poisoned Wine Barrels: An enemy spy has poisoned one out of 1000 barrels of wine in a king’s cellar. Even a sip of the poisoned wine has potency to kill. However, the effects of the poison show only in 30 days. The king asks the royal jailor to identify the poisoned barrel within 30 days. What is the least number of prisoners the jailor must employ to identify the poisoned barrel? Solution

M10. Four Ships: Four ships are sailing on a 2D planet. Each ships traverses a straight line at constant speed. No two ships are traveling parallel to each other. Their journeys started at some time in the distant past. Sometimes, a pair of ships collides. A ship continues its journey even after a collision. However, it is strong enough only to survive two collisions; it dies when it collides a third time. The situation is grim. Five of six possible collisions have already taken place (no collision involved more than 2 ships) and two ships are out of commission. What fate awaits the remaining two? Solution

M11. Cube Cutting with Stacking: How many cuts are necessary to cut an n x n x n cube into 1 x 1 x 1 cubes? Existing cuboids may be stacked together for cutting. So one cut may go through multiple existing cuboids. Solution

M12. Average Salary: Four honest and hard-working computer engineers are sipping coffee at Starbucks. They wish to compute their average salary. However, nobody is willing to reveal an iota of information about his/her own salary to anybody else. How do they do it? Solution

M13. Bigger or Smaller: Alice writes two distinct real numbers between 0 and 1 on two chits of paper. Bob selects one of the chits randomly to inspect it. He then has to declare whether the number he sees is the bigger or smaller of the two. Is there any way he can expect to be correct more than half the times Alice plays this game with him? Solution

M14. Number Guessing Game: Shankar chooses a number between 1 and 10,000. Geeta has to guess the chosen number as quickly as possible. Shankar will let Geeta know whether her guess is smaller than, larger than or equal to the number. The caveat is that Geeta loses the game if her guess is larger than Shankar’s chosen number two or more times. (A) How many guesses are necessary? (B) What if Shankar is allowed to pick an arbitrarily large positive number? Solution

M15. Number Guessing Game II: Shankar chooses a number uniformly at random between 1 and 1000. Geeta has to guess the chosen number as quickly as possible. Shankar will let Geeta know whether her guess is smaller than, larger than or equal to the number. If Geeta’s guess is larger than the number, Shankar replaces the number with another number chosen uniformly at random [1, 1000]. What should Geeta’s strategy be? Solution

M16. f(f(x)) = -x: Is it possible to write a function int f(int x) in C that satisfies f(f(x)) == -x? Without globals and static variables, of course. Solution

M17. Measuring Weights: (a) Customers at a grocer’s shop always want an integral number pounds of wheat, between 1 pound and 40 pounds. The grocer prefers to measure wheat in exactly one weighing with a beam balance. What is the least number of weights he needs? (b) Customers come to a pawn shop with antiques. An antique always weighs an integral number of pounds, somewhere between 1 pound and 80 pounds. The owner of the pawn shop is free to do as many weighings as necessary to ascertain the unknown integral weight by using a beam balance. What is the least number of weights he needs?

M18. 100 Prisoners and a Light Bulb: There are 100 prisoners in solitary cells. There’s a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion? Solution (PDF) by Willam Wu. Extension by Ulf Göransson.

M19. Two Eggs and a Building: You have to discover the smallest floor of the building from which an egg, when dropped, breaks. With two eggs at your disposal, how many times do you have to drop the egg from various floors? What if the number of floors of the building is unknown?

M20. Fuel Dumps on a Circular Racetrack: A set of fuel dumps on a circular racetrack have just enough gasoline for one car to make one round trip. Prove that there exists a fuel dump from which one car, starting with an empty gas tank, can complete the round trip. Solution

M21. Tiling With Calissons: A large regular hexagon is cut out of a triangular grid and tiled with diamonds (pairs of triangles glued together along an edge). Diamonds come in three varieties, depending on orientation; prove that precisely the same number of each variety must appear in the tiling. Solution

M22. Forks in a Road: A traveler has to pass tests of increasing difficulty to meet an Eastern mystical master. For the first test, he meets a pair of twins at a fork in the road: one path leads to the jungle, the other to the mystic. One of the twins always says the truth, the other always lies. What yes/no question should you ask one of the twins to determine the path that goes to the mystic? For the second test, the traveler encounters a second fork in the road. Again, one path leads to the jungle, the other to the mystic. This time, there are three look-alike brothers: one always tells the truth, the second always lies but the third sometimes tells the truth and sometimes lies. What two Yes/No questions should the traveler ask two of the brothers to determine the path to the mystic? Each question is answered by only the brother it is posed to. For the second question, the traveler may choose the brother and the question depending upon the answer to the first question. Solution

M23. What’s the Number on My Hat?: A goblin forewarns N gnomes as follows: “Tomorrow morning, I shall place one hat on each of you. Each hat shall be labeled with some number drawn from the range [0, N-1]. Duplicates are allowed, so two different hats might have the same label. Any gnome shall be able to see numbers on other hats but not his own! When a bell rings, all gnomes shall simultaneously announce one number each. If any gnome succeeds in announcing the number on his own hat, all gnomes shall be set free.” The gnomes have assembled in the evening to discuss their predicament. Can you help them devise a strategy? Solution

Difficult Puzzles

---

D1. Flipping Bits in a Matrix: An 8×8 matrix contains zeros and ones. You may repeatedly choose any 3×3 or 4×4 block and flip all bits in the block (that is, convert zeros to ones, and ones to zeros). Can you remove all the ones in the matrix? Solution

D2. 100 Prisoners and 100 Boxes: A room has 100 boxes labeled 1 thru 100. The names of 100 prisoners have been placed in these boxes by the warden. The prisoners shall visit the room one by one. Each prisoner is allowed to inspect the contents of at most 50 boxes, one after the other and leave the room with no communication with other prisoners. If the prisoner discovers his own name in the boxes he inspects, he is released. The prisoners are allowed to collude before hand and devise a strategy to maximize the chances of releasing each and every prisoner. What is their strategy? Solution

D3. Polya’s Urn Process: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Solution

D4. Balanced Coloring: Given k arbitrary points in a grid of size m by n, is it always possible to color them either red or black such that each row and each column is balanced? A row or column is said to be balanced if the difference in the number of red and black points in it is at most one. Solution

D5. Tumblers on a Rotating Table: Four tumblers are placed at the corners of a square table. A blind gnome and an evil goblin take turns to play a game. The blind gnome gets to choose a subset of the four tumblers and flip them simultaneously. Effectively, he may choose “one tumbler”, “two diagonally opposites”, “two adjacent”, “three tumblers” or “four tumblers” lying in front of him. After flipping, if all four tumblers are upright, he wins the game! Otherwise, the game continues: the evil goblin rotates the table by an amount of his choice. Can the blind gnome win the game with a deterministic strategy? Solution

D6. Three NOT Gates from Two NOT Gates: Design a 3-input 3-output logic circuit that negates the 3 signals. You have an infinite supply of AND and OR gates but only two NOT gates. Solution

D7. Dijkstra’s Self-Stabilization Protocol: There are n+1 processors named 0, 1, …, n. Processor i has a counter C(i) that takes values in the range [0, n]. Its initial value is arbitrarily chosen from [0, n]. Processor 0 is said to be privileged if C(0) = C(n). Processor i, where i > 0, is said to be privileged if C(i) ≠ C(i-1). At successive clock ticks, exactly one out of possibly several privileged processors is arbitrarily chosen and its counter is updated as follows: If processor 0 is chosen, we set C(0) ← (C(0) + 1) mod (n+1). Otherwise, we set C(i) ← C(i-1). Prove that after a bounded number of clock ticks, exactly one processor will be privileged. And that this will continue to hold forever. Solution

D8. Rectangle with Integral Side: A big rectangle is composed of smaller rectangles, each having an integral width or integral height or both. Prove that the big rectangle enjoys the same property. Solution by David McKay. A solution by E W Dijkstra. Another Solution by Ulrich Berger. Another Solution at cut-the-knot.

D9. Grid Infection: In an n by n grid of squares, two squares are neighbors if they share an edge. Initially, some squares are “infected”. At successive clock ticks, an uninfected square gets infected if at least two of its neighbors are infected. How many squares must initially be infected so that all squares eventually get infected? Solution

D10. Horses on Auction: You are the chief guest at an auction, where an unknown number of horses will be revealed and auctioned, one after the other, randomly permuted. You are a connoiseur of horses, and can judge whether one horse is ‘better’ than another. Being the chief guest, you have a one-time privilege of selecting a horse, after it is revealed, but before it gets auctioned off. You get to keep this horse for yourself. Your objective is to maximize the probability of selecting the best horse. One strategy is to pick the first horse. Can you do any better? Solution

D11. Red Card: Alice repeatedly draws a card randomly, without replacement, from a pack of fifty-two cards. Bob has a one-time privilege to raise his hand just before a card is about to be drawn. If the card drawn is Red just after Bob raises his hand, Bob wins; otherwise he loses. Is there any way for Bob to be correct more than half the times he plays this game with Alice?

D12. My Cap Color: At the Secret Convention of Logicians, the Master Logician placed a band on each attendee’s head, such that everyone else could see it but the person themselves could not. There were many, many different colours of band. The Logicians all sat in a circle, and the Master instructed them that a bell was to be rung in the forest at regular intervals: at the moment when a Logician knew the colour on his own forehead, he was to leave at the next bell. Anyone who left at the wrong bell was clearly not a true Logician but an evil infiltrator and would be thrown out of the Convention post haste; but the Master reassures the group by stating that the puzzle would not be impossible for anybody present. How did they do it? Solution

D13. Geometry With Only a Compass: Using only a compass (and without a straight edge or a ruler), is it possible to identify (a) the midpoint of two points? (b) the center of a circle? (c) all four corners of a square, given two of them? Solutions to several such constructions.

D14. Sum and Product: P is told the product of two integers chosen from [2, 99] and S is told the sum. The following dialogue ensues: (1) P says, “I don’t know the two integers.” (2) S replies, “I knew that already.” (3) P exclaims, “Ah! I now know the two numbers.”, (4) S smugly replies, “Now I know them too.” What are the two numbers? Solution by E W Dijkstra and myriad variations of this puzzle.

D15. Five Card Trick: A mathemagician asks a volunteer to give him five cards drawn from a pack of fifty-two. He hands one card back to the volunteer and arranges the remaining four in some sequence he chooses. He then hands the sequence to a second volunteer and leaves the room. His assistant enters. The assistant asks the second volunteer to read out aloud the sequence handed to him. The assistant ponders a little and correctly announces the identity of the card held by the first volunteer. How could this be done? In general, how large a deck of cards can be handled if n cards are drawn initially? Solution may be found in the article: Five Card Trick by Colm Mulcahy in MAA Horizons, 10 February 2003.

D16. Twelve Coins: One of twelve coins is counterfeit: it is either heavier or lighter than the rest. Is it possible to identify the counterfeit coin in three weighings on a beam balance? A solution by Brian Bundy. The solution by Jack Wert is especially pleasing.

D17. Find the Angle: Find the measure of angle “a” in the diagram (click to enlarge). Solution by Tom Rike (Berkeley Math Circle Handouts)

D18. Fast Bit Counting: Devise a fast algorithm for computing the number of 1-bits in an unsigned integer. If the machine supports n-bit integers, can we compute the number of 1-bits in O(log n) machine instructions? Can we compute the number of 1-bits in O(b) machine instructions where b is the number of 1-bits in the integer? Solution

D19. Empty the Bucket: Three buckets have marbles. You are allowed to double the number of marbles in a bucket by borrowing from one of the other two buckets. Prove that it is possible to produce an empty bucket with a series of such operations. Solution

---

Links to Puzzle Sites

The Puzzle Toad at CMU has challenging puzzles. William Wu’s Puzzles Page at Berkeley has myriad puzzles with a discussion board. Cut the Knot has dozens of high quality articles on mathematics, puzzles and games. Puzzles by Erich Friedman has cute puzzles; he also maintains Math Magic, Erich’s Packing Center and Ambigrams. Archives of Ed Pegg Jr’s Math Games in MAA make interesting reading. Age of Puzzles is a nicely done website with classic puzzles, diagrams and references. Sam Lloyd website: A few of his puzzles have tastefully been compiled at this website. SOMA cube has dozens of SOMA cube configurations. List of books by Martin Gardner. Select puzzles for high school students: SNAP Math Fair. Another small collection. A nice collection of problems at mathproblems.info. Another collection of puzzles. Yet another collection by Tanya Khovanova.