leino.science
© 2020-2024, K.R.M. Leino
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, usually without pen and paper. So as not to spoil your fun, no solutions are given on this page, but for some problems I have provided some hints.
I got this problem from Johannes Kinder, who said he heard it from his brother. I reformulated the setting.
A particular basketball shootout game consists of a number of duels. In each duel, one player is the challenger. The challenger chooses another player to challenge, and then gets one chance to shoot the hoop. If the player makes the shot, the playing being challenged is out. If the player does not make the shot, or if the player chooses to skip his turn, then the game continues with the next duel. A player wins when only that player remains.
One day, this game is played by three players: A, B, and C. Their skill levels vary considerably: player A makes every shot, player B has a 50% chance of making a shot, and player C has a 30% chance of making a shot. Because of the difference in skill levels, they decide to let C begin, then B, then A, and so on (skipping any player who is out of the game) until there is a winner. If everyone plays to win, what strategy should each player follow?
For this follow-up question, it will be helpful to have a paper and pen--not because the calculations are hard, but because it helps in remembering the numbers.
If A, B, and C follow their winning strategies (as determined above), which player has the highest chance of winning the game?
Howard Lederer sent me this problem.
You’re on a government ship, looking for a pirate ship. You know that the pirate ship travels at a constant speed, and you know what that speed is. Your ship can travel twice as fast as the pirate ship. Moreover, you know that the pirate ship travels along a straight line, but you don’t know what that line is. It’s very foggy, so foggy that you see nothing. But then! All of a sudden, and for just an instant, the fog clears enough to let you determine the exact position of the pirate ship. Then, the fog closes in again and you remain (forever) in the thick fog. Although you were able to determine the position of the pirate ship during that fog-free moment, you were not able to determine its direction. How will you navigate your government ship so that you will capture the pirate ship?
I got this problem from the book In code: a mathematical journey by Sarah Flannery and David Flannery.
A (presumed smart) insurance agent knocks on a door and a (presumed smart) woman opens. He introduces himself and asks if she has any children. She answers: 3. When he then asks their ages (which for this problem we abstract to integers), she hesitates. Then she decides to give him some information about their ages, saying "the product of their ages is 36". He asks for more information and she gives in, saying "the sum of their ages is equal to our neighbors’ house number". The man jumps over the fence, inspects the house number, and the returns. "You need to give me another hint", he begs. "Alright", she says, "my oldest child plays the piano". What are the ages of the children?
I think I’ve heard some version of this problem before, but heard this one from Sophia Drossopoulou and Alex Summers.
There’s a certain kind of egg about which you wonder: What is the highest floor of a 36-story building from which you can drop an egg without it breaking? All eggs of this kind are identical, so you can conduct experiments. Unfortunately, you only have 2 eggs. Fortunately, if an egg survives a drop without breaking, it is as good as new–that is, you can then conduct another dropping experiment with it. What is the smallest number of drops that is sure to determine the answer to your wonderings?
Claude Marché told me this puzzle. At first, it seems quite similar to "Catching a spy" (below), but the solution is entirely unrelated.
There are five holes arranged in a line. A hermit hides in one of them. Each night, the hermit moves to a different hole, either the neighboring hole on the left or the neighboring hole on the right. Once a day, you get to inspect one hole of your choice. How do you make sure you eventually find the hermit?
This problem was inspired by some basic probability questions mentioned in a lecture by Eric Hehner (and that can be formalized and solved by calculation using this Probability Perspective), and some subsequent discussions with him, Itay Neeman, Jim Woodcook, Ana Cavalcanti, and Leo Freitas.
The house next door has some new neighbors. They have two children, but you don’t know what mix of boys and girls they are. One day, your wife tells you "At least one of the children is a girl". What is the probability that both are girls?
Your wife then tells you "The way I found out that at least one of the children is a girl is that I saw one of the children playing outside, and it was a girl". Now, what is the probability that both are girls?
I got this problem from Koen Claessen.
A duck is in circular pond. The duck wants to swim ashore, because it wants to fly off and this particular duck is not able to start flying from the water. There is also a fox, on the shore. The fox wants to eat the duck, but this particular fox cannot swim, so it can only hope to catch the duck when the duck reaches the shore. The fox can run 4 times faster than the duck can swim. Is there always a way for the duck to escape?
I got this puzzle from Raphael Reischuk, who also has a little puzzle collection.
You and a friend each have a fair coin. You can decide on a strategy and then play the following game, without any further communication with each other. You flip your coin and then write down a guess as to what your friend’s coin will say. Meanwhile, your friend flips her coin and writes down a guess as to what your coin says. There’s a third person involved: The third person collects your guesses and inspects your coins. If both you and your friend correctly guessed each other’s coins, then your team (you and your friend) receive 2 Euros from the third person. But if either you or your friend (or both) gets the guess wrong, then your team has to pay 1 Euro to the third person. This procedure is repeated all day. Assuming your object is to win money, are you happy to be on your team or would you rather trade places with the third person?
I got this puzzle from Dave Detlefs, who read it in an MIT Alumni magazine. This puzzle is a bit more involved than most puzzles on my page, so you may want a paper and pen (and some tenacity) for this one. Once you get into it, though, it’s a hard puzzle to put aside until you’ve solved it.
There are two kinds of coins, genuine and counterfeit. A genuine coin weighs X grams and a counterfeit coin weighs X+delta grams, where X is a positive integer and delta is a non-zero real number strictly between -5 and +5. You are presented with 13 piles of 4 coins each. All of the coins are genuine, except for one pile, in which all 4 coins are counterfeit. You are given a precise scale (say, a digital scale capable of displaying any real number). You are to determine three things: X, delta, and which pile contains the counterfeit coins. But you’re only allowed to use the scale twice!
I got this one from Madan Musuvathi.
Some multiples of 11 have an even digit sum. For example, 7 * 11 = 77 and 7 + 7 = 14, which is even; 11 * 11 = 121 and 1 + 2 + 1 = 4, which is even. Do all multiples of 11 have an even digit sum? (Prove that they do or find the smallest that does not.)
Clark Barrett told me this problem.
Given is a (possibly enormous) rectangular chocolate bar, divided into small squares in the usual way. The chocolate holds a high quality standard, except for the square in the lower left-hand corner, which is poisonous. Two players take turns eating from the chocolate in the following manner: The player whose turn it is points to any one of the remaining squares, and then eats the selected square and all squares positioned above the selected square, to the right of the selected square, or both above and to the right of the selected square. Note, although the board starts off rectangular, it may take on non-rectangular shapes during game play. The object of the game is to avoid the poisonous square. Assuming the initial chocolate bar is larger than 1x1, prove that the player who starts has a winning strategy.
Hint: To my knowledge, no efficient strategy for winning the game is known. That is, to decide on the best next move, a player may need to consider all possible continuations of the game. Thus, you probably want to find a non-constructive proof. That is, to prove that the player who starts has a winning strategy, prove just the existence of such a strategy; in particular, steer away from proofs that would construct a winning strategy for the initial player.
I received this puzzle from Vladislav Shcherbina, but I changed gloves into T-shirts to emphasize the people rather than the spaces between them.
Ten friends walk into a room where each one of them receives a hat. On each hat is written a real number; no two hats have the same number. Each person can see the numbers written on his friends’ hats, but cannot see his own. The friends then go into individual rooms where they are each given the choice between a white T-shirt and a black T-shirt. Wearing the respective T-shirts they selected, the friends gather again and are lined up in the order of their hat numbers. The desired property is that the T-shirts colors now alternate.
The friends are allowed to decide on a strategy before walking into the room with the hats, but they are not otherwise allowed to communicate with each other (except that they can see each other’s hat numbers). Design a strategy that lets the friends always end up with alternating T-shirt colors.
This is a slight rewording of a problem I got from Phil Wadler, who said he read the problem on xkcd.
A man has a medical condition that requires him to take two kinds of pills, call them A and B. The man must take exactly one A pill and exactly one B pill each day, or he will die. The pills are taken by first dissolving them in water.
The man has a jar of A pills and a jar of B pills. One day, as he is about to take his pills, he takes out one A pill from the A jar and puts it in a glass of water. Then he accidentally takes out two B pills from the B jar and puts them in the water. Now, he is in the situation of having a glass of water with three dissolved pills, one A pill and two B pills. Unfortunately, the pills are very expensive, so the thought of throwing out the water with the 3 pills and starting over is out of the question. How should the man proceed in order to get the right quantity of A and B while not wasting any pills?
I got this puzzle from Jason Koenig.
You are given an irreflexive symmetric (but not necessarily transitive) "enemies" relation on a set of people. In other words, if person A is an enemy of a person B, then B is also an enemy of A. How can you divide up the people into two houses in such a way that every person has at least as many enemies in the other house as in their own house?
Hint: As Radu Grigore pointed out to me, solving the [Planar configuration of straight connecting lines](/puzzles/#Planar-configuration-of-straight-connecting-lines) puzzle may provide a hint to solving this puzzle.
A puzzle Aistis Simaitis gave me inspired this puzzle.
In a room are three boxes that on the outside look identical. One of the boxes contains a car, one contains a key, and one contains nothing. You and a partner get to decide amongst yourselves to each point to two boxes. When you have made your decision, the boxes are opened and their contents revealed. If one of the boxes your partner is pointing to contains the car and one of the boxes you are pointing to contains the key, then you will both win. What strategy maximizes the probability of winning, and what is the probability that you will win?
Rupak Majumdar told me this intriguing puzzle.
You have 3000 bananas that you want to transport a distance of 1000 km. The transport will be done by a monkey. The monkey can carry as many as 1000 bananas at any one time. With each kilometer traveled (forward or backward), the money consumes 1 banana. How many bananas can you get across to the other side?
I got this puzzle from Serdar Tasiran.
You are given one 44-meter piece of fence and 48 one-meter pieces of fence. Assume each piece is a straight and unbendable. What is the large area of (flat) land that you can enclose using these fence pieces?
Michael Jackson told me this problem, as a variation of a problem he got from Koen Claessen.
A park contains paths that intersect at various places. The intersections all have the properties that they are 3-way intersections and that, with one exception, they are indistinguishable from each other. The one exception is an intersection where there is a restaurant. The restaurant is reachable from everywhere in the park. Your task is to find your way to the restaurant.
The park has strict littering regulations, so you are not allowed to modify the paths or intersections (for example, you are not allowed to leave a note an intersection saying you have been there). However, you are allowed to do some bookkeeping on a pad of paper that you bring with you at all times (in the computer-science parlance, you are allowed some state). How can you find the restaurant?
You may assume that once you enter an intersection, you can continue to the left, continue to the right, or return to where you just came from.
As an alternative puzzle, suppose you must continue through an intersection, turning either left or right, but not turning around to exit the intersection the way you just entered it.
Pamela Zave shared this problem with me.
Hilary and Jocelyn are throwing a dinner party at their house and have invited four other couples. After the guests arrive, people greet each other by shaking hands. As you would expect, a couple do not shake hands with each other and no two people shake each other’s hands more than once. At some point during the handshaking process, Jocelyn gets up on a table and tells everyone to stop shaking hands. She also asks each person how many hands they have shaken and learns that no two people on the floor have shaken the same number of hands. How many hands has Hilary shaken?
Radu Grigore told me this problem. I think may have heard it 20 years earlier from Jan van de Snepscheut.
Given an even number of points in general positions on the plane (that is, no three points co-linear), can you partition the points into pairs and connect the two points of each pair with a single straight line such that the straight lines do not overlap?
Roger Wattenhofer told me this puzzle.
Someone picks, at their will, two cards from a deck of cards. The cards have different numbers, so one is higher than the other. (In other words, the person picks two distinct numbers in the inclusive range 1 through 13.) The cards are placed face down on a table in front of you. You get to choose one of the cards and turn it face up. Now, you will select one of the two cards (one of whose face you can see, the other one you can’t). If you select the highest card, you win. Design a card-selection strategy for which your chance of winning is strictly greater than 50%.
I got this problem from Radu Grigore, who I think told me it was a problem used in the 2009 Math Olympics. I suppose perhaps the problem then involved 2009 cards.
There is a table with a row of 2014 cards. Each card has a red side and a blue side. We’ll say that a card is red if the color on its visible face is red, and analogously for blue. Two players take turns to do the following move: select any 50 consecutive cards where the left-most card is red, then flip each of those 50 cards (thus, for those 50 cards, turning red cards into blue cards and blue cards into red cards). Both players look at the cards from the same side of the table, so "left-most" means the same to both of the players (that is, you can think of one of the ends of the table as being designated as the left end). When it is a player’s turn, if that player cannot make a move (that is, if there is no way to select 50 consecutive cards the left-most one of which is red), then that player loses and the other player wins. If you are one of the players and all cards are initially red, can you be sure to win, and if so, do you want to be the player who goes first or second?
Prakash Panangaden told me this problem.
There is a polynomial and you have access to a function that evaluates that polynomial at a given number. You don’t know the degree of the polynomial, nor do you know any of the coefficients of its terms. However, you are told that all coefficients are non-negative integers. How many times do you need to call the evaluation function in order to identify the polynomial (that is, to figure out the values of its coefficients)?
I was asked this puzzle by Vlad Rusu, who in turn heard it from Grigore Rosu and family
Two arbitrary rectangles are placed to form an “L”. That is, the lower left-hand corner of the two rectangles share the same point. (What I’m trying to say is that there’s an “L” whose “I” and “_” parts have arbitrary widths and heights.) Using only a (pen and a) straightedge (that is, no measuring device and no compass), figure out a way to, with a single straight cut, divide the “L” into two pieces of equal area.
[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?
[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 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 got this problem from Radu Grigore.]
A spy is located on a one-dimensional line. At time 0, the spy is at location A. With each time interval, the spy moves B units to the right (if B is negative, the spy is moving left). A and B are fixed integers, but they are unknown to you. You are to catch the spy. The means by which you can attempt to do that is: at each time interval (starting at time 0), you can choose a location on the line and ask whether or not the spy is currently at that location. That is, you will ask a question like “Is the spy currently at location 27?” and you will get a yes/no answer. Devise an algorithm that will eventually find the spy.
[I got this problem from Mariela Pavlova.]
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
[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).
[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 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 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?
[This problem was told to me by Clark Barrett, who got it from his father. 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?
[Rajeev Joshi told me this problem.]
The harmonic series–that is, 1/1 + 1/2 + 1/3 + 1/4 + …–diverges. That is, the sum is not finite. This is in difference to, for example, a geometric series–like (1/2)^0 + (1/2)^1 + (1/2)^2 + (1/2)^3 + …–which converges, that is, has a finite sum.
Consider the harmonic series, but drop all terms whose denominator represented in decimal contains a 9. For example, you’d drop terms like 1/9, 1/19, 1/90, 1/992, 1/529110. Does the resulting series converge or diverge?
[More generally, you may consider representing the denominator in the base of your choice and dropping terms that contain a certain digit of your choice.]
[Here is a follow-up question suggested by Gary Leavens.]
Consider again the harmonic series, but drop a term only if the denominator represented in decimal contains two consecutive 9’s. For example, you’d drop 1/99, 1/992, 1/299, but not 1/9 or 1/909. Does this series converge or diverge?
[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?
[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 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.
[Matthew Parkinson told me this problem, or a slight variation thereof.]
You are given a balance (that is, a weighing machine with two trays) and a positive integer N. You are then to request a number of weights. You pick which denominations of weights you want and how many of each you want. After you receive the weights you requested, you are given a thing whose weight is an integer between 1 and N, inclusive. Using the balance and the weights you requested, you must now determine the exact weight of the thing.
As a function of N, how few weights can you get by requesting?
[Unlike most problems in my puzzle collection, this problem requires some computer science knowledge. Many years ago, I read a solution to this problem in one of Donald Knuth’s books (I think). The algorithm intrigued me and stuck in my mind.]
Consider the following array operations. Init(N,d) initializes an array of N elements so that each element has value d. Once Init has been called, the following two operations can be applied: For any i such that 0 <= i < N, Get(i) returns the array element at position i and Set(i,v) sets the array element at position i to the value v.
Given any amount of memory you want, implement the three operations so that each operation has an O(1) time complexity.
[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.
[Vladislav Shcherbina told me this problem.]
A ledge is 1 meter long. On it are N lemmings. Each lemming travels along the ledge at a constant speed of 1 meter/minute. A lemming continues in the same direction until it either falls off the ledge or it collides with another lemming. If two lemmings collide, they both immediately change their directions. Initially, the lemmings have arbitrary starting positions and starting directions. What is the longest time that may elapse before all lemmings have fallen off the ledge?
[Michael Jackson suggested the following variation of the problem: Suppose the ledge is not horizontal, but is leaning. A lemming now travels up the ledge at a speed of 1 meter/minute and travels down the ledge at a speed of 2 meters/minute. What is the longest time before all lemmings have fallen off?]
[I got this problem from Radu Grigore.]
You are given four points (on a Euclidian plane) that make up the corners of a square. You may change the positions of the points by a sequence of moves. Each move changes the position of one point, say p, to a new location, say p’, by "skipping over" one of the other 3 points. More precisely, p skips over a point q if it is moved to the diametrically opposed side of q. In other words, a move from p to p’ is allowed if there exists a point q such that q = (p + p’) / 2.
Find a sequence of moves that results in a larger square. Or, if no such sequence is possible, give a proof of why it isn’t possible. (The new square need not be oriented the same way as the original square. For example, the larger square may be turned 45 degrees from the original, and the larger square may have the points in a different order from in the original square.)
[I got this problem from Rajeev Joshi, who got it from Alex Groce.]
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?
Follow-up question: What is the probability that the penultimate passenger gets to sit in her assigned seat?
[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?
[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).
I got this problem from Clark Barrett, who got it from Robert Nieuwenhuis. Just when you thought you had heard all variations of prisoners and boxes…
100 prisoners agree on a strategy before playing the following game: One at a time (in some unspecified order), each of the prisoners is taken to a courtyard where there is a line of 100 boxes. The prisoner gets to make choices to open 50 of the boxes. When a box is opened, it reveals the name of a prisoner (the prisoners have distinct names). The names written in the boxes are in 1-to-1 correspondence with the prisoners; that is, each name is found in exactly one box. If after opening 50 boxes, the prisoner has not found his own name, the game is over and all the prisoners lose. But if the prisoner does find the box that contains his name among the 50 boxes he opens, then the prisoner is taken to the other side of the courtyard where he cannot communicate with the others, the boxes are once again closed, and the next prisoner is brought out into the courtyard. If all prisoners make it to the other side of the courtyard, they win.
One possible strategy is for each prisoner to randomly select 50 boxes and open them. This gives the prisoners 1 chance out of 2100 to win–a slim chance, indeed. But the prisoners can do better, using a strategy that for a random configuration of the boxes will give them a larger chance of winning. How good a strategy can you develop?
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 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 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.)
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 got this problem from Vladislav Shcherbina.
You have 240 barrels of wine, one of which has been poisoned. After drinking the poisoned wine, one dies within 24 hours. You have 5 slaves whom you are willing to sacrifice in order to determine which barrel contains the poisoned wine. How do you achieve this in 48 hours?
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?
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.
[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).
[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.
[I got this problem from Joe Morris, who created it.]
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?
[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.
[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 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 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 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.
[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.]
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.
[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 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.
[This problem is a bit fuzzier than most on this page, just because I don’t know for sure that the cookbook publisher made a translation error. But I hope you’ll still enjoy the problem.]
Recently, I received a wonderful cookbook. In an appendix, it shows a table that converts oven temperatures between Celsius and Fahrenheit. (Side remark: Approximate oven temperatures are actually really simple to convert in your head–just double the number of degrees Celsius to get the number of degrees Fahrenheit. For oven temperatures, this will be within 10 F of the exact answer.)
The table has a footnote that says "If your oven has a fan, reduce the recipe temperature by 68 F". I have a strong hunch that this footnote suffers from a translation error. How many degrees Fahrenheit should it have said to reduce the temperature by? (No knowledge of convection ovens required.)
[This problem was communicated to me by Sophia Drossopoulou.]
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.]
[I got this puzzle from Alex Pintilie.]
Two witches each makes a nightly visit to an all-night coffee shop. Each arrives at a random time between 0:00 and 1:00. Each one of them stays for exactly 15 minutes. On any one given night, what is the probability that the witches will meet at the coffee shop?