Delightful Puzzles
1. 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?
2. 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?
3. 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?
4. 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?
5. 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?
6. Cube Cutting — Imagine a 3x3x3 wooden cube. How many cuts do we need to break it into twenty-seven 1x1x1 cubes? A cut may go through multiple wooden pieces.
7. Ant Collisions — Peter and Cynthia stand at each end of a straight line segment. Peter sends 50 ants towards Cynthia, one after another. Cynthia sends 20 ants towards Peter. All ants travel along the straight line segment. Whenever two ants collide, they simply bounce back and start traveling in the opposite direction. How many ants reach Peter and how many reach Cynthia? How many ant collisions take place?
8. Ant in a Room — An ant crawls from one corner of a room to the diametrically opposite corner along the shortest possible path. If the dimensions of the room are 3 x 4 x 5, what distance does the ant cover?
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?

10. 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?
11. 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?
12. 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?
13. 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?
14. 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).
15. 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.
16. 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?
17. 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.
18. Blind Man and Cards — A blind man is handed a deck of 52 cards and told that exactly 10 of these cards are facing up. How can he divide the cards into two piles, not necessarily of equal size, with each pile having the same number of cards facing up?
19. 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.
20. Two Dice = Nine Cards — Alice has two standard dice with labels 1 thru 6. When she rolls them and adds their labels, she gets a distribution over integers in [2, 12]. Bob has nine cards, each labeled with some real number. When Bob chooses two cards (without replacement) and adds their labels, he gets exactly the same distribution over integers in [2, 12] as Alice gets by rolling her dice. What are the labels on Bob's nine cards?
21. 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 must then remove one empty box from the table. Finally, Bob is 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?
22. 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?
23. 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?
24. 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.
25. 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?
26. Divide 100 Marbles into Two Piles — How would you divide 50 black and 50 white marbles into two piles, not necessarily of same size, 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?
27. 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?
28. 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?
29. 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. If Simran makes the first move, could Tavleen ever collect more money than Simran, if Simran makes the optimal choices?
30. Ants in a Circle — Suppose n ants are placed on a circle with a diameter of one meter. Each ant location is chosen independently, uniformly at random. An ant chooses between clockwise or anti-clockwise direction, uniformly at random, and starts scampering along the circle. All ants move at the same speed: one meter per second. When two ants bump into each other, they reverse their direction of travel. One of the ants is named Alice. What is the probability that Alice returns to the same point as she started, one minute after the ants start their scampering?
31. Fifteen Sum — Alice and Bob take turns to pick numbers from 1 thru 9, without replacement. The first to possess three distinct numbers that sum to 15 wins. Does Alice have a winning strategy?
32. 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?
33. 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 a gnome can see exactly those gnomes that are shorter than 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?
34. 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.
35. 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?
36. 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?
37. 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.
38. 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?
39. 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?
40. 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.
41. 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.
42. 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?
43. Perplexing Polynomial — Alice is allowed to choose an arbitrary polynomial p(x) of any degree with nonnegative integer coefficients. Bob can infer the coefficients of p(x) by only two evaluations as follows. He chooses a real number a and Alice communicates p(a) to him. He then chooses a real number b and Alice communicates p(b) to him. What values of a and b helped Bob succeed and how?
44. 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?
45. Two Eggs and a Building — With two eggs and a building with 100 floors, what is the optimal strategy for finding the lowest floor at which an egg will break when dropped? Followup: What if the number of floors of the building is unknown?
46. 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?
47. Cutting a Cake with Icing — One day, grandma baked a cake with a square top and dimensions 30cm x 30cm x 10cm. What is a simple strategy for cutting the cake into 9 equal pieces? The next day, grandma baked another cake with the same dimensions. This time, she put a thin layer of icing on top and on all four sides but not on the bottom. What is a simple strategy for cutting such a cake into 9 pieces such that all pieces have the same amount of cake by volume and the same amount of icing by surface area?
48. 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?
49. 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.
50. 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?
51. Tiling a Chessboard with Dominoes (A) An 8x8 chessboard has had two of its diagonally opposite squares removed, leaving it with sixty-two squares. Can we tile it with 31 non-overlapping 2x1 rectangles (dominoes) such that all squares are covered? (B) Under what circumstances would removal of two squares from an 8x8 chessboard allow such a tiling? For example, if we remove an arbitrary white square and an arbitrary black square, can the remaining board be tiled?
52. 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 2^n consists of (2^n)3 unit cubes. Prove that if one unit cube is removed from T, then the remaining solid can be decomposed into pieces.
53. 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.
54. 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. Bob must execute his privilege before the last card is 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?
55. 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?
56. 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?
57. 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?
58. 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?
59. Find the Angletriangle-puzzle Find the measure of angle "a" in the diagram.
60. 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?
61. 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 do not 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?
62. 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?
63. 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.
64. 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.
65. 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?
66. 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 urn with fewer balls?
67. 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?
68. Rectangle with Integer Side — A big rectangle is composed of smaller non-overlapping rectangles, each having integer width or integer height or both. Prove that the big rectangle enjoys the same property.
69. 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?
70. 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?
71. Firing Squad Synchronization — Consider a finite but arbitrary number of identical finite state machines (soldiers) arranged in a line. At time t = 0, each soldier is initialized to the quiescent (idle) state, except for the soldier on the far left (the general). The state of each soldier at each discrete time-step t > 0 is dependent on its state and the state of its two neighbors at time t - 1 (except for the two soldiers at either end, each of whose state depends only on itself and its sole neighbor). In addition, if a soldier and its neighbors are in the quiescent state, then the soldier will remain quiescent at the next time-step. The problem is to define a finite set of states and state transition rules for the soldiers such that all soldiers enter a distinguished state (fire) at the same time and for the very first time.
72. 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.
73. Tumblers on a Rotating Table — A blind gnome and an evil goblin take turns to play a game. Four tumblers are placed at the corners of a square table. The initial configuration of the tumblers (facing up or facing down) is chosen by the evil goblin. When the blind gnome gets his turn, he is allowed to specify a subset of the four tumblers and flip them simultaneously. To be precise, he may choose "one tumbler", "two diagonally opposites", "two adjacent", "three tumblers" or "four tumblers" lying in front of him, and flip them simultaneously. After flipping, if all four tumblers are upright, he wins the game! Otherwise, the game continues and the evil goblin is allowed to rotate the table by an amount of his choice. Can the blind gnome win the game with a deterministic strategy?
74. 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?
75. 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.
76. 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.
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 Another collection of puzzles. Yet another collection by Tanya Khovanova. Some problems by Mihai Patrascu. Several ingenious puzzles at MathOveflow.Net. Prisoner and Hat Puzzles. Surprises! Surprises! Surprises!. MSRI Archives (puzzles in each newsletter). Nice C Puzzles by Gowri Kumar. Interesting articles on various problems.