My Math Team Teacher gave us this combinatorial-number-theory problem.
Ann and Ben plays the following game:
The numbers $1, 2, 3,...,n$, where $n\in\mathbb{Z}^+$, are written on the blackboard.
Ann and Ben do the following operation, where Ann starts first.
Choose a number $m$ remaining on the blackboard. Then rub out all factors of $m$.
The person who rubs out the last number wins.
For which values of $n$, Ann has a wining strategy?
The teacher said that it is hard, so we may ask for help.
Also, I tried $n=1, 2, 3, 4, 5$ and they all works.
For $n=1$, Ann should choose $m=1$ so she rubs out $1$.
For $n=2$, Ann should choose $m=2$ so she rubs out $1$ and $2$.
For $n=3$, Ann should choose $m=1$ so she rubs out $1$, then Ben rubs out $2$ or $3$, then Ann rubs out the remaining.
For $n=4$, Ann should choose $m=2$ so she rubs out $1$ and $2$, then Ben rubs out $3$ or $4$, then Ann rubs out the remaining.
For $n=5$, Ann should choose $m=4$ so she rubs out $1,2$ and $4$, then Ben rubs out $3$ or $5$, then Ann rubs out the remaining.
Can someone help me? Any help is appreciated.
This is a classic strategy stealing argument. Ann can always win. Given an $n$, assume Bob can win. He must have a winning response to Ann playing $1$. Ann can play that number, which rubs out $1$ and win because she is leaving the same position Bob would leave after she played $1$. This is a contradiction, so our assumption that Bob can win is wrong.
Note that this does not provide a winning strategy for Ann, just proves that one exists.