Average
clan sizeColored
balls in boxesMixed
up airplane seats
Here are some mathematical puzzles that I have enjoyed. Most of them are of the kind that you can discuss and solve at a dinner table.
Average
clan sizeColored
balls in boxesMixed
up airplane seats[I got this problem from Ernie Cohen, who I think had made it up. Itay Neeman suggested the use of "clans" instead of Ernie's original "families", because "clans" has a stronger connotation of the groups being disjoint.]
The people in a country are partitioned into clans. In order to estimate the average size of a clan, a survey is conducted where 1000 randomly selected people are asked to state the size of the clan to which they belong. How does one compute an estimate average clan size from the data collected?
[I got this little problem from Leonardo de Moura.]
There are three boxes, one containing two black balls, another containing two white balls, and another containing one black and one white ball. You select a random ball from a random box and you find you selected a white ball. What is the probability that the other ball in the same box is also white?
[I got this problem from Rajeev Joshi, who I think said he heard it from Jay Misra.]
An airplane has 50 seats, and its 50 passengers have their own assigned seats. The first person to enter the plane ignores his seat assignment and instead picks a seat on random. Each subsequent person to enter the plane takes her assigned seat, if available, and otherwise chooses a seat on random. What is the probability that the last passenger gets to sit in her assigned seat?
[Carroll Morgan told me this puzzle.]
Prove that for any positive K, every Kth number in the Fibonacci sequence is a multiple of the Kth number in the Fibonacci sequence.
More formally, for any natural number n, let F(n) denote Fibonacci number n. That is, F(0) = 0, F(1) = 1, and F(n+2) = F(n+1) + F(n). Prove that for any positive K and natural n, F(n*K) is a multiple of F(K).
[Rajeev Joshi told me this problem. He got it from Jay Misra.]
Consider a game that you play against an opponent. In front of you are an even number of coins of possibly different denominations. The coins are arranged in a line. You and your opponent take turns selecting coins. Each player takes one coin per turn and must take it from an end of the line, that is, the current leftmost coin or the current rightmost coin. When all coins have been removed, add the value of the coins collected by each player. It is possible that you and your opponent end up with the same value (for example, if all coins have the same denomination). Develop a strategy where you take the first turn and where your final value is at least that of your opponent (that is, don't let your opponent end up with coins worth more than your coins).
[This problem was told to me by Clark Barrett. It may sound reminiscent of the Three hat colors problem, but it's different in many ways.]
N people team up and decide on a strategy for playing this game. Then they walk into a room. On entry to the room, each person is given a hat on which one of the first N natural numbers is written. There may be duplicate hat numbers. For example, for N=3, the 3 team members may get hats labeled 2, 0, 2. Each person can see the numbers written on the others' hats, but does not know the number written on his own hat. Every person then simultaneously guesses the number of his own hat. What strategy can the team follow to make sure that at least one person on the team guesses his hat number correctly?
100 coins are to be distributed among some number of persons, referred to by the labels A, B, C, D, .... The distribution works as follows. The person with the alphabetically highest label (for example, among 5 people, E) is called the chief. The chief gets to propose a distribution of the coins among the persons (for example, chief E may propose that everyone get 20 coins, or he may propose that he get 100 coins and the others get 0 coins). Everyone (including the chief) gets to vote yes/no on the proposed distribution. If the majority vote is yes, then that’s the final distribution. If there’s a tie (which there could be if the number of persons is even), then the chief gets to break the tie. If the majority vote is no, then the chief gets 0 coins and has to leave the game, the person with the alphabetically next-highest name becomes the new chief, and the process to distribute the 100 coins is repeated among the persons that remain. Suppose there are 5 persons and that every person wants to maximize the number of coins that are distributed to them. Then, what distribution should chief E propose?
[This problem and its solution caused my niece Sarah Brown to send me the following article from The Economist, which considers a human aspect of situations like these.]
Each of two players picks a different sequence of two coin tosses. That is, each player gets to pick among HH, HT, TH, and TT. Then, a coin is flipped repeatedly and the first player to see his sequence appear wins. For example, if one player picks HH, the other picks TT, and the coin produces a sequence that starts H, T, H, T, T, then the player who picked TT wins. The coin is biased, with H having a 2/3 probability and T having a 1/3 probability. If you played this game, would you want to pick your sequence first or second?
A room has 100 light switches, numbered by the positive integers 1 through 100. There are also 100 children, numbered by the positive integers 1 through 100. Initially, the switches are all off. Each child k enters the room and changes the position of every light switch n such that n is a multiple of k. That is, child 1 changes all the switches, child 2 changes switches 2, 4, 6, 8, …, child 3 changes switches 3, 6, 9, 12, …, etc., and child 100 changes only light switch 100. When all the children have gone through the room, how many of the light switches are on?
[Ernie Cohen sent me this puzzle, and I also heard it from a student who got it from Ernie at Marktoberdorf.]
You have 12 coins, 11 of which are the same weight and one counterfeit coin which has a different weight from the others. You have a balance that in each weighing tells you whether the two sides are of equal weight, or which side weighs more. How many weighings do you need to determine: which is the counterfeit coin, and whether it weighs more or less than the other coins. How?
[I got this problem many years ago, likely from Jan van de Snepscheut.]
You're given a 3x3x3 cube of cheese and a knife. How many straight cuts with the knife do you need in order to divide the cheese up into 27 1x1x1 cubes?
[I got this question from Sergei Vorobyov.]
The games played in the soccer world championship form a binary tree, where only the winner of each game moves up the tree (ignoring the initial games, where the teams are placed into groups of 4, 2 of which of which go onto play in the tree of games I just described). Assuming that the teams can be totally ordered in terms of how good they are, the winner of the championship will indeed be the best of all of the teams. However, the second best team does not necessarily get a second place in the championship. How many additional games need to be played in order to determine the second best team?
[I must have heard this problem ages ago, but as I remembered it, one was always satisfied after finding just one solution. It was a math professor at the Kaiserslautern Technical University who brought asking for all solutions to my attention.]
Initially, you're somewhere on the surface of the Earth. You travel one kilometer South, then one kilometer East, then one kilometer North. You then find yourself back at the initial position. Describe all initial locations from which this is possible.
[I heard this nice problem from Sumit Gulwani.]
You're given a procedure that with a uniform probability distribution outputs random numbers between 0 and 1 (to some sufficiently high degree of precision, with which we need not concern ourselves in this puzzle). Using a bounded number of calls to this procedure, construct a procedure that with a uniform probability distribution outputs a random point within the unit circle.
[I read this problem in a puzzle book I have.]
You have two jars. One contains vinegar, the other oil. The two jars contain the same amount of their respective fluid.
Take a spoonful of the vinegar and transfer it to the jar of oil. Then, take a spoonful of liquid from the oil jar and transfer it to the vinegar jar. Stir. Now, how does the dilution of vinegar in the vinegar jar compare to the dilution of oil in the oil jar?
[I got this problem from Carroll Morgan.]
A building has 16 rooms, arranged in a 4x4 grid. There is a door between every pair of adjacent rooms ("adjacent" meaning north, south, west, and east, but no diagonals). Only the room in the northeast corner has a door that leads out of the building.
In the initial configuration, there is one person in each room. The person in the southwest corner is a psycho killer. The psycho killer has the following traits: If he enters a room where there is another person, he immediately kills that person . But he also cannot stand the site of blood, so he will not enter any room where there is a dead person.
As it happened, from that initial configuration, the psycho killer managed to get out of the building after killing all the other 15 people. What path did he take?
[Chuck Chan created this little puzzle. Greg Nelson suggested introducing the name "squarish" in order to simplify the problem statement.]
Let's say that a number is squarish if it is the product of two consecutive
numbers. For example, 6 is squarish, because it is 2*3.
A friend of mine at Microsoft recently had a birthday. He said his age is now squarish. Moreover, since the previous time his age was a squarish number, a
squarish number of years has passed. How many years would he have to wait until
his age would have this property again?
[This problem appears as a sample question on the web page for the Putnam exam.]
A game is played as follows. N people are sitting around a table, each with
one penny. One person begins the game, takes one of his pennies (at this
time, he happens to have exactly one penny) and passes it to the person to his
left. That second person then takes two pennies and passes them to the
next person on the left. The third person passes one penny, the fourth
passes two, and so on, alternating passing one and two pennies to the next
person. Whenever a person runs out of pennies, he is out of the game and has to
leave the table. The game then continues with the remaining people.
A game is terminating if and only if it ends with just one person sitting
at the table (holding all N pennies). Show that there exists an infinite
set of numbers for which the game is terminating.
[I heard this problem from Bertrand Meyer, who had heard it was once given on the Putnam exam.]
At some point during a baseball season, a player has a batting average of less than 80%. Later during the season, his average exceeds 80%. Prove that at some point, his batting average was exactly 80%.
Also, for which numbers other than 80% does this property hold?
[I got this problem from Jay Misra, who got it from Gerard Huet.]
For any even number N, partition the integers from 1 to N into pairs such that the sum of the two numbers in each pair is a prime number.
Hint: Chebyshev proved that the following property (Bertrand's Postulate) holds: for any k > 1, there exists a prime number p in the range k < p < 2*k.
[Madan Musuvathi asked me this question.]
Find two positive integers that together with 23 are the lengths of a right triangle.
[Madan first told me 17, which I could solve right away, because I had just finished reading Mark Haddon's novel "The curious incident of the dog in the night-time", which toward the end mentions that a triangle with sides n2+1, n2-1, and 2*n, where n>1, is a right triangle. Madan then asked me about 23.]
[A follow-up question.]
There's a simple technique that, given any odd positive integer, allows you to figure out the other two integer sides of a right triangle in your head (or with pen and paper if the numbers get too large). Find this technique.
Hint: Think of every number as a multiset of prime factors, so that multiplying the prime factors gives you the number. Move one of the addends of the Pythagorean Theorem to the other side and factor it (a technique I recently learned from Raymond Boute).
[Jay Misra told me this problem.]
A rubber band (well, a rubber string, really) is 10 meters long. There's a worm that starts at one end and crawls toward the other end, at a speed of 1 meter per hour. After each hour that passes, the rubber string is stretched so as to become 1 meter longer than it just was. Will the worm ever reach the other end of the string?
[I got this problem from Amit Rao.]
Two players are playing a game. The game board is a circular table. The players have access to an ample supply of equal-sized circular coins. The players alternate turns, with each turn adding a single coin to the table. The coins are not allowed to overlap. Once a coin is placed on the table, it is not allowed to be moved. The player who has no place to put his next coin loses. Develop a winning strategy for the player who starts. (The table is large enough to accommodate at least one coin.)
[I got this problem from Olean Brown, who had pointed me to the following web page that claims to read your mind.]
Think of a positive integer, call it X. Shuffle the decimal digits of X, call the resulting number Y. Subtract the smaller of X,Y from the larger, call the difference D. D has the following property: Any non-zero decimal digit of D can be determined from the remaining digits. That is, if you ask someone to hide any one of the non-zero digits in the decimal representation of D, then you can try to impress the other person by figuring out the hidden digit from the remaining digits. How is this done? Why does it work?
[I got this problem from Todd Proebsting.]
Boris and Natasha live in different cities in a country with a corrupt postal service. Every box sent by mail is opened by the postal service, the contents stolen, and the box never delivered. Except: if the box is locked, then the postal service won't bother trying to open it (since there are so many other boxes whose contents are so much easier to steal) and the box is delivered unharmed.
Boris and Natasha each has a large supply of boxes of different sizes, each capable of being locked by padlocks. Also, Boris and Natasha each has a large supply of padlocks with matching keys. The padlocks have unique keys. Finally, Boris has a ring that he would like to send to Natasha. How can Boris send the ring to Natasha so that she can wear it (without either of them destroying any locks or boxes)?
[I first got this problem from Ernie Cohen. Apparently, it has appeared as a Car Talk Puzzler, but I've been unable to find it on their web site.]
Warm-up: You are given a box of matches and a piece of rope. The rope burns at the rate of one rope per hour, but it may not burn uniformly. For example, if you light the rope at one end, it will take exactly 60 minutes before the entire rope has burnt up, but it may be that the first 1/10 of the rope takes 50 minutes to burn and that the remaining 9/10 of the rope takes only 10 minutes to burn. How can you measure a period of exactly 30 minutes? You can choose the starting time. More precisely, given the matches and the rope, you are to say the words "start" and "done" exactly 30 minutes apart.
The actual problem: Given a box of matches and two such ropes, not necessarily identical, measure a period of 15 minutes.
[I have heard several versions of this problem. I first heard it from Bertrand Meyer, who got the problem from Yuri Gurevich.]
You're given a regular deck of 52 playing cards. In the pile you're given, 13 cards face up and the rest face down. You are to separate the given cards into two piles, such that the number of face-up cards in each pile is the same. In separating the cards, you're allowed to flip cards over. The catch: you have to do this in a dark room where you cannot determine whether a card is face up or face down.
[I think I got this puzzle from Lyle Ramshaw, who I think got it from some collection of problems or maybe the American Mathematical Monthly.]
A team of three people decide on a strategy for playing the following game. Each player walks into a room. On the way in, a fair coin is tossed for each player, deciding that player's hat color, either red or blue. Each player can see the hat colors of the other two players, but cannot see her own hat color. After inspecting each other's hat colors, each player decides on a response, one of: "I have a red hat", "I had a blue hat", or "I pass". The responses are recorded, but the responses are not shared until every player has recorded her response. The team wins if at least one player responds with a color and every color response correctly describes the hat color of the player making the response. In other words, the team loses if either everyone responds with "I pass" or someone responds with a color that is different from her hat color.
What strategy should one use to maximize the team's expected chance of winning?
For example, one possible strategy is to single out one of the three players. This player will respond "I have a red hat" and the others will respond "I pass". The expected chance of winning with this strategy is 50%. Can you do better? Provide a better strategy or prove that no better strategy exists.
[Here's a related problem, which I got from Jim Saxe.]
In this variation, the responses are different. Instead of "red", "blue", "pass", a response is now an integer, indicating a bet on having the hat color red. Once the responses have been collected, the team's score is calculated as follows: Add the integer responses for those players wearing red hats, and subtract from that the integers of those players wearing blue hats. For example, if the three players respond with 12, -2, -100 while wearing blue, red, blue, respectively, then the team's score is (-2) - (12) - (-100) = 90. The team wins if and only if its score is strictly positive.
For example, any strategy used in the first game can be used with this second game by replacing "I have a red hat" with 1, "I have a blue hat" with -1, and "I pass with 0". Such a strategy wins anytime the strategy would have produced a win in the first game; plus, this strategy may win in some cases where the strategy would not produce a win in the first game. For example, for hat colors red, red, red, the strategy "red", "red", "blue" loses in the first game, whereas 1, 1, -1 still wins in the second game. Hence, playing this second game can only increase the team's expected chance of winning.
[Further generalizations.]
Of course, you can generalize these two problems from 3 players to N players. The solution to the first problem with N players may require more mathematical sophistication than the solution to the second problem with N players.
[Ernie Cohen told me this problem.]
100 persons are standing in line, each facing the same way. Each person is wearing a hat, either red or blue, but the hat color is not known to the person wearing the hat. In fact, a person knows the hat color only of those persons standing ahead of him in line.
Starting from the back of the line (that is, with the person who can see the hat colors of all of other 99 persons), in order, and ending with the person at the head of the line (that is, with the person who can see the hat color of no one), each person exclaims either "red" or "blue". These exclamations can be heard by all. Once everyone has spoken, a score is calculated, equal to the number of persons whose exclamation accurately describes their own hat color.
What strategy should the 100 persons use in order to get as high a score as possible, regardless of how the hat colors are assigned? (That is, what strategy achieves the best worst-case score?)
For example, if everyone exclaims "red", the worst-case score is 0. If the first 99 persons exclaim the color of the hat of the person at the head of the line and the person at the head of the line then exclaims the color he has heard, the worst-case score is 1. If every other person exclaims the hat color of the person immediate in front and that person then repeats the color he has just heard, then the worst-case score is 50. Can you do better?
[Here's a generalization of the problem.]
Instead of using just red and blue as the possible hat colors and exclamations, use N different colors.
[Tom Ball told me (a close variation of) this problem. The problem has been featured as a Car Talk Puzzler under the name Prison Switcharoo (beware: the Car Talk problem page also contains an answer).]
N prisoners get together to decide on a strategy. Then, each prisoner is taken to his own isolated cell. A prison guard goes to a cell and takes its prisoner to a room where there is a switch. The switch can either be up or down. The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch. The prisoner is then taken back to his cell. The prison guard repeats this process infinitely often, each time choosing fairly among the prisoners. That is, the prison guard will choose each prisoner infinitely often.
At any time, any prisoner can exclaim "Now, every prisoner has been in the room with the switch". If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed. What strategy should the prisoners use to ensure their eventual freedom?
(Just in case there's any confusion: The initial state of the switch is unknown to the prisoners. The state of the switch is changed only by the prisoners.)
As a warm-up, you may consider the same problem but with a known initial state of the switch.
[This problem has crossed the desk of Jan van de Snepscheut, but it may have been due to someone else.]
A square table has a coin at each corner. Design an execution sequence, each of whose steps consists of one of the following operations:
such that at some point during the execution (not necessarily at the end), a state where all coins are turned the same way (all heads or all tails) obtains.
[I got this problem from Jay Misra, who had received it from Edsger Dijkstra. This particular description of the problem borrows from a description given by Michael Jackson.]
In a finite, undirected, connected graph, an integer variable v(n) is associated with each node n. One node is distinguished as the anchor. An operation OP(n) is defined on nodes:
OP(n):
if node n is the anchor, then do nothing,
else set v(n) to the value 1 + min{v(m)}, where m ranges over all neighbors of n that are distinct from n.
An infinite sequence of operations <OP(n),OP(m), ...> is executed, the node arguments n, m, ... for the operations being chosen arbitrarily and not necessarily fairly. Show that eventually all v(n) stabilize. That is, that after some finite prefix of the infinite sequence of operations, no further operation changes v(n) for any node n.
[This problem was told to me by Dave Detlefs, who got it from the following impressive collection of math problems.]
Given N points randomly distributed around the circumference of a circle, what is the probability that all N points lie on the same semi-circle?
[I learned about this problem from Greg Nelson, who phrased the problem in terms of a tall building and elevator rides. Here, I instead say a mountain and helicopter rides, which is the way Lyle Ramshaw had heard the problem and which more forcefully emphasizes the price of each ride. As a computer scientist, I like this problem a lot, because of the variety of solutions of different computational complexities.]
You're an electrician working at a mountain. There are N wires
running from one side of the mountain to the other. The problem is that
the wires are not labeled, so you just see N wire ends on each side of
the mountain. Your job is to match these ends (say, by labeling the two
ends of each
wire in the same way).
In order to figure out the matching, you can twist together wire ends, thus
electrically connecting the wires. You can twist as many wire ends as you
want, into as many clusters as you want, at the side of the mountain where you
happen to be at the time. You can also untwist the wire ends at the side
of the mountain where you're at. You are equipped with an Ohm meter, which
lets you test the connectivity of any pair of wires. (Actually, it's an
abstract Ohm meter, in that it only tells you whether or not two things are
connected, not the exact resistance.)
You are not charged [no pun intended] for twisting, untwisting, and using the
Ohm meter. You are only charged for each helicopter ride you make from one
side of the mountain to the other. What is the best way to match the
wires? (Oh, N>2, for there is no solution when N=2.)
[I learned about this problem from Lyle Ramshaw. See also puzzles 19 and 20 on the following large collection of mathematical puzzles.]
In this problem, you and a partner are to come up with a scheme for communicating the value of a hidden card. The game is played as follows:
Question: What is the foolproof scheme that you and your partner settled on ahead of time?
As a follow-up question, consider the same problem but with a 124-card deck.
[Communicated to me by Carroll Morgan.]
A king has a daughter and wants to choose the man she will marry. There are three suitors from whom to choose, a Knight, a Knave, and a Commoner. The king wants to avoid choosing the Commoner as the bridegroom, but he does not know which man is which. All the king knows is that the Knight always speaks the truth, the Knave always lies, and the Commoner can do either. The king will ask each man one yes/no question, and will then choose who gets to marry the princess. What question should the king ask and how should he choose the bridegroom?
[A follow-up question posed by Lyle Ramshaw.]
Suppose the three suitors know each other (an assumption that's not needed in the original problem). Then find a new strategy for the king where the king only needs to ask a question of any two of the three suitors in order to pick the bridegroom.
[Another variation of the problem.]
Find a strategy for the king where the king can ask questions of only one suitor, but can ask two questions of that suitor.
[And another (at first sight incredible) follow-up question communicated to me by both Jim Saxe and Pierre Nallet.]
Find a strategy for the king where the king can ask only one yes/no question and only of one suitor.