Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Fifteen Sum

Puzzle

Alice and Bob take turns to pick numbers from 1 thru 9, without replacement. The first to possess three distinct numbers that sum to 15 wins. Does Alice have a winning strategy?

Source

From Peter Winkler's puzzles book.

Solution

Eight subsets of {1, 9} sum to 15. These are {1, 5, 9}, {2, 5, 8}, {3, 5, 7}, {4, 5, 6}, {1, 6, 8}, {2, 4, 9}, {2, 7, 6} and {3, 4, 8}. An insight into the structure of these eight possible subsets is helpful. The subsets can be laid out as a 3x3 magic square. The three rows, the three columns and the two diagonals of the magic square sum to 15 each.

2  7   6  
9  5   1  
4  3   8  

The final insight is that Alice and Bob are simply playing tic-tac-toe on the magic square! So Alice does not have a winning strategy.

Previous Puzzle: Ants in a Circle

Suppose n ants are placed on a circle with a diameter of one meter. Each ant location is chosen independently, uniformly at random. An ant chooses between clockwise or anti-clockwise direction, uniformly at random, and starts scampering along the circle. All ants move at the same speed: one meter per second. When two ants bump into each other, they reverse their direction of travel. One of the ants is named Alice. What is the probability that Alice returns to the same point as she started, one minute after the ants start their scampering?

Next Puzzle: Four Ships

Four ships are sailing on a 2D planet. Each ships traverses a straight line at constant speed. No two ships are traveling parallel to each other. Their journeys started at some time in the distant past. Sometimes, a pair of ships collides. A ship continues its journey even after a collision. However, it is strong enough only to survive two collisions; it dies when it collides a third time. The situation is grim. Five of six possible collisions have already taken place (no collision involved more than 2 ships) and two ships are out of commission. What fate awaits the remaining two?

20 Feb 2013
© Copyright 2008—2017, Gurmeet Manku.