
Picking a Pair:
3, then at least 2 must be the same color as there are only 2 colors.
In general if the box had N colors then you would need to pull out N+1 socks.

Labeling the Boxes:
The surprising answer is 1. Pull a ball out of the box labelled black
and white. If the color you pull out is (X), then the correct label of that
box is X.
Now consider the box labelled by the other color. It must be labelled
incorrectly and cannot be X therefore it must be the Black and White Box,
and so we are done.

Burning Strings:
Start 3 ends burning. When one string is burnt, start the 4th end.
When all burning is done, you have 45 sec.

Quarters on a Table
Go first! Your first move should be to
place a coin in the center. Now whatever the opponent does your play is
diametrically opposite, since you are guaranteed to be able to play if your
opponent could have played. You therefore win.

Zeros Please:
249. In general, K! has floor(K/5)+floor(K/(5^2))+floor(K/(5^3))+.......
Why, because all you have to do is determine the number of factors of
5 there are in K!, as there are an abundance of 2's.

Communicating the Card:
The first card you pass can determine the suit that you hold, as there
must be at least two cards of a single suit (see problem 1). The remaining
3 cards can be used to determine (by ordering of the deck determined ahead
of time) a number from 1 to 6 that is encoded in which permutation you send
(the order in which you send the cards). You can now always ensure that the
denomination of the first card sent plus this number is the denomination of
the card you hold modulo 13 (as the maximum distance modulo 13 of the two
denominations is 6).

10 Balls, 2 Weighings:
Cant be done. This is an application of the pigeon hole principle.
With 2 weighings of 3 outcomes each, there are only 9 possible different
outcomes. But you have to be able to distinguish between 10 possible events
hence this is not
possible.
Beware the axiom of solvability  in real life, you do not
know if a problem is solvable or not.

12 Balls, 3 Weighings:
Label the balls {1,2,3,4,5,6,7,8,9,10,11,12}. Weigh A={1,2,3,4} against
B={5,6,7,8}. Use A< B to dentoe A is lighter than.
If A< B (a similar situation if A> B) let C={1,2,3,5} and D={4,9,10,11}.
If C< D, the faulty (light) ball is in {1,2,3}. Weigh 1 vs. 2 to resolve.
If C=D, the faulty (heavy) ball is in {6,7,8}. Weigh 6 vs. 7 to resolve.
If C> D, then either 5 is heavy or 4 is light. Weigh 5 vs. 12 to resolve.
If A=B then you have the remaining 4 balls {9,10,11,12} and 2 weighings.
Let C={9,10,11} and D={1,2,3} and weigh C vs. D.
If C< D, weigh 9 vs. 10 to determine which ball is light.
If C> D, weigh 9 vs. 10 to determine which ball is heavy.
If C=D, weigh 12 vs. 1 to determine whether it is heavy or light.

13 coins, 3 Weighings:
Label the balls {1,2,3,4,5,6,7,8,9,10,11,12,13}. Weigh A={1,2,3,4} against
B={5,6,7,8}. Use A< B to dentoe A is lighter than. If A< B (similar to
A> B) we use the algorithm above). If A=B then the faulty ball is in
{9,10,11,12,13}. Let C={9,10,11} and D={1,2,3} and weigh C vs. D.
If C< D then weigh 9 vs. 10 to resolve which ball is light.
If C> D then weigh 9 vs. 10 to resolve which ball is heavy.
If C=D then weigh 12 vs. 1 to determine if it is heavy or light. if neither,
then the counterfeit is 13.
To generalize, there are two possibilities.
a)
The first is that you know that the counterfeit is heavy. In this case:
Suppose there are N coins, then there are N possible states of the world.
There are 3^K possible outcomes of K weighings so
3^K> N
is a necessary constraint on K, the minimum number of weighings. That
this is the true minimum (ie also a sufficient condition)
is clear by the lemma that if you can do
X coins with K weighings then you can do 3X coins with K+1 weighings. This
is clear by splitting into 3 piles of X and using one weighing to determine
which group has the faulty coin and then using your algorithm on X coins
using K weighings. Clearly you can do 3 coins in 1 weighing so by induction
it is easy to show that you can do 3^K coins using K weighings.
b)
The counterfeit is of unknown weight, if it is desired to determine whether the
counterfeit is heavy or light then
Again, there are 2N possible states of the world. Thus
3^K> 2N
is a necessary constraint on K, the minimum number of weighings, however it is
not sufficient. It terns out that if 3^K> 2N+3, a solution exists.

6 Sticks, 4 Triangles:
Tetrahedron  dont always be planar in ones thinking.

4 Sticks, 16 RightAngles:
Consider the tictactoe board.

Tiling the Board:
Not possible. Every tile covers a black and a white square.
Removing the opposite corners removes two squares of the same color, so there
is an imbalance in the number of white and black squares.
To generalize, if M x N is odd, then there is one more white square than
black. If any white square is removed, the remaining squares
can be tiled, and if
a black square is removed, it cannot be tiled.
To see this, suppose that a white square is removed.
Then consider the row it was removed from  row k.
If k is odd, then the white square partitions that row into
two even parts which can easily be tiled, leaving (at most) two
smaller boards of even size which can be tiled.
If k is even, then the white square partitions the row into two
odd parts. Combining one odd part with the row above, and the other
with the row below, these two odd parts can be tiled, once again
leaving (at most) two smaller boards of even size which are easy to tile.
If M x N is even, then it is
easy to construct a Hamiltonian cycle in the board. It is now clear that if
any two squares of opposite colors are removed, then the remaining
can be tiled by following the Hamiltonian cycle.

Breaking the Chocolate Bar:
49. Any breaking strategy will solve this as every break adds exactly
one piece. Start with 1, end with 50 hence 49 breaks.

Guessing the Pair:
We reason as follows. For A to know that R cannot know the number, it
means that the sum cannot be expressed as the sum of exactly 2 primes. This
rules out even numbers (famous conjecture) and primes +2 leaving a list
of about 24 possibilities for the sum:
11 17 23 27 29 35 37 41 47 51 53 57
59 65 67 71 77 79 83 87 89 93 95 97
Since R then claims to know the number, this means that of the possible
factorizations into 2 numbers, only one yielded a sum in the allowed set
of sums. This reduces the possible products to
P={18,24,28,50,52,54,76,92,96,98,100,112,124,140,148,152,160,172,176,188,...}
with the corresponding sums being
S={11,11,11,27,17,29,23,27,35,51, 29, 23, 35, 27, 41, 27, 37, 47, 27, 51,...}
Now if A knows the numbers, he knows the product which means that only one
product could yield that particular sum. This is only the case for
S=17 thus we have that P=52 and S=17 yielding that the numbers are
13 and 4.

A Winning Betting Strategy:
There is nothing wrong with the reasoning except that
it is a high variance strategy. Notice that the expectation for each
play assuming independence is 0, thus for any strategy, the expected gain
is 0. The flaw in the logic is that one has a finite bank, hence this game
ends with a loss of the bank with probability 1 if played for ever.

Toggling the Lightbulbs:
The number of times a bulb i is toggled is equal to the number
of divisors i has. If i is not square then it has an even number of
divisors (for every divisor < sqrt(i) there is one > sqrt(i)).
If i is square then it has an odd number of divisors. A bulb is on if toggled
an odd number of times, so the bulbs in the square positions are on at
the end.

The Following Cars:
By symmetry the cars meet at the center. Since the velocity of a car is
always directly toward the target car and the velocity of the target car
is always perpendicular to this direction, the target car's velocity
contributes nothing to the shortening of the distance. Thus the entire 1 mile
to the target car is traversed by each car.

The Towers of Hanoi:
This is the famous towers of Hanoi problem. Call the current peg C then
we wish to get all the discs to A. We solve the identical but slightly smaller
problem of getting the N1 smallest pegs to B. Any solution must pass through
this stage. Thus if M(N) is the required number of moves, we can move
N1 to B using M(N1), one move to put the largest peg onto A and then
M(N1) to get the remaining pegs onto A. Thus
M(N)=2M(N1)+1 or
M(N)+1=2*(M(N1)+1)
This recursion is easily solved: M(N)=2^N1

Taking Coins Away:
Represent the number of coins in each stack by a binary number and align
the binary numbers on top of each other.
You win if it is your opponents turn with all piles empty, i.e., all the
binary numbers are 0.
Thus, in every column in the stacked binary numbers, there are an
even number (zero) of 1's in the winning configuration.
Consider any configuration with an even number of 1's in every column.
Since a draw changes one of the numbers, at least one 1 or zero in
that row must change, hence it is not possible to win from this configuration.
Thus if you maintain
this the invariant that every column have an even number of 1's,
you can guarantee winning. If the initial configuration
has an even number of ones in each column, then you must play second.
To maintain the invariant, you consider the first column from the
left with an odd number of 1's. Pick one of the piles which has
a 1 in this column. Now remove coins from this column so that
this column and all columns to the right have an even number of
1's.

The Unfaithful Husbands:
Lets simplify the problem. If there are 1 man and woman, then on the first
day since the queen said that there is an unfaithful man, the woman immediately
knows that it must be her husband, so the man dies on the first night.
Now consider two men and women. The women reason as follows.
Suppose that noone dies on the first night. That means that the other
woman must know that my husband is unfaithful. For if my husband were honest,
then the other woman would immediately conclude that her husband is dishonest
(as at least one unfaithful exists) and hence that husband should have
died on the first night. The only reason no one dies on the first night
means that everyone sees at least 1 unfaithful man. Thus on the second day
I conclude that my husband is unfaithful and he dies that night. This
happens to both men. Now consider 3 men and women. I, a woman reason as
follows.
day 1: I see two unfaithfuls so I do nothing.
day 2: I assume my man is faithful, and reason, that both of the other women
must see only one unfaithful. In which case after 1 day, they each conclude
that their husbands are unfaithful (the same as the two man, two woman)
and so on the second night these two unfaithfuls should die.
day 3: I conclude that since no one died yet, my husband is unfaithful.
All women reason this way and on night 3, all 3 men die.
By induction one can prove that if there are K unfaithfuls,
then they all die on the Kth night.

The Dishonest Politicians:
There cannot be more than 1 honest.

The Savy Archaeologist:
The printer of the 44BC coin would have to be extremely
clairvoyant to know when christ would be born. Hence any decent
assistant should know that the coin is fake.

Going up and Down the Hill:
Imagine that on my descent another person started an ascent
in exactly the same way as I did the previous day. We must meet at some
point.

Squares Inside Squares:

Eat Pie or Pie Eat:

Triangulating the Stick:

Efficient Swap:
A=A+B;B=AB;A=AB;

Near Perfect Predictability:

Interviewing Models (aka Dating):
see Magdon's 1/e theorem for dating

The Monty Hall Problem:
Switch. There are 3 possibilities to start with: prize behind door 1,2
or 3. In two of these you win by switching.

The Number Dryer:

Don't Play Roulette with Russians:

Fake from Real in One Weighing:
Suppose that the buckets are labeled
a9 a8 a7 a6 a5 a4 a3 a2 a1 a0
and let ai=0 if the bucket is real and ai=1 if the bucket is fake.
Suppose that the number of coins taken out of each bucket is
c9 c8 c7 c6 c5 c4 c3 c2 c1 c0
Choose the ci's as follows:
512 256 128 64 32 16 8 4 2 1
so the sum of the ci's is 1023. After weighing all these coins,
the total weight will be in excess of 1023 by some amount, call this ammount
E, and consider the binary expansion of E. Let the binary expansion be
b9 b8 b7 b6 b5 b4 b3 b2 b1 b0
then we claim that ai=bi and we have determined which buckets are fake (the
ai's that equal 1). It is not hard to prove that this is the case since every
integer has a unique binary expansion. As an example, suppose that a4 and
a1 are fake, then the excess will be 32+2=34 which has binary expansion
0 0 0 0 0 1 0 0 1 0
correctly identifying the fake bins. In fact one can prove that this is
the minimum number of coins that one can pick and guarantee being able to
identify all the fake bins.
If there are only 100 coins per bucket then clearly the above scheme does not
work, as it requires picking more than 100 coins from some buckets. In fact
we will prove that no scheme can work. Clearly any subset of the buckets
can be fake. The excess E will be the sum of the ci for those buckets that
are fake. Therefore in order to be identify correctly, for every possible
subset of the buckets, the sum of that subset of the ci must be unique
(different from every other subset sum). Since each ci is at most 100,
the maximum possible subset sum is 1000, and so there are at most 1001
different subset sums (0,1,...1000). But there are 2^10=1024
possible subsets so there is no way to distinguish every one of these (this
is called the pigeonhole principle). Thus it is impossible with at most
100 coins per bucket.

Don't Restrict my Choice:
If the bag contained a black and white ball,
there is only one possibility for the white
ball in your hand. If the bag contained two whites, there are two, for a total
of three possibilities. Two of these lead to the remaining ball being white,
hence 2/3.

The Slimy Auction:

Why Do We Need Rear Windshield Wipers:
The rain falls at some speed. The car moves at speed v, so the relative
velocity of the rain with respect to the car makes an angle with the
vertical, which becomes larger as v increases. When this angle is larger than
the angle of the rear windshield (for large enough v), the rain will not hit
the rear windshield. Thus, rearwind shield wipers are generally of no use,
even in torrential rain, as long as you are going at some minimum
speed.

Sharing the Cake:

Securing the Vault:
Consider a set of 5 people. They cannot open at least 1 lock. Any other
person must be able to open this lock (since a majority must be able to open
the safe), therefore, any
different subset of 5 people must be able to open this lock. Thus there
has to be at least 1 lock for each different subset of 5 people. This is
11 choose 5 or 462 locks. Now consider a person. Every different subset of
5 people from the ten people excluding this person has at least
1 different lock that this person must be able to open, therefore this
person must have at least 10 choose 5 different keys, or 252 keys. This
solution is attainable by having a new lock for every one of the 462
subsets of 5 people, and giving every person not in a particular subset the
key for that subset.
In general if there are N people and at least M must be present to open, then
N choose M1 locks are needed, and N1 choose M1 keys.

Icecream and Students:
This is equivalent to the number of ways to place 6 indistinguishible
balls in 11 bins, or 16 choose 6. To get this answer imagine placing
18 positions on the line. The left most and right most must be walls of
the bins. Of the remaining 16, 6 have to be chosen for balls and 10 for
bin walls.

Counting the 1s:

Building from Basics:



Befudling the USPS:



The Paranoid Maharaga of Patiala:



Friends or Foes:

Got Gas?

Fighting for Fifteen:
This is tictactoe on a magic square. We all know that tictactoe
is a draw with optimal play, pick 5 to start.

The Scared Guards:

Tipping the Balance:

Rectangles in Rectangles:

The Accurate Clocks:

Equal Sums:

The NonFloating Pebble:

Leaving the Grounds:

A Curious Tour:

A Prime Problem:

Turning On the Bulb:

What's Up with Climate Control:

$7.11 at 711
$1.20, $1.25, $1.50, $3.16  note that this problem becomes a
problem in the integers once all numbers get multiplied by
100: w+x+y+z=711 w*x*y*z=711000000.

Buying Letters:
TWELVEELEVEN=TWEN=TWOONE=$1 so $6.

Remembering the Number:

In Tens to Hundred:

An Odd Way to Exceed 45:

Guessing the Hat:

Equalizing the Piles:

4 Men and a Flashlight:

Even Odds for Even Choices:

Tournament Matches:

Three Odds making Even:Put 1, 2 and 7 balls in the cups.
Now place the cup with one ball inside the cup
with 2 balls.

Bartering Links :
Cut links 5,14 and 31 to obtain pieces of sizes 1,1,1,4,8,16,32. Two pices of
size 1 can be used as a piece of size 2 to obtain disjoint sets of links of
sizes 1,2,4,8,16,32. Using binary representations, it should be clear that
any size up to 63 can be represented.
For 2^k1, a similar strategy can be used.

Guessing Your Friend's Number:
Yes.

Maximizing the Probability:
Put one white in one jar and the rest in the other for almost 0.75 probability
of getting white.

Word Paths:
Here are two possible solutions:
WARM, WORM, WORK, CORK, COOK, COOL,
WARM, WORM, WORD, WOOD, WOOL, COOL

Triangle Areas:
400,500,600. Put the base as 400 in both cases, and construct the
triangle with 500,600 as the other sides. To replace the 600 with 700,
you have to rotate the 500 side closer to the base, which means it has smaller
height but the same base.

Heaven or Hell:
To one of them ask what the other would say is the way to heaven, and take
the other path.
If only one person is there, something like "If I were to ask you which way
to heaven, tell me what would you say?", and follow that direction. This is
the so called double negative being used.

Shrivelling Watermellons:
50 lbs. (1 lb of watermellon and 49 lbs of water is 98% water).

Maximizing the Product:
100 terms equal to 2.71 each.

Tossing Coin Sequences:




Only Marginally More Favorable:
1/2. Since either A has more heads or more tails, and not both, by symmetry,
each of these must have equal probability.

A Tricky Equation:

An Interesting Sum:
By the axiom of solvability it should not depend on what is in the {a} set
and what is in the {b} set. Thus set a={1,2,...,n} and
b={n+1,...,2n}, in which case the sum is clearly n^2. Knowing the answer,
it is now not so tough to prove this.
This result is known as Proizvolov's Identity

Irrational Trigonometry:

Measuring With SandGlass:
Start the 11 and 7 minute sandglasses. When the 7 is done, flip it over.
When the 11 is done, flip over the 7 again to measure another
4 minutes.

Coloring The Plane:

Dividing the Children:

Tiling with an L:
Yes. Here is the recursive algorithm.
Consider the central 4 squares and place an L on these
squares. Imagine the original square divided into
4 squares of equal size, S1,S2,S3,S4 (suppose S1 contains the missing
square). This first L should be placed so as to intersect the
squares S2,S3,S4. Now what remains of S1,S2,S3,S4 are 4 squares of
side 1/2 the original, each of them "missing" one of its corner
squares. As long as these smaller problems can be solved, the larger one
can too. Thus since the 2x2 version is easy to solve no matter which
"corner" square is removed, the recursion works and we are done.

Area Between Concentric Circles:
2500pi. By the axiom of solvability the answer cannot depend on the two
radii of the circles. Hence we can take one to 0 and the chord C becomes
the diameter of the larger.
C/2, r1 and r2 form a right triangle, hence using Pythagoras and
the fact that the desired area is pi(r2^2r1^2) also immediately
gives the answer pi*C^2/4.

The Knight Tour:

Determining The Number of Heavier Balls:

Identifying the Weights:

Integer Midpoint:

Divisible Subsets:

Packing Balls:

Dividing Coconuts:

Splitting The Proceeds:

Dividing by n!:

This also follows from the second part by considering
(t+a)!/t!. We will give a direct proof.

This follows from the first part by breaking n!
up into the product of a consecutive integers
and b consecutive integers and c consecutive integers
and so on. We will also give a direct proof.
to tell me of an extremely ingenious and short solution
that you have found.
If you have puzzles that can be solved with some
ingenious and creative trick, I would like to know of it!