Bariz - Problem

Source: 2022 IMOC C2

Tags: combinatorics, IMOC

CrazyInMath

05.09.2022 15:54

There are $2022$ stones on a table. At the start of the game, Teacher Tseng will choose a positive integer $m$ and let Ming and LTF play a game. LTF is the first to move, and he can remove at most $m$ stones on his round. Then the two people take turns removing stone, each round they must remove at least one stone, and they cannot remove more than twice the amount of stones the last person removed. The player unable to move loses. Find the smallest positive integer $m$ such that LTF has a winning strategy. Proposed by ltf0501

Let $f(n)$ be the answer of $n$ stones, here $f(0):=+\infty.$ We have $f(1)=1,f(2)=2,f(3)=3$ and $f(n)=\min_{f(n-m)\ge 2m+1}m.$ By listing $f(1)\sim f(21)$ we will realize $f(n)=n$ when $n$ is Fibonacci number, and $f(n)=f(n-F)$ otherwise, here $F$ is the biggest Fibonacci number less than $n.$ It can be easily proved by induction. Finally $f(2022)=f(1597+425)=f(425)=f(377+48)=f(48)=f(34+14)=f(14)=f(13+1)=f(1)=1,$ so $m=1$ is enough.$\Box$ Remark. What's interesting, after I solve this, I found this problem in OI is earlier and even harder, this one will be really easy if we've seen that before.