MathLabs

第1問

関数 f(n)f(n) は正の整数上で定義され、非負整数値をとる。f(2)=0f(2)=0、f(3)>0f(3)>0、f(9999)=3333f(9999)=3333 であり、任意の m,nm,n に対して f(m+n)−f(m)−f(n)=0 or 1.f(m+n)-f(m)-f(n)=0 \text{ or } 1. が成り立つ。f(1982)f(1982) を求めよ。
ステップ 3/7: f(3k)f(3k) を下限と f(9999)=3333f(9999)=3333 で挟み撃ちにする
ざっくり言うと

この証明全体の要となる挟み撃ちである。優加法性のみから作った下限が、与えられた唯一の厳密な大きな値による上限とちょうど一致し、ff の無数の値が一挙に確定する。

f(3(k+1))≥f(3k)+f(3)=f(3k)+1for all k≥1f(3(k{+}1))\ge f(3k)+f(3)=f(3k)+1 \quad\text{for all } k\ge1
詳しい解説

m=3k, n=3m=3k,\,n=3 に対する優加法性より、数列 ak=f(3k)a_k=f(3k) は各段階で少なくとも 11 ずつ増加するので、すべての ak≥a1+(k−1)=ka_k\ge a_1+(k-1)=k に対して k≥1k\ge1。ところが a3333=f(9999)=3333a_{3333}=f(9999)=3333 はこの下限にちょうど等しい。もしどこか一段階で 22 以上増加すれば a3333a_{3333} は 33333333 を超えてしまい矛盾する。したがって各段階の増分はちょうど 11 であり、すべての f(3k)=kf(3k)=k に対して 1≤k≤33331\le k\le3333 である。