1. Introduction
Quantitative brainteasers are more than just fascinating. They are part of the natural pastime in engineering and science. The exact solution to a few may require greater computing power, but a satisfactory response without computer aid is provided in this paper. Two excellent references for material leading to these problems can be found in [1] or [2] .
2. Strategy
2.1. Heads Up
You are blind-folded before a table with n identical heads-tails coins spread about and non-overlapping. You are told that exactly 
of these coins are showing heads. How can you create two piles of coins with an equal number of heads showing?
Solution: You must take m coins and turn them over into a new pile. The resulting pile will have the same number of heads showing as the remaining pile. For each coin that is flipped into the new pile, either the number of heads in the original pile decreases by one or the number of heads in the new pile increases by one, in either case reducing the difference in number of heads shown by one. After m such flips, the difference in number of heads between the two piles is zero. Of course, we do not know how many heads are showing.
2.2. Bridge Crossing
Four people must cross a rickety bridge in the dark with one flashlight. The bridge can only support two people at a time and any person or pair crossing the bridge must carry the flashlight. The four individuals can cross the bridge in 1 minute, 2 minutes, 5 minutes, and 10 minutes, respectively. When two people cross the bridge, the faster person must walk at the slower person’s pace. What strategy will have the four people cross the bridge safely in the shortest time?
Solution: The trick is that the 5-minuter and 10-minuter must cross the bridge once and together. To accomplish this, the 1-minuter and 2-minuter first cross. The 2-minuter remains on the other side and the 1- minuter returns with the flashlight. The 5-minuter and 10-minuter then cross the bridge with the flashlight and hand it to the 2-minuter, who returns across the bridge to guide the 1-minuter across with the flashlight. The total time required for this strategy is an optimal 17 minutes.
2.3. Coin Game
A two-player turn-based game is played on a round table. On a player’s turn, he draws a coin from an infinite supply of identical coins and places this coin somewhere on the table without moving or overlapping with any existing coins and such that no part of the coin hangs over the edge of the table. The next player does the same. The players take turns until no player can fit a coin on the table. The last player to have placed a coin on the table wins. You may choose to play the first move or defer it to your opponent. Which should you do and what is the winning strategy?
Solution: You should choose to move first and place your first coin directly in the middle of the table. From then on, you will mirror your opponent’s move by 180 degrees. In doing so, you guarantee that for any play your opponent makes, there is an available space for you to play as well.
2.4. Pushing Pawns
On a standard eight-by-eight chess board, one player has eight pawns lined up on the first rank facing his opponent who has his pawns lined up the opposite rank. During a turn, a player must advance one of his pawns forward either one space or two spaces. The game is over when the pawns in all the files can no longer move forward because they are blocked by opposing pawns. The winner is the last to have moved. In this game, which player has the advantage: First to move or second to move? What is his optimal strategy?
Solution: The second player to move has the advantage and can guarantee victory. First, consider the case of a single file. Initially, there are six squares between the pawns. After the first player moves, there are either five or four squares remaining between the pawns. The second player should advance his pawn either two squares or one square so that three squares remain between the pawns. Regardless of the first player’s next move, the second player can be certain that he has the final move. This strategy can be applied across an arbitrary number of files, the second player always responding to the first player’s move in the same file.
2.5. Unbeknownst to the Department of Corrections
A twisted prison warden offers his one-hundred prisoners a chance at freedom. He intends to arrange them in a single-file line where each prisoner faces the back of the next prisoner. Once aligned, each prisoner will randomly and with equal probability be given a red or blue hat to wear. The warden will start at the backmost prisoner and ask him to identify the color of his hat. If the prisoner responds correctly, the warden will proceed to the next prisoner in line and ask him the same question. If at any point any prisoner responds incorrectly, all prisoners return to jail. If every prisoner responds correctly, all prisoners will be released back into poor unsuspecting society. Any prisoner in line can see the hat color of any prisoner in front of him and can hear the response of any prisoner behind him. He cannot, however, see the color of his own hat or communicate information to any prisoner in any manner other than in his binary response to the warden?s question. The prisoners may discuss their strategy beforehand. What strategy maximizes the probability that the prisoners go free?
Solution: The optimal strategy succeeds with probability one-half. The backmost prisoner counts the number of red hats and responds to the warden, Red, if this number is even, and Blue, if this number is odd. This provides enough information for the next prisoner to identify his hat color. Any subsequent prisoner, in turn, combines the first prisoners information with the responses of prisoners behind him to determine his own hat color with certainty. The only uncertainty, of course, is whether the first prisoner’s code for the parity of the hats in fact matches the color of his own. Further, no method can succeed with greater odds, since the first prisoner cannot possibly have any insight into the color of his own hat; under any strategy, the first prisoners response is correct with probability one-half.
2.6. Quality Assurance
There is a one-hundred-floor building and two identical hammers. You wish to determine the highest floor from which such a hammer can be dropped without breaking. You can drop these two hammers from various floors, but once one hammer breaks, it cannot be used anymore. Devise a strategy to exactly determine this floor using these two hammers under which the worst case number of trials (drops) is minimized.
Solution: The idea is to use the first hammer to narrow the floor down to a smaller range, using the second hammer to fine-tune, dropping it at incrementally increasing floors until it breaks. It is natural to consider dropping the first hammer from all floors divisible by ten, narrowing the critical floor down to one of the deciles. This approximately balances the expected number of drops between the two hammers, but it still leaves a worst case of 19 drops when the critical floor is number 99. To refine the strategy, we can balance the better cases (when the breaking point is on a lower floor) with the worst case by decreasing the size of every jump with the first hammer. With this in mind, we can determine by trial and error that the best strategy involves dropping the hammer from floor 14, then leaping 13 floors to 27, then to 39, and so on until the first hammer breaks. We then use the second hammer and drop incrementally from just above the last unbreaking floor until the hammer breaks or until we reach the floor from which the first hammer broke. Under this strategy our worst case is 14 drops.
3. Counting & Induction
3.1. Christmas Lights
There is a string of one hundred Christmas lights. All of the lights are initially off. A button is pressed: the state of every light is toggled (i.e., they all turn on). The button is pressed again: the state of every second light (lights 2, 4, 6, ...) is toggled. The button is pressed again: every third light is toggled. This continues until the one hundredth press. At the end, which lights remain on?
Solution: A light n is toggled once for every factor of n including unity and n itself. Since only perfect squares have an odd number of unique factors, only lights n for which n is a perfect square will be toggled an odd number of times and therefore remain on after all of the presses.
3.2. His Roommate Was a Logician
An anthropology student is conducting field work on a remote island. While looking for the camp of the tribe of Truth-tellers, he faces a fork in the road. At this fork is a representative from the tribe of Truth-tellers, whose every response to a yes-or-no question is true, and a representative from the the tribe of Liars, whose every response to a yes-or-no question is false. Since the anthropologist is in a hurry to reach the camp of the Truthtellers, he only has time to ask one yes-or-no question of one of the tribesmen, but he does not know which man is from which tribe. What question will guarantee him the path to the Truth-tellers.
Solution: The student can ask Tribesman A, would Tribesman B say that the left path leads to the camp of the Truth-tellers, if the response is No, then the left path leads to the Truth-tellers; if Yes, then the right path leads there. Alternatively, the student can ask Tribesman A, if I were to ask you if the left path leads to the camp of the Truth-tellers, would you say Yes if the response is Yes, then it is the left path; otherwise, it is the right path.
3.3. Lion's Dilemma
In a strange, isolated universe there are one hundred identical, rational lions and one sheep. In this universe, lions eat sheep, but in doing so themselves become sheep and are then at risk of consumption by another lion. Considering that all lions are rational, and all lions know that all lions are rational, and so on, a lion will eat a sheep if and only if the lion knows that he will not be consumed once he becomes a sheep. Will a lion eat the sheep?
Solution: Backward induction from the case of a single lion reveals that when there are an odd number of lions, the sheep will be eaten, and when there are an even number of lions, the sheep will not be eaten. Thus, in the case of one hundred lions, the sheep will not be eaten.
3.4. Pile of Stones
There is a pile of n stones. The pile is separated into two piles of arbitrary size. The sizes of the piles are multiplied and recorded. The resulting piles are then each split arbitrarily, with the product of the sizes of their two children computed and recorded. Each pile is split recursively until there are n piles of single stones. At the end, all of the recorded products are summed to arrive at one number, which is invariant to the way the piles are split.
1) What is this number?
Solution: A simple way of splitting the piles is to pull one stone off the master pile. The recorded products for this process are the numbers 1 through n − 1, whose sum is n(n − 1)/2.
2) Why is this sum invariant to the way the piles are split?
Solution: The sum is the total number of two-stone combinations. When the original pile is split and the sizes of the resulting piles multiplied, each stone in one pile scores one point for each stone in the other pile. As these piles are then broken down further, each stone scores additional points for every other stone that is split away into another pile. Ultimately, all stones are split away into separate piles, so every stone will score once for every other stone.
3.5. Tournament
There are 
teams in a sudden-death elimination tournament. In the first round, there are 
games, and the winners of those games proceed to the next round, in which there are 
games. This continues until one team wins the final round. How many games are played?
Solution: Brute-force calculation of the sum 
betrays the solution that can be intuited immediately from the fact that every team but one must lose exactly once.
3.6. Frantic Bee
Two trains are a distance 
apart and are approaching each other at a speed
. There is a bee that starts out in the middle of the two trains and then proceeds to fly toward one train. Whenever it arrives at one train, it instantly turns around and flies in the opposite direction. The bee flies back and forth between these trains until the two trains meet and the bee is squashed. If the bee travels at all times at a speed
, how much distance does it cover before its demise?
Solution: Brute-force summation is not necessary since the total time that the bee is flying is the time before the trains collide:
. The distance covered by the bee is this time multiplied by its constant speed:
.
3.7. Dotted Foreheads
One hundred mimes participate in the latest and least eventful reality television series. In the first episode, the viewers see that twelve of these mimes have a dot on their forehead. The mimes can see the foreheads of every other participant but cannot see their own. They are told by their host that at least one participant has a dot on his forehead and that at the end of every episode, any participant who knows that he must have a dot on his forehead must leave the show. Assuming that these participants are highly rational and compliant, how many episodes will run before all the dotted participants leave?
Solution: In the case where only one participant has a dot, this participant will know immediately that he is the dotted one when he observes no other dotted foreheads. In the case of two dotted participants, one dotted participant will see only one other dotted participant and will wait one episode to see if the other leaves. Observing that the other does not leave, the participant knows that he, too, must be dotted, and they both leave after the second episode. Induction reveals that in the case of twelve dotted participants, all twelve will leave after the twelfth episode. Of course, the problem’s formulation is fundamentally flawed: no rational person would take part in such a futile game.
3.8. Grid Lock
There is a square grid of 2n-by-2n squares and an infinite supply of three-square L-shaped pieces. A random square in this grid is blocked out. Can all of the remaining squares be filled using an unlimited supply of these three-square l-shaped pieces?
Solution: It can be determined by induction that the remaining squares can be filled regardless of which square is initially blocked out. The solution is trivial for the two-by-two case. The inductive step is made once it is clear that an L-shaped piece of twice the size can be constructed using four base L-pieces, and the blocked-out square can be doubled simply by placing an L-shaped piece to complete a blocked-out square region of twice the size.
3.9. Global Warming
Temperature is a continuous function along the surface of a globe. On two opposite poles, the temperatures are 
and 
where
. Are there two diametrically opposed points such that the temperature at those points is identical?
Solution: Yes. Consider the simpler case of a circle with diametrically opposed points at temperatures 
and
. As these points are rotated about the circle while still constrained to be radians apart, they will both cross some intermediate value 
between 
and
.
Instead of being diametrically opposed, two points are separated by some angle. Are there two points separated by the same such that the temperature at these points is the same?
Solution: Yes. The solution to the first part can be generalized for any angle.
4. Algorithms
4.1. Scrambled Vector
A vector of length n contains the integers 1 through n in random order.
1) An arbitrary entry in the vector is overwritten with a zero. How can the missing number be determined in an efficient way?
Solution: The sum of the numbers in the vector is subtracted from the known sum of the numbers 1 through n, or n(n + 1)/2. The difference is the value of the missing number.
2) Two arbitrary entries in the vector are overwritten with zeros. How can the missing numbers be determined in an efficient way?
Solution: The sum of numbers is subtracted from n(n + 1)/2 to determine the sum of the two missing numbers S. The product of the numbers is divided into n! to determine the product of the two missing numbers P. These two equalities imply a quadratic equation whose solution yields the missing numbers. Since n! can be very large, however, the solution to the final part of this problem is probably better applied in the case of two missing numbers.
3) Some k ≤ n arbitrary entries in the vector are overwritten with zeros. How can the missing numbers be determined in an efficient way?
Solution: Initialize a logical vector of length n with default values of true. Iterate through the vector: If the ith element is x, set the xth element of the logical vector to false. Finally, iterate through the logical vector and report the index of elements that are true; those indexes are the missing numbers.
4.2. Reunited at Long Last
Two robots are placed onto an infinite discrete line. The initial positions of both robots are indicated with identical markers. Every second, a robot can either remain still or move one unit to the right or left. The robot can detect that it is at the same point as a marker or another robot but cannot otherwise see a marker or robot at any distance away. Design one algorithm requiring bounded memory to be programmed into both of these robots that guarantees both robots will meet at some point on this line in finite time. Both robots must execute the exact same algorithm. No bound is known on the initial distance between the two robots.
Solution: Of course, a robot cannot simply be programmed to move in the direction of the other robot, since it cannot know the relative position of the other robot. One solution calls for an algorithm that requires the robot to move one tick to the right every other second until it encounters a marker, at which point it then moves one tick to the right every second. This algorithm requires only two bits of memory, one bit to remember if the robot moved to the right in the previous second and one bit to remember if the robot has encountered a marker. With both robots running this algorithm, they will move to the right at one tick per two seconds until the leftmost robot encounters the marker of the rightmost robot at which point the leftmost robot will double its speed to one tick per second, eventually catching up to the rightmost robot. If the initial distance between the robots is n, the robots will meet in roughly 4n seconds.
4.3. Linked List
Design an algorithm that is guaranteed to identify whether a loop exists in a singly-linked list. The algorithm should use bounded memory and complete in finite time. No bound is known on the length of the linked list or the length of a potential loop.
Solution: Begin two pointers at the head of the list and increment one pointer at twice the speed of the other. If and only if these two pointers point to the same node at any time after initialization and before the faster pointer reaches a terminal link, there is a loop in the linked list.
5. Finance
Pricing a Binary Option
In an ideal world where standard European call options exist for a continuous range of strikes and whose price is given by the continuous and differentiable function 
of the strike price
, what is the no-arbitrage price of a binary option 
struck at 
(i.e., an option that pays 1 if the underlying is above 
at expiry and 0 otherwise)?
Solution: A portfolio of call options consisting of long 
calls struck at 
and short 
calls struck at 
replicates the payout of the binary option as 
tends to zero:
