Petar Maymounkov

Wed, Oct 30, 2013

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 ﬁnd 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.*

You have two identical crystal orbs. Your goal is to ﬁgure 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 ﬁnd the right ﬂoor (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.*

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 ﬁnd 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.*

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 conﬁguration where they all
have the same orientation. *Communicated by Benjamin Rossman.*

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
overﬂow from the sides of the modiﬁed chess board. *Communicated by Tasho Statev Kaletha.*

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

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

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

(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 ﬁrst
communicated by Chris Coyne many years ago. An amazing solution was given by Krzysztof Onak.*

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

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

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

(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: