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

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

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

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

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

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

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? Solution

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? Solution

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

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

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

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

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

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

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

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

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? Solution

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

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? Solution

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? Solution

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

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? Solution

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

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

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? Solution

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

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

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? Solution

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? Solution

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? Solution

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

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? Solution

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

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

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

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

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

(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? Solution

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

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

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

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? Solution

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

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? Solution

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

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? Solution

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

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

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

(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? Solution

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)³ unit cubes. Prove that if one unit cube is removed from T, then the remaining solid can be decomposed into pieces. Solution

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

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? Solution

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

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? Solution

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

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

Find the measure of angle "a" in the diagram. Solution

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

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? Solution

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

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

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

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

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? Solution

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

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

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

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

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

Find all configurations of 4 points in a plane with only 2 distinct values for distances between pairs of points. Solution

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? Solution

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? Solution

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

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