Petar Maymounkov

Some old puzzles from the battlefield

Wed, Oct 30, 2013

Problem 1*

You are presented with 12 identically looking balls of which, you are told, only one differs in weight than the others. Your goal is to find which one it is and whether it is lighter or heavier than the rest. Your only tool is a scales, which can be used by putting balls (and only balls) on either side and observing the outcome. The scales can be used at most three times. Anonymous.


Problem 2*

You have two identical crystal orbs. Your goal is to figure out how high a floor an orb can fall from a 100 story building before it breaks. What is the largest number of orb-drops you would ever have to do to find the right floor (i.e. what is the most efficient strategy by a worst-case measure)? You can break both orbs in your search, provided you yield a unique and correct answer. Devised by Mark Gorton.


Problem 3*

Suppose some guy has 1000 bottles of wine. He finds out that 1 bottle is poisoned. Fortunately, he has 10 mice which he can use to check which bottle is tainted. It takes a day though to find the result of the test (i.e. if mouse drinks bad wine, it dies in 24 hrs). The dude is throwing a big party the next night. If he runs optimal tests with his mice, how many of the 1000 bottles can he served at the party? E.g. he could have each mouse drink from a bottle. If they all live, he knows that 10 bottles are safe. All mice have to be assigned to bottles right away, because there’s only 24 hours to the party. Communicated by Sanjay Menon.


Problem 4*

Four beer caps are placed on the corners of a square table with arbitrary orientations. There is a robot on the table that acts upon three commands: (a) “flip a corner cap”, (b) “flip two diagonal caps” and (c) “flip two side-wise caps”. However, upon action there is no guarantee as to which corner, diagonal or side, respectively, hethe robot will choose to flip. Devise a sequence of commands that forces the robot to turn all caps in a configuration where they all have the same orientation. Communicated by Benjamin Rossman.


Problem 5***

You are given an 8×8 chess board and a set of 31 dominos, such that each domino covers exactly two adjacent squares on the chess board. Two diametrically and diagonally opposite squares are cut away from the chess board (so that it has a total of 62 squares left). Your task is to 1cover the remaining chessboard with dominos, such that it is completely covered and no dominos overflow from the sides of the modified chess board. Communicated by Tasho Statev Kaletha.


Problem 6**

You are given a computer with an n-bit machine word, which supports the standard bitwise operations: AND, OR, NOT, XOR, LEFT SHIFT, and RIGHT SHIFT. Given a machine word w, what is the smallest number of bitwise operations you need to determine the number of set bits in that word? You can assume you have arbitrarily many registers to use and COPY operations are not counted. The result has to be presented in the form of an integer represented by a machine word. Communicated by David Karger.


Problem 7

Approximate √1 + √2 + · · · + √50 in your head (or using a sheet of paper or two) as best as you can. Anonymous.


Problem 8**

A prisoner is enclosed inside a square. You are given 4 dogs that can roam the perimeter of the square. They run 1.5 times the speed of the prisoner. He escapes if he can cross the border without two or more of the dogs converging on him. Your challenge is to place him initially and program the dogs to keep him inside. You can give each dog a unique program, if you like. Communicated by Sam Yagan via Chris Coyne.


Problem 9**

(The infamous 2-envelope problem.) You play a game. Two closed envelopes are presented to you. Inside each envelope is a positive real number, such that the two envelopes contain different numbers. You get to pick an envelope and open it. After looking at the number inside the envelope you can choose to end the game and your reward is that number. You can also opt to end the game with whatever number is in the other envelope. The question: What strategy ensures that with probability strictly greater than 1/2 you end up with the larger number? No assumptions whatsoever can be placed on the numbers inside the envelopes. The problem was first communicated by Chris Coyne many years ago. An amazing solution was given by Krzysztof Onak.


Problem 10***

Show that the unit cube cannot be partitioned into a finite number of smaller cubes of pairwise unequal side lengths. Note that this is not true for the square. Communicated by Benjamin Rossman.


Problem 11**

Let COL be a 3-coloring of 1, . . . , 2006. Show that there exists x,y such that COL(x) = COL(y) and |x − y| is a square. Appeared on Maryland Math Olympiad 2006. Acquired from Luca Trevisan’s blog.


Problem 12**

A regular hexagonal tiling is drawn on a sheet of paper (note that some hexagons along the edges of the paper may be incomplete), such that there is at least one complete hexagon. Consider an arbitrary black-and-white covering of the hexagons. Prove that there is either a black path (of hexagons) from the top to the bottom edge of the sheet, or a white path from the left to the right edge of the sheet. For the purpose of a path, two hexagons are adjacent if they share an edge. Also a hexagon is considered to be on the left edge of the sheet if they share an edge. (Likewise for right, top and bottom.) Communicated by Benjamin Rossman.


Problem 13*

(The Sum and Product Riddle) Let x and y be two integers with 1 < x < y and x + y <= 100. Sally is given only their sum x + y and Paul is given only their product xy. Sally and Paul are honest and all this is commonly known to both of them.

The following conversation now takes place:

Paul: I do not know the two numbers.
Sally: I knew that already.
Paul: Now I know the two numbers.
Sally: Now I know them also.

What are the numbers? Acquired on Lance Fortnow’s blog.

Comments? Please join the Google+ discussion. A read-only copy follows: