Blind Man and Cards: A blind man was handed a deck of 52 cards with exactly 10 cards facing up. How could he divide it into two piles, each of which having the same number of cards facing up?

Rope: 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?

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?

Choice of Three: In the previous problem, Bob had to pick one of the three boxes lying on the table. If he wished to select them with equal probability, how could he do it by using a penny in his pocket? What if the penny was biased?

Treasure Island: An old parchment contains directions to a treasure chest buried in an island: "There is an old 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?

30 Coins: 30 coins of arbitrary denominations are laid out in a row. Ram and Maya alternately pick one of the two coins at the ends of the row. Could Maya ever collect more money than Ram?

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?

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?

Tiling a Chessboard: An 8x8 chessboard has had two of its diagonally opposite squares removed, leaving it with sixty-two squares. Is it possible to tile it with non-overlapping 2x1 rectangles such that all squares are covered?

Cubes in Cube: Imagine a 3x3x3 solid cube. How many cuts do we need to break it into twenty-seven 1x1x1 cubes? How about an n x n x n cube? What if we are not allowed to stack pieces and cut them together?
Is there a way to repeatedly hop from a small cube to an adjacent small cube (sharing a surface) within the large 3x3x3 cube such that there is a closed path covering all small cubes, without ever passing through a small cube twice?

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. And yeah, the wires burn non-uniformly.

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?

Thousand Jars: Imagine an array of one thousand jars, labeled one thru thousand. Jars can be colored red or black. Initially, all jars are red. The color of a jar changes on successive days as follows: On the i-th day, jars whose labels are divisible exactly by i, switch their color. How many jars are red at the end of the thousandth day?

Working Computer: A room has n computers, less than half of which are damaged. 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 an undamaged computer in as few queries as possible.

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?

Number Guessing Game I: Shankar chooses a number 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. (a) What should Geeta's strategy be? (B) In a modified version of the game, Geeta loses if her guess is "larger than the number" two or more times. (c) What if Shankar is allowed to choose an arbitrarily large number?

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]. (a) What should Geeta's strategy be? (b) In a modified version of the game, Shankar gets to choose a number arbitrarily / adversarially. (c) And finally, what if Shankar just says "equal to" or "not equal to" when Geeta guesses (the rest of the setup remains the same)?

Four Ships: Four ships are sailing on a 2D planet. Each ships traverses a straight line at constant speed. 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 and two ships are out of commission. What fate awaits the remaining two?

f(f(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? Is it possible to construct a function f mapping rationals to rationals such that f(f(x)) = 1/x?

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?

Counting with a Magical Bird: An evil goblin assembles 100 gnomes together. He tells them that they will be locked up into individual cells. Each cell will have a window and a large supply of grains. Thereafter, a magical bird will hop from window to window, ad infinitum. Initially, the bird is white in color, and it will switch its color from white to black and vice versa if a grain is fed to it. The bird will be fair in the sense that it will visit every cell infinitely often. As soon as some gnome is sure that the bird has visited every cell, he should say "abracadabra" aloud. If the bird has indeed visited every cell, all gnomes will be released. Otherwise, all of them will be killed. The gnomes have ten minutes to arrive at a strategy. How can they save themselves?

Troll n Gnomes: 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? What if hats come in 10 different colors?

Red-black Squares: 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.

Four Cards: Four cards are placed on a square table, one card at each corner. A blind gnome and an evil goblin take turns to play the following game. The blind gnome gets to choose a subset of the four cards and flip them simultaneously. If all four cards are face up, he wins the game. Otherwise, the evil goblin get to rotate the table by an amount of his choice. Show that for any initial configuration of cards chosen by the evil goblin, the blind gnome can win the game in a finite number of steps with a deterministic strategy.

And-Or Gates: Alice and Bob were working in the hardware design lab one morning giving final touches to their 4-bit microprocessor, when suddenly they discovered that three of their NOT gates were malfunctioning! They opened the inventory cupboard and received another shock: only two NOT gates were available.
"Look. All we have is hundreds of AND and OR gates but just two NOT's! Damn! Just six hours before the deadline. We're out of luck. Any ideas?", asked Alice.
"Well, we obviously cannot hope to get three NOTs out of two NOTs", replied Bob.
"I guess you're right ...", said Alice with a frown on her face and her shoulders dropping. Then suddenly she jumped and said, "No, wait! It can be done! Here it it!" And pulling out a pen from her pocket, she sketched a circuit of a piece of paper.
"Wow! You're a genius, Alice!", cried Bob.
Are you as smart as Alice? In general, how many signals can we invert using n NOT gates and any number of AND and OR gates? No other gates may be used.

Dijkstra's Problem: 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) is not equal to 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.

Tiling Problem: A big rectangle is composed of smaller rectangles, each having an integral width or integral height or both. Does the big rectangle enjoy the same property?

Marked Squares: Consider an n by n grid of squares. A square is said to be a neighbour of another one if it lies directly above/below or to its right/left. Thus, each square has at most four neighbours. Initially, some squares are marked. At successive clock ticks, an unmarked square marks itself if at least two of its neighbours are marked. What is the minimum number of squares we need to mark initially so that all squares eventually get marked?

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, in no particular order. 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. What do you do?

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?

Geometry without a Ruler: 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?

Chessboard with Signs: An 8x8 chessboard has either a plus or a minus written in each of its sixty-four squares. You are allowed to repeatedly choose a 3x3 or a 4x4 block of squares and invert all signs within it. How would you go about getting rid of all the minuses?

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?