Suggested Solutions

Since many have asked for solutions to various puzzles, I post them here when requested (if I have the energy to write them up). Alas, this list is not complete. Perhaps someday, I will complete it. If you have ingenious solutions to any of the puzzles, email me your solution (and how you would like to be acknowledged), and I will post it. -MMI.

Fun
Technical

Fun:
  1. 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.
  2. 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.
  3. Burning Strings: Start 3 ends burning. When one string is burnt, start the 4th end. When all burning is done, you have 45 sec.
  4. 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.
  5. 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.
  6. 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).
  7. 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.
  8. 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.

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

  10. 6 Sticks, 4 Triangles: Tetrahedron - dont always be planar in ones thinking.
  11. 4 Sticks, 16 Right-Angles: Consider the tic-tac-toe board.
  12. 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.

  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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 N-1 smallest pegs to B. Any solution must pass through this stage. Thus if M(N) is the required number of moves, we can move N-1 to B using M(N-1), one move to put the largest peg onto A and then M(N-1) to get the remaining pegs onto A. Thus
    M(N)=2M(N-1)+1 or
    M(N)+1=2*(M(N-1)+1)
    This recursion is easily solved: M(N)=2^N-1
  19. 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.
  20. 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 no-one 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.
  21. The Dishonest Politicians: There cannot be more than 1 honest.
  22. 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.
  23. 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.
  24. Squares Inside Squares:
  25. Eat Pie or Pie Eat:
  26. Triangulating the Stick:
  27. Efficient Swap: A=A+B;B=A-B;A=A-B;
  28. Near Perfect Predictability:
  29. Interviewing Models (aka Dating): see Magdon's 1/e theorem for dating
  30. 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.
  31. The Number Dryer:
  32. Don't Play Roulette with Russians:
  33. 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.
  34. 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.
  35. The Slimy Auction:
  36. 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, rear-wind shield wipers are generally of no use, even in torrential rain, as long as you are going at some minimum speed.
  37. Sharing the Cake:
  38. 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 M-1 locks are needed, and N-1 choose M-1 keys.
  39. Ice-cream 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.
  40. Counting the 1s:
  41. Building from Basics:
  42. Befudling the USPS:
  43. The Paranoid Maharaga of Patiala:
  44. Friends or Foes:
  45. Got Gas?
  46. Fighting for Fifteen: This is tic-tac-toe on a magic square. We all know that tic-tac-toe is a draw with optimal play, pick 5 to start.
  47. The Scared Guards:
  48. Tipping the Balance:
  49. Rectangles in Rectangles:
  50. The Accurate Clocks:
  51. Equal Sums:
  52. The Non-Floating Pebble:
  53. Leaving the Grounds:
  54. A Curious Tour:
  55. A Prime Problem:
  56. Turning On the Bulb:
  57. What's Up with Climate Control:
  58. $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.
  59. Buying Letters: TWELVE-ELEVEN=TW-EN=TWO-ONE=$1 so $6.
  60. Remembering the Number:
  61. In Tens to Hundred:
  62. An Odd Way to Exceed 45:
  63. Guessing the Hat:
  64. Equalizing the Piles:
  65. 4 Men and a Flashlight:
  66. Even Odds for Even Choices:
  67. Tournament Matches:
  68. 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.
  69. 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^k-1, a similar strategy can be used.

  70. Guessing Your Friend's Number: Yes.
  71. Maximizing the Probability: Put one white in one jar and the rest in the other for almost 0.75 probability of getting white.
  72. Word Paths: Here are two possible solutions:
    WARM, WORM, WORK, CORK, COOK, COOL,
    WARM, WORM, WORD, WOOD, WOOL, COOL
  73. 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.
  74. 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.

  75. Shrivelling Watermellons: 50 lbs. (1 lb of watermellon and 49 lbs of water is 98% water).
  76. Maximizing the Product: 100 terms equal to 2.71 each.
  77. Tossing Coin Sequences:
  78. 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.
  79. A Tricky Equation:
  80. 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
  81. Irrational Trigonometry:
  82. Measuring With Sand-Glass: 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.
  83. Coloring The Plane:
  84. Dividing the Children:
  85. 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.
  86. 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^2-r1^2) also immediately gives the answer pi*C^2/4.

  87. The Knight Tour:
  88. Determining The Number of Heavier Balls:
  89. Identifying the Weights:
  90. Integer Midpoint:
  91. Divisible Subsets:
  92. Packing Balls:
  93. Dividing Coconuts:
  94. Splitting The Proceeds:
  95. 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.
Technical:

  1. A Trig Inequality: Cos(Sin x) > Cos (x) > Sin(Cos x) (Cos is a decreasing function and Sin(x)
  2. The Monotonic Subsequence:
  3. Condensing the Gaussian:
  4. A Probability Problem:
  5. Integer Representations:
  6. Divisors:
  7. Co-Prime Probability:
  8. A Line Through 2 Points:
  9. Matching the Hats:
  10. Betting the Deck:
  11. Sampling Rationals:
  12. : Here is a problem originaly (to the best of my knowledge) posed by Moorthy. Consider an m by n square lattice (i.e. a rectangle decomposed into mn unit squares). Color the vertices in this lattice using two colors in any way you like.

    Question: For a large enough lattice (m,n), no matter how you color the vertices, there is a set of four monochromatic vertices at the corners of a square (the square may be of any size)?

    The original motivation for this problem is to construct a misere game for two players who alternately color the vertices on a large enough grid. The loser is the first player to create such a monochromatic quadruplet.

  13. : If x is a positive rational number, show that x^x is irrational unless x is an integer.
  14. : Let H(n) = 1/1 + 1/2 + ... + 1/n. Show that, for n > 1, H(n) is not an integer.
  15. : Given any sequence of n integers, show that there exists a consecutive subsequence the sum of whose elements is a multiple of n. For example, in sequence {1,5,1,2} a consecutive subsequence with this property is the last three elements; in {1,-3,-7} it is simply the second element.
Email 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!