# Using your Head is Permitted

## January 2013 riddle

The following are four classic riddles. Answer all four, with proofs, for credit. No Internet searching, please.

All four riddles refer to a turn-based game where two players, taking alternate turns, each removes, in her turn, a chosen number of elements from a pile. The initial pile-size is N, a positive integer. The games differ in the rules regarding how many elements a player is allowed to remove in her turn. In every case, this number is restricted to be a positive integer. The player to lose is the first to have no legal moves left. For example, this happens if the pile is completely emptied.

The object is to determine which of the two players (first to play or second to play) has a winning strategy, as a function of N. The rules for the different games are as follows.

#### Part 1:

Each player is allowed to take from the pile any non-composite number of elements.

#### Part 2:

Each player is allowed to take any positive amount that is less than half the total number of elements in the pile.

#### Part 3:

On the first turn, the first to play can take any amount that is less than N. On any subsequent turn, each player can take any amount that is less than twice what was taken (by the other player) in the preceding turn.

#### Part 4:

On the first turn, the first to play can take any amount that is less than N. On any subsequent turn, each player can take any amount that is no more than twice what was taken (by the other player) in the preceding turn.

### List of solvers:

Radu-Alexandru Todor (2 January 09:30)
Oded Margalit (3 January 00:56)
Joseph DeVincentis (3 January 03:56)
Lewei Weng (5 January 17:20)
Liubing Yu (10 January 15:51)
Deron Stewart (11 January 09:46)
Erick Wong (12 January 19:46)
Harald Bögeholz (16 January 18:58)
Todd Will (22 January 08:28)
Daniel Bitin (25 January 01:03)
Øyvind Grotmol (25 January 08:57)
Hooman Habibi (30 January 10:59)
Thomas Mack (31 January 08:43)

Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!