yukicoder 2016 Countdown Divisors の手で出来る証明
（注）この記事はネタバレを含みます。
先日の yukicoder で面白い問題が出ました。解いていない方はぜひ解いてみてください。
解説では、ある程度の範囲の全探索によって正当性を示していますが、ここではこの問題が「数学の試験」であったと仮定して、紙と手だけで出来る証明を書きます。（本質はほとんど変わりませんが、一応 N の上限に関わらず示せているという差分もあります。）
整数 x に対する答えを f(x) とおきます。
まず、1から17まで手で実験します。
すると、x=1,3,4,5,7,8 で答えが 1 、それ以外で 2 であることが分かります。
特に、9<=x<=17 で答えが全て 2 です。
f(x)=f(x-d(x)) であること、および
x-d(x)>= x-2*sqrt(x) >= x/2 (2 つめの等式において x>=16 を仮定)
を用いると、18 以上の任意の x について、x-d(x) に変換していく過程で必ず 9<=x<=17 であるタイミングがあります。以上から、x>=18 において全て f(x)=2 が示されました。
