Consider the following two player game:

Two players take turns naming numbers 1 through 9. Players may not name a number that has already been named. If at any point three of the numbers that one of the players has named add up to exactly 15, that player wins. After all 9 numbers have been named, if neither player has already won, the game is declared a tie.

Is this game a first player win, a second player win, or a tie? This problem shouldnt be too difficult to solve on a computer, but you get bonus points if you can convince a friend of the correct answer in two minutes with out a computer. Solution in comments.

The solution is based on three lemmas:

Lemma 1) There are exactly 8 triples of distinct numbers from 1 to 9 adding to 15.

Lemma 2) There exists a 3 by 3 magic square. (The numbers 1 through 9 are put in a 3 by 3 square so that all the rows columns and diagonals add to 15.)

Lemma 3) Tic-tac-toe is a a tie.

By Lemma 2, you can put the 9 numbers in a magic square. By Lemma 1, the ways to get 15 are exactly the ways to get 3 in a row. The game therefore reduces to tic-tac-toe, which is a tie by Lemma 3.

That is a remarkably clever way to prove it. I’m not sure how I’d convince someone of Lemma 1 without a computer in less than two minutes, but the code to show it using a computer took less than two minutes to write, so I’ll count it as in-bounds.

For reference:

(count (distinct

(for [a (range 1 10) b (range (inc a) 10) c (range (inc b) 10)

:when (= 15 (+ a b c))]

#{a b c})))

# => 8

Thanks for your comment, Orion. When I said convince in 2 minutes, what I had in mind was just what I wrote. (I know I probably wouldn’t bother to check the details on lemma 1 if someone told it to me.)

However, I think you can see in under a minute that there are 2 triples starting with 1, 3 triples starting with 2, 2 triples starting with 3, 1 triple starting with 4, and no others.

Instead of using numbers from 1 to 9, use numbers from -4 to 4 and find triples of distinct numbers which sum to zero. There are four which make use of the number zero, since they must be of the form (-n,0,n), and four which do not: (3,-2,-1),(4,-3,-1) and their negatives.

That is a nice way to do it.