The number $2$ is written on the board. Ana and Bruno play alternately. Ana begins. Each one, in their turn, replaces the number written by the one obtained by applying exactly one of these operations: multiply the number by $2$, multiply the number by $3$ or add $1$ to the number. The first player to get a number greater than or equal to $2011$ wins. Find which of the two players has a winning strategy and describe it.
Problem
Source:
Tags: combinatorics proposed, combinatorics
m.candales
04.10.2011 22:27
Bruno has a winning strategy Notation: >> $[x, y]$ is the interval of all the natural numbers from $x$ to $y$ inclusive. >> $(x, y)$ is the interval of all the natural numbers from $x$ to $y$ inclusive, and with the same parity than $x$ and $y$. This requires that $x$ and $y$ have the same parity. Let $S_A = (2)\cup(5, 13)\cup(28, 54)\cup(57, 167)\cup(336, 670)$ Let $S_B = (3)\cup(4, 12)\cup[14, 27]\cup(29, 55)\cup(56, 166)\cup[168, 335]\cup(337, 669)\cup(671, 2010)$ Notice that $S_A\cup S_B = [2, 2010]$ and $S_A\cap S_B = \emptyset$ The strategy is to always have a number from $S_A$ written in the board when Ana's turn starts. Bruno can achieve this as follows: If when Bruno's turn starts, the number written in the board is a number that belongs to: >> $(3)$ then he does $*3$ >> $(4, 12)$ then he does $+1$ >> $[14, 27]$ then he does $*2$ >> $(29, 55)$ then he does $*3$ >> $(56, 166)$ then he does $+1$ >> $[168, 335]$ then he does $*2$ >> $(337, 669)$ then he does $+1$ >> $(671, 2010)$ then he does $*3$ and wins Check that by applying any of the three operations to a number in $S_A$ we always get a number in $S_B$