MathDB
Alice keeps writing numbers

Source: India EGMO 2022 TST P2

November 21, 2021
wetindiacombinatorics

Problem Statement

Let a,ba,b be arbitrary co-prime natural numbers. Alice writes the natural number t<bt < b on a blackboard. Every second she replaces the number on the blackboard, say xx, with the smallest natural number in {x±a,x±b}\{x \pm a, x \pm b \} that she has not yet ever written. She keeps doing this as long as possible. Prove that this process goes on indefinitely and that Alice will write down every natural number.
~Pranjal Srivastava and Rohan Goyal