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) を求めよ。
ステップ 6/7: 優加法性を三倍にして 661661 を排除する
前のステップ次のステップ
ざっくり言うと

小さな f(3k)f(3k) に対して kk を確定させたのと同じ挟み撃ちが再び現れ、既に厳密な値が分かっている三倍の添字と比較することで、残る二つの候補のうち大きい方を排除する。

f(3n)=f(n+n+n)≥f(n)+f(2n)≥f(n)+f(n)+f(n)=3f(n)f(3n)=f(n+n+n)\ge f(n)+f(2n)\ge f(n)+f(n)+f(n)=3f(n)
詳しい解説

優加法性を二回適用すると、すべての f(3n)≥3f(n)f(3n)\ge3f(n) に対して nn が成り立つ。n=1982n=1982 とすると、もし f(1982)=661f(1982)=661 ならば f(5946)=f(3⋅1982)≥3⋅661=1983f(5946)=f(3\cdot1982)\ge3\cdot661=1983 となる。しかし 1982≤33331982\le3333 なので、ステップ3より厳密な値は f(5946)=f(3⋅1982)=1982f(5946)=f(3\cdot1982)=1982 であり、1982≥19831982\ge1983 に矛盾する。