問題022｜整数・数え上げと小さい解への帰着

$x$ を11で割った余りに取り直すと，$0\le x\le 10$ としてよい．この11個の $7x$ は，11を法としてすべて異なる余りをもつ．

$7r$ と同じ余りをもつ整数のうち，表せない正整数は $7r-11,7r-22,\dots$ である．総数を求める際は $r$ と $11-r$ を組にせよ．

解 $(x,y)$ から $(3x-4y,3y-2x)$ を作ると，左辺の値は変わらない．$y>2$ のとき，この新しい組も正整数になるかを調べよ．

$y>2$ ならば $4y/3<x<3y/2$ が成り立つので，変換後の2成分は正で，さらに第2成分は $y$ より小さい．逆変換は $(u,v)\mapsto (3u+4v,2u+3v)$ である．

(1) 隣り合う2つの二項係数の差を考えよ．(2) 階乗に含まれる2の因子の個数は $\lfloor m/2\rfloor +\lfloor m/4\rfloor +\cdots$ で数えられる．

$m$ の二進表示に現れる1の個数を $s_2(m)$ とすると，$m!$ に含まれる2の指数は $m-s_2(m)$ である．これを使うと $C_n$ に含まれる2の指数は $s_2(n)-v_2(n+1)$ になる．

非負整数値であることと $f(2)=0$ から $f(1)$ を決め，次に $f(3)$ を決めよ．条件を繰り返すと $f(3k)\ge k$ が得られる．

$9999=3k+3(3333-k)$ と分割して，$1\le k\le 3333$ で $f(3k)=k$ を示せ．最後に $1982=1980+2$ と $5946=1982+1982+1982$ を使え．

$x=11q+r$，$0\le r\le 10$ と書けば，$7x+11y=7r+11(y+7q)$ となる．したがって，表せる整数全体は $7r+11t$（$r=0,\dots ,10,t\ge 0$）である．7と11は互いに素なので，$7r$ の余りはこの11個で0から10までをちょうど1回ずつとる．

$r\ge 1$ の剰余類で表せない正整数は，$7r$ より小さいもの，すなわち $7r-11,7r-22,\dots$ のうち正のものである．全体の最大値は $r=10$ のときの $70-11=\boxed{{\displaystyle 59}}$ である．

その個数は $\lfloor 7r/11\rfloor$ だから，総数は $\sum _{r=1}^{10}\lfloor 7r/11\rfloor$ となる．$7r/11$ は整数でないので，

である．$r$ と $11-r$ の5組を足すと，総数は $\boxed{{\displaystyle 30}}$ 個と分かる．余り0の正整数はすべて11の倍数として表せるので，加えるべきものはない．

$y=1$ では $x^2=3$ となり解はなく，$y=2$ では $(x,y)=(3,2)$ である．$y>2$ の解について，$u=3x-4y,v=3y-2x$ と置くと，展開によって

となる．また $x^2=2y^2+1$ より $x>4y/3$ であり，$y>2$ から $2y^2+1<9y^2/4$，すなわち $x<3y/2$ である．よって $u,v>0$ である．さらに $x>y$ より $v=3y-2x<y$ である．

したがって，$y>2$ の解からは，必ず第2成分が小さい正整数解が得られる．これを繰り返すと有限回で $(3,2)$ に到達する．逆変換は

で一意に決まるので，すべての正整数解は $(3,2)$ からこの逆変換を繰り返して得られる．順に

となり，第2成分は狭義に増加する．よって求める組は $\boxed{{\displaystyle (3,2),(17,12),(99,70)}}$ である．

(1) $n=0$ では $C_0=1$ である．$n\ge 1$ では

より，$C_n=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n+1})$ となる．したがって $C_n$ は整数である．

(2) 正整数 $M$ を割り切る2の最高べきの指数を $v_2(M)$ とする．$m!$ の各因子について2の因子を1個ずつ数えると，

である．$m=\sum _{i\ge 0}{\epsilon }_i{2}^i$（${\epsilon }_i=0,1$）と二進表示し，$s_2(m)=\sum _i{\epsilon }_i$ と置くと，右辺は

となる．$s_2(2n)=s_2(n)$ だから，

$n$ の二進表示の末尾に連続する1の個数を $t$ とすると，1を加えたときの繰り上がりから $v_2(n+1)=t$ である．よって $v_2(C_n)=0$ となるのは，二進表示の1が末尾の $t$ 個だけである場合，すなわち $n=2^t-1$ の場合に限られる．$n=0$ も $t=0$ に対応する．したがって答えは

である．

$m=n=1$ を代入すると，$0=f(2)=2f(1)+\delta$（$\delta =0$ または1）である．$f(1)$ は非負整数なので $f(1)=0$ である．次に $3=1+2$ より $f(3)\in \{0,1\}$ であり，$f(3)>0$ だから $f(3)=1$ となる．

与条件から常に $f(m+n)\ge f(m)+f(n)$ である．帰納的に $f(3k)\ge k$ が従う．$1\le k<3333$ ならば，

したがって途中もすべて等号であり，$f(3k)=k$ である．$k=3333$ の場合は仮定そのものである．

$1982=1980+2$ より，$f(1982)\ge f(1980)+f(2)=660$ である．一方，$5946=3\cdot 1982$ と先ほどの結果から，

となる．$f(1982)$ は整数なので $f(1982)\le 660$ である．以上より $\boxed{{\displaystyle f(1982)=660}}$ を得る．なお，$f(n)=\lfloor n/3\rfloor$ はすべての条件を満たすので，条件が両立することも確認できる．