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:
What are the numbers? Acquired on Lance Fortnow’s blog.