Puzzles and Games

Herein are a small collection of diversions that I find interesting, usually because their solutions are creatively simple. Some of them are not mine (and I have been quite relaxed about providing the sources), so if you would like further references simply e-mail me. Please contemplate...and feel free to e-mail your thoughts to me. -MMI.

You can find some of the solutions here.
Fun
Games
Bridge
Technical

Fun:
  1. Picking a Pair: 100 black and white socks are in a drawer. How many socks must you pull out before you are guaranteed to have a pair? Generalize to socks of K different colors.
  2. Labeling the Boxes: 3 boxes, one with black, one with white, and one with black and white balls are all labeled incorrectly. What is the minimum number of balls that need to be pulled before you can relabel all the boxes correctly?
  3. Burning Strings: 2 strings burn continuously and reversibly in 1 minute. You have an unlimited supply of matches. How do you measure 45 sec?
  4. Quarters on a Table In this game, you and an opponent take turns in placing identical circular coins on a circular table so that they do not overlap. Coins must remain on the table. The last person able to place a coin wins. Do you want to go first or second?
  5. Zeros Please: How many zeros at the end of 1000! (1000 factorial) ?
  6. Communicating the Card: You have a deck of cards. 5 cards will be randomly picked. You can have a "decoding" system with your partner. The goal is for you to transfer 4 cards to your partner and he after looking at the 4 cards must guess the remaining card. How can you always achieve this.
  7. 10 Balls, 2 Weighings: You are given 10 balls and a comparison balance, one is heavier. You have 2 weighings, your goal being to determine the heavier ball.
  8. 12 Balls, 3 Weighings: You are given 12 balls and a comparison balance. One has different weight. Can you determine which one and whether it is heavier or lighter with only 3 weighings? If so how, and if not, why not?
  9. 13 coins, 3 Weighings: You are given 13 coins, 12 genuine and 1 counterfeit. It is given that the counterfeit coins and genuine coins have different weights. You are also given a scale which when given a pair (A,B) of disjoint subsets of the 13 coins returns how the weights of A and B compare (equal, greater, or less). If you are allowed at most 3 uses of the scale, how would you determine which coin is counterfeit? Can you generalize this problem? (With an appropriately generalized solution, of course!)
  10. 6 Sticks, 4 Triangles: Arrange 6 match sticks so that 4 equilateral triangles are formed.
  11. 4 Sticks, 16 Right-Angles: Arrange 4 match sticks so that 16 right-angles are formed.
  12. Tiling the Board: An 8x8 chess board can be tiled with 32 dominos. Suppose we remove the left top and right bottom corner of the board. Can the remaining 62 squares be tiled by 31 dominos?
    Generalize to an MxN chess board: if both M and N are odd, under what conditions can the board be tiled if one square is removed; if M or N is even and two squares are removed, under what conditions can the board be tiled.
  13. Breaking the Chocolate Bar: You are given a bar of chocolate with 50 squares (5 x 10). What is the minimum number of breaks necessary to break the bar into 50 individual squares? A bar (or a piece of it) can only be broken along a straight line that runs from one side to the other. Pieces cannot be stacked while breaking.
  14. Guessing the Pair: Adam, Rob and Rohit are sitting on the beach at Malibu around 3am.

    Rob:

    "I just picked two integers greater than one and their sum is less than 100."
    "Adam, their sum is ..." (he whispers it to Adam).
    "Rohit, their product is..." (he whispers it to Rohit).
    Adam:
    "Rohit, we don't know the numbers."
    Rohit:
    "Now I do."
    Adam:
    "Me too".

    What were the numbers?

  15. A Winning Betting Strategy: Person A and B play the following game. Person A makes a bet of x dollars on heads or tails. Person B then tosses a fair coin. If the outcome matches A's guess, A receives 2x dollars; otherwise, A loses his bet. Consider the following strategy for A: x:=1 initially; if win, then x:=1; otherwise x:=x*3. Now, if A wins at any point, he makes a profit. This means that A will always make a profit. What (if anything) is wrong with this strategy?
  16. Toggling the Lightbulbs: There are 100 light bulbs and 100 people, both numbered from 1 to 100. Initially, all the light bulbs are off. Person number k toggles all the light bulbs that are divisible by k. For example, person 2 toggles bulbs 2, 4, 6, ..., 100. After all 100 people have finished toggling the light bulbs, which light bulbs are on?
  17. The Following Cars: Four cars that all move with the same speed of 60 mph start off at the four corners of a square of side 1 mile. Label the cars in clockwise order 1,2,3,4. At every instant, car 1 moves in the direction of car 2, car 2 in the direction of car 3, car 3 in the direction of car 4 and car 4 in the direction of car 1. Where will the cars eventually meet and how far will each car have travelled.
  18. The Towers of Hanoi: 50 disks are stacked on a peg in decreasing size (the largest on the bottom). Two empty pegs A and B are available. What is the minimum number of moves that need to be made to transfer all the disks onto peg A if at no time can a larger disk can be placed on top of a smaller one.
  19. Taking Coins Away: There are three piles of coins. Two players take turns to remove any number of coins from any single pile. The last person able to make a move wins.
    • The piles contain 13,11,6 coins. Do you want to move first?
    • The piles contain 13,11,22 coins. Do you want to move first?
  20. The Unfaithful Husbands: There are 100 men and women (all married) on an island, and a queen. Every husband is unfaithful, a fact known to everyone but the wife of that particular husband. The queen declares that at least one husband is unfaithful. The queen declares that if you find out that your husband is unfaithful, you must banish him from the island at exactly midnight on the day that you find out, in a public ritual. There is no communication between the women and no man is going to divulge the crimes of his fellow men. What happens in this society?
  21. The Dishonest Politicians: In a room of 100 politicians, at least 1 is honest and in every pair, at least one is dishonest. How many honest politicians are there, if every politician is either honest or dishonest.
  22. The Savy Archaeologist: An archaelogist and his assistant are working. The assistant makes a great find, and thinking that he will get a promotion boasts it off to his master. Look here is a Roman coin: one side had 44 BC printed on it and one had an imprint of an olive tree. The archaelogist immediately fired the assistant. Why?
  23. Going up and Down the Hill: I started up a hill at sunrise and arrived at the top at sunset. The next day at sunrise I started back down and reached the bottom at sunset. If the sun rises and sets at the same time every day, is there a point in time where I was at the same place on my upward as well as downward journey?
  24. Squares Inside Squares: In a chess board with 64 by 64 squares, what is the total number of squares (of any size) that can be formed? generalize to cubes in a 64 by 64 by 64 cube. Generalize to "K-dimensional cuboids" in a 64^K cube.
  25. Eat Pie or Pie Eat: Which is larger, e^pi or pi^e?
  26. Triangulating the Stick: What is the probability that if you cut a stick at 2 random places you can form a triangle?
  27. Efficient Swap: Write code to swap two variables A and B without using a third variable.
  28. Near Perfect Predictability: So we are familiar with paradoxes having to do with perfect prediction. For the purposes of this mission assume that there exists a machine that can predict your action correctly with probability (1-a) where a can be made as small as we wish. For all practical purposes it can predict you perfectly. Here is the game...

    • In a sealed room is a transparent box and an opaque box. The transparent box contains $100. The opaque box is currently empty. You go in and survey the scene.
    • The rules of the game are as follows. You will eventually be given a choice. Either you can choose the opaque box only, or you can choose both boxes. I will consult my machine. If my machine predicts that you will take only the opaque box then I will insert $1000000 into it. If it predicts that you will take both boxes, I will do nothing.
    • So you now leave the room and I consult my machine. I do whatever I have to do and pick up my machine and leave the room. You enter and now have 1 hour to make your choice.
    • What do you do? - Remember that the machine can essentially predict you with 100% accuracy.
  29. Interviewing Models (aka Dating): Here is the problem. You are the manager at Victoria Secret. You will be interviewing 100 young'uns for the position of Assistant Manager. Your goal is to select the best, failure results otherwise, and you lose your job.
    • The problem is that you do not see all the applicants at once and you have to immediately notify the current applicant if you are hiring her or else s/he will just settle for some job say at Express or something, who knows.
    • What is your best strategy?

    Magdon's 1/e theorem for dating - what an application!
  30. The Monty Hall Problem: There are 3 doors, behind one of which is a prize. You pick a door and I am forced to show you a vacant door (other than the one you picked). I now give you the option to switch to the remaining door. Do you definitely want to switch, definitely not want to switch or does it matter whether you switch or not.
  31. The Number Dryer: At a party with 100 people, everyone is to write down a number between 0 and 100. The person who writes the number closest to two thirds the average number will win the prize. What number should you write down. What number would you write down? Try this experiment at a party and see what the winning number is and compare to the number you should write down and the number you would write down.
  32. Don't Play Roulette with Russians:
    • Russian roulette is played as follows. Into a 6-shooter pistol is placed one bullet. The barrel is then rapidly rotated and comes to a stop. Now 2 players take it in turns to place the gun to their head and shoot. Eventually the game ends with one player dead. Do you want to shoot first or second? Generalize to K-shooter russian roulette played by M players and compute the probability that you stay alive if you follow the optimal strategy.
    • A fair coin has probability of turning up heads (p) given by p=0.5. You and another player take turns to toss the coin. Whoever tosses the first head wins $1. Do you want to toss first or second. Generalize to M players. If you choose the optimal action (given p and M), what is your probability of winning (as a function of p and M).
    • Aren't the two problems essentially the same? The second seems to be the equivalent to the first for very large K, in fact the limit as K goes to infinity. So how come the answers are different?
  33. Fake from Real in One Weighing: There are 10 buckets of coins. Real coins weigh 10 grams. Fake coins weigh 11 grams. Buckets are either fake (contain only fake coins) or real (contain only real coins). Each bucket contains the same number of coins. You have one weighing to weigh any number of coins picked from buckets of your choice. If there are 1000 coins per bucket, can you determine which buckets are fake with one weighing? If there are 100 coins per bucket, can you determine?
  34. Don't Restrict my Choice: A ball is picked from a box of 1000 black and 1000 white balls and thrown into a bag. You are then given the bag. You have a white ball. You throw this into the bag. You then pick a ball from the bag and it happens to be white. What is the probability that the ball remaining in the bag is white?
  35. The Slimy Auction: At a party with many people, I offer up for auction $1, and people bid. The eventual highest bidder gets my $1 for whatever was bid. The catch is that the second highest bidder also has to pay the amount he/she bid to the highest bidder. Do you want to play. If so what will happen in this auction?
  36. Why Do We Need Rear Windshield Wipers: I was speeding from Boston to Albany in torrential rain - please do not do this at home. I had my wipers on full and I could barely see the road. We have all experienced this, I guess. An interesting observation: my rear windscreen was PERFECTLY dry. Not a drop of water on it, whereas my front windscreen was drenched. Pity too, because my car needed a wash and now everything is clean except for the rear windscreen.
    Balls now in your court!
    (Bonus: What speed would you suspect the phenomenon to pop up at - you'll be surprised)
  37. Sharing the Cake: There are three kids, Alan, Brian and Cory (A,B,C), your 3 kids. You have a cake that you want to divide fairly among these three. The different kids value the different parts of the cake differently. You can ask any kid to cut any piece of cake into a specific ratio - this is the only way you can get information about how a particular kid values a particular part of the cake. Assume that to every kid, a set of pieces has a value equal to the sum of values of each piece. Each kid will be happy if they think they have at least 1/3 of the value of the cake. Describe a way of doing this that uses at most 3 cuts. Can you do better?
    • What about if Dick now came along. Is there a way to divide with 3 cuts so that each receives what they believe is at least 1/4 of the cake. What about 4 cuts? 5 cuts?...
    • Suppose now each kid is happy if they each believe they have more than their fair share. Can this be done with 3 kids?
    • Suppose now that each kid is happy only if they believe they have more cake than anyone else. Can this be done with 3 kids?
    • Can you generalize the problem and your algorithms?
    This problem is called fair cake-cutting and has a number of ramifications in economics, arbitrage based finance, computer resource allocation, auctions, fair inheritance division among siblings....
  38. Securing the Vault: There are 11 vice presidents of a bank. The vault containing the cash is to be locked using a number of locks and the keys to the locks are to be given to the vice presidents so that the only way that all the locks may be opened and access to the vault gained is if a majority of vice presidents are present. What is the minimum number of locks and keys that are required?
  39. Ice-cream and Students: An ice cream shop has 11 flavors. A teacher wishes to buy 6 cones for some students. In how many ways can these 6 flavors (not necessarily different) be chosen?
  40. Counting the 1s: Among the integers from 0 to 10,000,000,000 do the majority of them contain a 1?
  41. Building from Basics:
    1. In how many ways can 37 cents be made up using 1 and 2 cent stamps. Generalize to n cents using 1 and k cent stamps.
    2. In how many ways can 37 cents be made up using 1, 2 and 3 cent stamps. Generalize to n cents using 1, 2 and 3 cent stamps.
  42. Befudling the USPS: One of the problems with the US postal service is that every now and again, they raise the rate for first class postage (by say 1c). This makes it extremely inconvenient to stock up on stamps. For example, I have a whole bunch of 33c stamps which I cannot use unless I buy a whole bunch of 1c stamps. There are ways around this problem
    1. Show that using only 4 and 5 cent stamps, you can come up with any postage greater than 11 cents. Thus, it suffices to stock up on only 4 and 5 cent stamps. For example the current postage is 37c which is eight 4c stamps and and one 5c stamp.
    2. Show that using only 6 and 7 cent stamps, any total greater than 29c can be made.
  43. The Paranoid Maharaga of Patiala: A maharaja has a wine cellar containing 100 amphoras of wine. A traitor gets into the cellar to poison the wine and gets detected and killed after he has poisoned only one amphora. The contaminated amphora is not known, however the poison is known to kill in exactly one month. The maharaja has some tasters. If the maharaja uses some tasters to taste wine bottles, then that taster cannot be used to taste anything else for a month.
    1. The maharaja wants to be able to drink wine in a month, what is the minimum number of tasters the maharaja should be willing to put out of commission for at least a month in order to be able to drink wine safely in a month?
    2. The maharaja wants to throw an orgy in a month using all the uncontaminated amphoras. What is the minimum number of tasters that the maharaja must be willing to put out of commission (for a month) in order to be able to have this orgy? For example, a solution is to use 100 tasters, one on each amphora. One can do better though.
  44. Friends or Foes: Is it always true that in a gathering of 6 people, either at least 3 are mutual strangers or at least 3 are mutual friends?
  45. Got Gas? On a circular circuit around the city, there are fuel stations. All the fuel in these stations is just enough to complete one circuit around the city. Is it always possible to start at one of the stations with an empty tank and complete one full circuit without running out of fuel?
  46. Fighting for Fifteen: Two players alternately pick numbers without replacement from the set 1,2,3...9. The first player to obtain three numbers that sum to 15 wins. What is your strategy?
  47. The Scared Guards: 57 security guards are positioned so that no two pairs of guards are the same distance apart. Every guard watches the guard closest to him. Is there an arrangement of the guards so that every guard is being watched?
  48. Tipping the Balance: In a party with 50 people, there are 10 weights, and on each weight is written the name of at least one person. The weights are positioned on a balance scale, some on the left and some on the right. When a person enters or leaves the room, he takes all weights containing his name and switches the side on the balance that they are on. In its initial configuration, the balance is tipped to the right (i.e. the weights on the right are heavier than those on the left). Is there necessarily some configuration of people who can enter the room that will tip the balance to the left?
  49. Rectangles in Rectangles: A rectangle is partitioned into smaller rectangles. Each smaller rectangle has either an integer height or an integer width (or both). Show that the original large rectangle must have either an integer height or integer width (or both).
  50. The Accurate Clocks: 7 identical watches are lying on a circular table. They all say the same time. Show that there is some point of time at which the sum of the distances from the center of the table to the center of the clocks is smaller than the sum of the distances from the center of the table to the tips of the minute hands.
  51. Equal Sums: Take any 10 different integers between 1 and 100. Of these 10 numbers there are two disjoint sets with the same sum.
  52. The Non-Floating Pebble:
    • A container with a small pebble is floating in a bucket of water. The pebble is taken out and dropped into the water. The pebble sinks to the bottom of the bucket. Does the level of the water in the bucket rise or fall?
    • A cube of ice is also floating in the bucket. The ice subsequently melts. Does the level of the water in the bucket rise or fall?
    Leaving the Grounds:
  53. You are at the center of a circular field with radius 1 mile. A guard dog is restricted to run around the perimeter. You run at 10mph and the dog at 40mph. Your goal is to escape from the field, and the dog will try its best to stop you. Can you escape?
  54. A Curious Tour: I walk on the earth (a perfect sphere) 10 miles south, then 10 miles east and then 10 miles north to return to my starting point. Where can I be?
  55. A Prime Problem: If p>3 is prime, then p^2-1 is divisible by 24?
  56. Turning On the Bulb: A light bulb is controlled by 2 switches on a bar. The bulb will light if all switches are simultaneously on. Initially the bulb is off. On each turn you may toggle any subset of the switches. However, after each turn an adversary may rotate the bar through any angle. Is there a way to guarantee that after a finite number of turns, you will be able to switch the bulb on?
    • What if the bulb were controlled by 3 switches on an equilateral triangle?
    • What if the bulb were controlled by 4 switches on a square?
    • can your algorithm be generalized...?
  57. What's Up with Climate Control: In my brand new car with climate control, I can set the temperature to some value, and the "car" automatically maintains the temperature at this value. During the summer, I find I am most comfortable setting the temperature to 75F, whereas in the winter I find that I am most comfortable setting it to 68F. Note that the summer in Albany is hot, and the winter is COLD! Assuming that the climate control is properly functioning, what is going on here?
  58. $7.11 at 711 Kilam walks into the store 711 and buys 4 items. The cashier quotes the price to be $7.11. Curious as to how the price was the same as the store name, Kilam asks how this price was obtained. The cashier says by taking the products of the four prices. Kilam insists this is wrong and it should be the sum. The cashier says "no sweat, the price will be the same, thank you". What were the four prices?
  59. Buying Letters: Buying O N E costs $2, T W O costs $3 and E L E V E N costs $5. How much does T W E L V E cost?
  60. Remembering the Number: From the numbers 1-100, you remove any number you want. You will read out the remaining numbers in any order you wish, at the end of which I will tell you the number you left out. What strategy would you use to accomplish my task?
  61. In Tens to Hundred: Two players start with a total of 0 and alternately add an integer in {1,2,3...,10} to the total. The winner is the player to call 100. Do you want to go first or second, and how will you play?
  62. An Odd Way to Exceed 45: Two players start with a total of 0 and alternately add an integer in {1,2,3,4,5} to the total. The loser is the player to take the total above 45. The catch is that a player, on his turn, cannot add the same amount his opponent added in the previous turn. Do you want to go first or second, and how will you play?
  63. Guessing the Hat: From 3 white hats and 2 black hats, I place three hats, one on each head of three men in a line facing forward. The men can only see what is ahead of them. The last man who sees two other hats says he cannot say with certainty what color hat is on his head. Then the middle man says the same. But surprisingly now the front man who sees no other hat says I know the color of the hat on my head! What color was it?
  64. Equalizing the Piles: I take a deck of 52 playing cards and place 20 cards face up. I then shuffle the deck in any way as I wish so that 32 cards stay face down and 20 face up. I then blindfold you and give you the deck. If you can divide the deck into two piles of cards so that both piles have the same number of face up cards I will give you $100. Otherwise you must pay me $1. Do you want to take this bet?

    If instead of $1 I said if you fail you owe me $X, what is the maximum value of X for which you will take on this bet?

  65. 4 Men and a Flashlight: 4 men arrive at a bridge in the dark, with one flashlight. The flashlight is required by any group crossing the bridge, and the bridge can only hold two men at a time. The minimum times it takes for the men to walk across the bridge are 1,2,5,10 minutes respectively. What is the minimum time by which all 4 men can have crossed the bridge?
  66. Even Odds for Even Choices: I have 3 cards in a bag. One is black on both faces, one is white on both faces and one has a black and a white face. I pull one card out (randomly) and place it on the table. You see a white face, so you conclude this is either the WW card or the BW card. I bet you even odds that the other face of this card is white, if it is black you win. Do you want to take this bet?
  67. Tournament Matches: In a standard knock out tournament with 57 people, how many matches are played in total. How many byes are there. Generalize to a knockout tournament with N players.
  68. Three Odds making Even: Place 10 balls in three cups so that each cup has an odd number of balls.
  69. Bartering Links : You have a gold chain with 63 links. You would like to cut some links to obtain a set of links of different sizes. You goal is to be able to represent any number of links as a collection of some of your pieces in order to trade. What is the minimum number of links you need to cut to be able to do so? Generalize to a chain with 2^k-1 links. What about to a chain of arbitrary size n?
  70. Guessing Your Friend's Number: You and your friend are given two consecutive positive integers (at random). You look at your number and shout out your opponents number if you know it, otherwise you pass the turn to your opponent. Will this game ever stop?
  71. Maximizing the Probability: You are given 50 white marbles and 50 black marbles along with two jars. You are asked to place all 100 marbles into the jars in any way you choose. Afterwards, you will be blindfolded, the jars will be shaken and rearranged, and you will be asked to select one marble from either jar. How would you arrange the marbles originally to maximise the probability of drawing a white marble?
  72. Word Paths: Starting with WARM, change one letter at a time, each time making a valid word and end with COOL? What is the shortest such sequence?
  73. Triangle Areas: Which triangle has larger area. One whose sides are 400,500,600 or one whose sides are 400,500 700?
  74. Heaven or Hell: On the way to heaven, you come to a fork with two people. One is known to be a perpetual liar, one a perpetual truth teller. You do not know which is which, however they know. You can ask one question. What question will you ask in order to ensure that you will be able to determine the correct way to heaven.

    What if only one person (either a perpetual liar or perpetual truth teller) was standing at the fork. What question would you ask.

  75. Shrivelling Watermellons: Watermellon is 99% water. I have 100 pounds of watermellon. After a week, drying in the sun, the shrivelled watermellon had only dried down to being 98% water. What is the total weight of the watermellon now?
  76. Maximizing the Product: Write 271 as the sum of positive real numbers so as to maximize their product.
  77. Tossing Coin Sequences: Two players play the following game with a fair coin. Player 1 chooses (and announces) a triplet (HHH, HHT, HTH, HTT, THH, THT, TTH, or TTT) that might result from three successive tosses of the coin. Player 2 then chooses a different triplet. The players toss the coin until one of the two named triplets appears. The triplets may appear in any three consecutive tosses: (1st, 2nd, 3rd), (2nd, 3rd, 4th), and so on. The winner is the player whose triplet appears first.
    1. What is the optimal strategy for each player? With best play, who is most likely to win?
    2. Suppose the triplets were chosen in secret? What then would be the optimal strategy?
    3. What would be the optimal strategy against a randomly selected triplet?
  78. Only Marginally More Favorable: Player A has one more coin than player B. Both players throw all of their coins simultaneously and observe the number that come up heads. Assuming all the coins are fair, what is the probability that A obtains more heads than B?

    What about if player A has N>1 more coins than B?

  79. A Tricky Equation: Solve the equation sqrt(4 + sqrt(4 - sqrt(4 + sqrt(4 - x)))) = x.
  80. An Interesting Sum: The first 2n positive integers are arbitrarily divided into two groups of n numbers each. The numbers in the first group are sorted in ascending order: a1 < a2 < ... < an; the numbers in the second group are sorted in descending order: b1 > b2 > ... > bn.

    What is the value of the sum |a1 - b1| + |a2 - b2| + ... + |an - bn|?

  81. Irrational Trigonometry: sin(1), cos(1) and tan(1) are irrational? (all angles in degrees).
  82. Measuring With Sand-Glass: You have two sandglasses, one which measures 7 minutes and one which measures 11 minutes. How can one use them to measure 15 minutes?
  83. Coloring The Plane: The plane is divided into areas by straight infinite lines. Show that these areas can be colored using only two colors, so that any two states that share a border line, have different colors.
  84. Dividing the Children: Given a group of children, show that they can be divided into two subgroups, such that at least half of the friends of any child, are in the opposite subgroup (friendship is considered to be mutual).
  85. Tiling with an L: You have a 64x64 chess board and an unlimited tiles each containing 3 squares in the shape of an L. The top left corner of the board is removed. Can the remainder of the board be tiled with the L shaped tiles? If so how?
  86. Area Between Concentric Circles:
    Two concentric circles are as pictured. The chord in the larger one which is tangent to the smaller one has length 100. What is the area of the ring between the two circles?
  87. The Knight Tour: Consider a knight on the bottom left square of a standard 8x8 chess board. Give a tour in which the knight touches every square exactly once and ends on the top right square. (Note that the knight has already touched its starting square.) What about the ending at the top left?
  88. Determining The Number of Heavier Balls: You have 20 balls, at least one of which is normal. There are some (perhaps zero) heavier balls. can you determine the number of heavier balls using at most 11 weighings?
  89. Identifying the Weights: You have 4 weights of 2,3 5,7 pounds. Unfortunately they are not labeled. What is the smallest number of weighings in which you can identify and correctly label the weights? What about if the goal was to weigh as small a weight as possible?
  90. Integer Midpoint: You have 100 points on the plane, each point having integer coordinates. Show that there is always at least one pair for which the mid point of their connecting chord is at integer coordinates. What is the minimum number of points to guarantee this property?
  91. Divisible Subsets: You have 13 coins with integer weights. Every subset of size twelve can be divided into two disjoint subsets of size 6 with the same total weight each. All the coins should therefore be the same weight -- show this. What if the weights are rational; what about real?
  92. Packing Balls: A cube of side 10 is filled with 10 layers of 100 balls each, each ball of diameter 1. The same cube is filled in a similar way with balls of half the diameter. Which arrangement has more air in it?
  93. Dividing Coconuts: Kilam divides his wealth (dollars bills) among his 5 children as follows. He splits the bills into 5 piles and one bill remains. He buys himself an ice-cream for this dollar and gives one pile to his oldest. He splits the remaining into 5 piles, a dollar remains, which he spends and gives one pile to his 2nd oldest. In this way he continues, each time splitting the pile into 5, spending the remaining dollar and giving one pile to the next child. After each child has received a pile, the remaining bills are split into 5, one pile going to each child and one dollar remaining with the dad which is spent. No poorer man could have accomplished this feat. How wealthy was Kilam?
  94. Splitting The Proceeds: Kilam and Liamsi sell some precious stones. They received the for each stone a price equal to the total number of stones they had. They shared the proceeds as follows. First Kilam took $10, then Liamsi, and so on. Finally when Liamsi came to take his last installment, there was less than $10, which he took. Kilam feeling sorry gave Liamsi his pocketknife so that the division would be fair. How much was the pocketknife worth?
  95. Largest Integer Parts: Let [x] be the largest integer less than or equal to x, eg. [3.25]=3 and [-2.7]=-3.
    Show [x+y]&ge[x]+[y].
  96. Dividing by n!:
    • Show that the product of n consecutive positive integers is divisible by n!.
    • If a,b,c,... are positive integers with a+b+c+...&le n then n!/(a!b!c!...) is an integer.
  97. Bridge Across the River: A river has width 10 meters and two points (A,B) on either side need to be connected by a bridge which will run perpendicular to the shore. The two points are 100 meters apart along the river; A is 100 meters
  98. Finding a Divisor: From the first 100 natural numbers find 50 such that none of them divides another. Can you find 51?
  99. Hat on the River: You have a constant paddling speed of 10 miles/hour and the diver flows at 2 miles per hour. You are paddling upstream, and drop your hat in the water. The hat has traveled 5 miles from you when you realize this, and immediately turn around and paddle the other way to fetch it. For how long have you been separated from your hat?
  100. Dividing by 100: Of 52 positive integers, at least one pair has a sum or difference which is divisible by 100.
Games:

  1. (Nim) This is a game for 2 players. There are three stacks of coins. The players take it in turns to remove some number of coins (greater than zero) from only one of the stacks (the whole stack could be removed). The winner is the player who removes the last coin.
    • The stacks contain 19,8, and 22 coins. Do you want to play first and if so, what is your move and why? If not, what is your strategy?
    • the stacks contain 19,7, and 22 coins. Do you want to play first and if so, what is your move and why? If not, what is your strategy?
    Can you generalize to N stacks. With three stacks, the game is called NIM.
  2. This is a two player game. 50 coins are arranged in a line (each of different, arbitrary, denominations). A player may pick a coin from one or other end. Players alternate until there are no more coins left. The loser has the smaller amount of money. Can the first player always guarantee herself not to be the loser? Is there an efficient algorithm to compute the optimal strategy?
  3. Place (say) 20 red points and 20 blue points on a plane piece of paper. No three should be on a line. Two players, the red player and the blue player take turns connecting a pair of points of their color with a straight line so that no lines intersect. The loser is the first player who has to draw a line that intersects an existing line. For any arrangement of the points is it always possible to place the n red lines and blue lines so that no two lines intersect.
  4. Sam Lloyd's matrimony game: Two players alternately pick integers in the range 1-5, and add it to a running total which is initially zero. The constraint is that a player cannot pick the same integer that was picked by her opponent on the previous turn. The loser is the player who picks the integer that takes the running total above 45. Do you wish to go first or second, and what is your strategy?
  5. A game is to be played on a circular table. Quarters are to be placed non overlappingly on the table. You alternate turns with your opponent. The last person to place a quarter on the table wins. Do you want to start or go second?
Bridge: 

  1. Bidding:

W    N    E    S
--   --   --   1D         *majors
2D*  2H#  3H   3NT        #heart stopper, diamond support, good hand        
4H   X    --   5D  

Opening Lead HQ: Plan the Play.



                            NORTH: 
                             86
			     AK6
			     Q97
			     AT984


			    SOUTH:
	                     K74
			     5
			     AKJT86
			     J76
  2. For the moment this is a double dummy problem. It is not mine and was in fact posed by two famous Hungarians. 
    
                             973
			     973
			     A973
			     973



          A86542	                           QJT
	  T864                                     2
	  2                                        JT82
	  J2				           Q8654


	                     K
			     AKQJ5
			     KQ65
			     AKT
    South is declaring in 6H. West to lead. What do you lead? What leads allow South to make the contract-and how? What leads set the contract-and why? 
  3. 
                             AKQJ2
			     -
			     A
			     8765432



          -	                                   T87654
	  T8542                                    9763
	  J64                                      532
	  KQJT9				           -


	                     93
			     AKQJ
			     KQT987
			     A
    South is declaring 6NT and the lead is the Club K.
Technical:

Here are a small collection of technical puzzles that I find interesting. The answers to some of them may elude me from time to time. Their appeal to me lies in the fact that one can spend MANY hours on them and get nowhere. Sometimes the solution is elegent and sometimes ugly, so as Erdos would say, if you have a "book" proof for some of these problems, please do tell. -MMI
  1. A Trig Inequality: Cos(Sin x) > Sin(Cos x)
  2. The Monotonic Subsequence: Consider any permutaiton of {1,2,...n^2+1}. There must exist a monotonic sub-sequence of size at least n+1.
  3. Condensing the Gaussian: Let X be a Gaussian random variable with mean 0 and variance 1. You can transmit its value to a friend, using one of 2 numbers that have to be predetermined (before seeing X). When the friend receives the transmission, she will assume that the transmitted value is the actual value of X. What two numbers will you choose so that the expected squared error incurred by the friend is minimized. Prove that your solution cannot be beaten.
  4. A Probability Problem: Let X and Y be two independent identically distributed real random variables. Show that

    P[|X-Y|<=2]<= 3 P[|X-Y|<=1]

    I have managed to show P[|X-Y|<=2]<= 5 P[|X-Y|<=1], but the factor of 3 seems to have eluded me. This is problem number 2 in chapter 2 of the text "The Probabilistic Method" by N. Alon and J. H. Spencer, Wiley, 2000.

  5. Integer Representations: Here are some interesting ways to write some well known integers.
    \begin{displaymath} 1=\sqrt[3]{\frac{13\sqrt{3}}{36}+\frac{5}{8}}- \sqrt[3]{\fra... ...}{8}} \qquad 2=\sqrt[3]{6\sqrt{3}+10}- \sqrt[3]{6\sqrt{3}-10} \end{displaymath}

    More generally, for arbitrary c
    \begin{displaymath} 1=\sqrt[3]{\frac{1}{8}+\frac{c^2}{2}+\frac{c(4c^2+9)\sqrt{3}... ...qrt[3]{\frac{1}{8}+\frac{c^2}{2}-\frac{c(4c^2+9)\sqrt{3}}{36}} \end{displaymath}

  6. Divisors:
    • How many numbers less than 1000 are not divisible by 3 or 5 or 7? Generalize.
    • How many divisors does 9112001 have (including 1 and 9112001) and what is the sum of all these divisors?
  7. Co-Prime Probability: Given two positive numbers, what is the probability that they are relatively prime? (Assume a uniform distribution) Generalize to K numbers.
  8. A Line Through 2 Points: Given any set of greater than 2 points on the plane, not all on a line, there is at least one line that passes through exactly two points.
  9. Matching the Hats: 100 coats are randomly distributed to 100 owners. What is the probability that at least one owner gets his own coat?
  10. Betting the Deck: A deck has 26 red and black cards. A red card rewards you $1, and a black card fines you $1. You draw cards one by one, and may stop whenever you wish. What is your optimal strategy?
  11. : Let U be a perfect uniform random real number generator for the interval [0,1]. Suppose we independently sample N times from U. What is the probability that that at least one of the samples is a rational number. Clearly for any finite N, this probability must be zero. So the question is as follows. Let 0 < p < 1 be any fixed probability. Let N(p) be the "smallest" N such that if N samples are drawn, then the probability that at least one is rational is p.

    What is N(p) as a function of p?

    Here is a naive computer scientists argument that the answer to this question depends on the continuum hypothesis. Let a0 be aleph 0 and a1 be aleph 1. Treating a0 and a1 as algebraic quantities, suppose that a0 samples are drawn, then the probability that at least one is rational is

    1-(1-a0/a1)^(a0) - > 1-((1-a0/a1)^(a1/a0))^(a0^2/a1).

    Now suppose that a1 samples are drawn, then the probability that at least one is rational is

    1-(1-a0/a1)^(a1) - > 1-((1-a0/a1)^(a1/a0))^(a0).

    Since a0/a1 - > 0 lets postulate that (1-a0/a1)^(a1/a0) - > 1/e. Since a0^2/a1=0, the top expression is 0 and the bottom expression is 1. Thus, if N < = aleph 0 then p=0; if N > = aleph 1 then p=1. The only way to obtain 0 < p < 1 is if there is some cardinality between aleph 0 and aleph 1, i.e. the continuum hypothesis.

    So can someone put some beef into my argument or are my heuristics just plain false?

  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 get my solutions or 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!