n進法と記数法

方針：$N$ を $n$ で割ると $N=nq+r$（$0\le r< n$）となる。余り $r$ が一の位の数字、商 $q$ が「一の位を取り去った残り」になることを示し、$q< N$ なので小さい数について分かっていることを使う（数学的帰納法 の、$N$ より小さいすべての数で成り立つと仮定する形）。
段 1（商は元の数より小さい）。$N\ge1$ を $n$ で割って $N=nq+r$、$0\le r\le n-1$ とする（除法の原理）。$q\ge0$ である。$n\ge2$ なので $N=nq+r\ge2q$ であり、$q\ge1$ なら $q<2q\le N$、$q=0$ でも $q< N$ である。いずれにせよ $q< N$ である。
段 2（存在）。$N$ より小さい正の整数はすべて $n$ 進法の表し方をもつと仮定する。段 1 の $q$ が $0$ なら $N=r$ で、$1\le r\le n-1$ なので $N=r_{(n)}$ は 1 桁の表し方である。$q\ge1$ なら、仮定により $q=c_{m-1}n^{m-1}+\cdots+c_1n+c_0$（$c_{m-1}\ne0$）と書ける。これを $N=nq+r$ に代入すると
$$ N=c_{m-1}n^m+\cdots+c_1n^2+c_0n+r $$
となる。各係数は $n$ 進法の数字で、最高位 $c_{m-1}$ は $0$ でないので、これは $N$ の表し方である。$N=1$ では $q=0$ となるので、仮定なしに段 2 の前半だけで済む。よって帰納法により、すべての正の整数が表し方をもつ。
段 3（一の位は決まってしまう）。$N=d_mn^m+\cdots+d_1n+d_0$ を任意の表し方とする。$Q=d_mn^{m-1}+\cdots+d_2n+d_1$ とおくと $N=nQ+d_0$ で、$0\le d_0\le n-1$ である。除法の原理 により、$N=nq+r$、$0\le r< n$ をみたす整数の組 $(q,r)$ はただ 1 つなので、$d_0=r$、$Q=q$ である。つまり、どの表し方でも一の位の数字は「$N$ を $n$ で割った余り」であり、残りの数字は商 $q$ を表している。
段 4（一意性）。$N$ より小さい正の整数では表し方が 1 通りと仮定する。$N$ の表し方が 2 つあるとすると、段 3 により一の位の数字はどちらも $r$ である。$m=0$（1 桁）なら $Q=0$、$m\ge1$ なら $Q\ge d_mn^{m-1}\ge1$ なので、$q=0$ のときはどちらの表し方も 1 桁の $r$ で一致する。$q\ge1$ のときは、どちらの表し方でも残りの数字 $d_m\cdots d_1$ は $q$ の表し方になっている（最高位の $d_m\ne0$ もそのまま）。$q< N$ なので仮定により $q$ の表し方は 1 通りで、残りの数字も一致する。帰納法により、すべての正の整数で表し方は 1 通りである。$\square$

方針：$m+1$ 桁の数のうち最小のものと最大のものを求め、桁数ごとに数の範囲が隙間なく分かれることを使う。
段 1（$m+1$ 桁なら $n^m\le N< n^{m+1}$）。$N=d_mn^m+\cdots+d_0$、$d_m\ge1$ なら、ほかの数字は $0$ 以上なので $N\ge n^m$ である。また各数字は $n-1$ 以下なので
$$ N\le(n-1)(n^m+n^{m-1}+\cdots+1)=n^{m+1}-1< n^{m+1} $$
である。等号は 等差数列と等比数列 の等比数列の和の公式による。
段 2（逆）。$n^m\le N< n^{m+1}$ とする。$N$ の表し方が $j+1$ 桁なら、段 1 により $n^j\le N< n^{j+1}$ である。もし $j>m$ なら $N\ge n^j\ge n^{m+1}$、もし $j< m$ なら $N< n^{j+1}\le n^m$ となり、どちらも仮定に反する。よって $j=m$ である。$\square$

方針：$n$ 進法の表し方の和を、$k$ 項ずつまとめて $n^k$ の累乗でくくり、thm-bnn-unique の一意性を $n^k$ 進法で使う。
段 1（まとめる）。上に $0$ を補って桁数を $k$ の倍数 $kL$ にし、$N=\sum_{i=0}^{kL-1}d_in^i$ とする。$i=kj+t$（$0\le j\le L-1$、$0\le t\le k-1$）と書くと、$n^i=(n^k)^j\,n^t$ なので
$$ N=\sum_{j=0}^{L-1}\Bigl(\sum_{t=0}^{k-1}d_{kj+t}\,n^t\Bigr)(n^k)^j=\sum_{j=0}^{L-1}D_j\,(n^k)^j,\qquad D_j:=\sum_{t=0}^{k-1}d_{kj+t}\,n^t $$
である。$D_j$ が $j$ 番目の組を 1 つの数に置きかえたものである。
段 2（$D_j$ は $n^k$ 進法の数字）。$D_j\ge0$ であり、各 $d_{kj+t}\le n-1$ なので、prop-bnn-digits の証明の段 1 と同じ計算で $D_j\le(n-1)(1+n+\cdots+n^{k-1})=n^k-1$ である。
段 3。上の $0$ の組を除けば、段 1 の式は $N$ の $n^k$ 進法の表し方である。thm-bnn-unique により、それが $N$ の $n^k$ 進法の表し方そのものである。$\square$

方針：$a_k:=\lfloor n^kx\rfloor$ とおく。$d_k=a_k-na_{k-1}$ なので、部分和は「引いて足す」で打ち消し合い、$a_K/n^K$ だけが残る。これが $x$ と $1/n^K$ 未満しか違わないことを示す。$\lfloor\ \rfloor$ について使うのは、定義の不等式 $y-1<\lfloor y\rfloor\le y$ と、「整数 $m$ について $m\le y$ と $m\le\lfloor y\rfloor$ は同値」の 2 つだけである（証明は ガウス記号と整数の個数 の基本性質）。
段 1（$d_k$ は $0$ 以上）。$a_{k-1}\le n^{k-1}x$ の両辺に $n$ を掛けると $na_{k-1}\le n^kx$ である。$na_{k-1}$ は整数なので $na_{k-1}\le\lfloor n^kx\rfloor=a_k$、すなわち $d_k\ge0$ である。
段 2（$d_k$ は $n-1$ 以下）。$n^{k-1}x< a_{k-1}+1$ の両辺に $n$ を掛けると $n^kx< na_{k-1}+n$ である。$a_k\le n^kx$ なので $a_k< na_{k-1}+n$ で、整数どうしなので $a_k\le na_{k-1}+n-1$、すなわち $d_k\le n-1$ である。
段 3（部分和）。$0\le x<1$ なので $a_0=\lfloor x\rfloor=0$ である。$\dfrac{d_k}{n^k}=\dfrac{a_k}{n^k}-\dfrac{a_{k-1}}{n^{k-1}}$ なので
$$ \sum_{k=1}^K\frac{d_k}{n^k}=\Bigl(\frac{a_1}{n}-\frac{a_0}{1}\Bigr)+\Bigl(\frac{a_2}{n^2}-\frac{a_1}{n}\Bigr)+\cdots+\Bigl(\frac{a_K}{n^K}-\frac{a_{K-1}}{n^{K-1}}\Bigr)=\frac{a_K}{n^K} $$
である。
段 4（極限）。$n^Kx-1< a_K\le n^Kx$ を $n^K$ で割ると
$$ x-\frac1{n^K}<\sum_{k=1}^K\frac{d_k}{n^k}\le x $$
である。$K\to\infty$ で $\dfrac1{n^K}\to0$ なので、はさみうちにより部分和は $x$ に収束する。$\square$

方針：展開の「$K$ 桁目より先の部分」を $n^K$ 倍したもの（残りの部分）を考える。残りの部分は最大でも $1$ で、$1$ になるのは先の数字がすべて $n-1$ のときに限る。これを使って、数字が「$n$ 倍した数の整数部分」として決まってしまうことを示す。
段 1（残りの部分の大きさ）。数字の列 $c_1,c_2,\dots$ について $t:=\sum_{j=1}^\infty\dfrac{c_j}{n^j}$ とおくと、def-bnn-fraction の直後の計算により $0\le t\le1$ である。さらに、ある $c_i$ が $n-1$ でなければ $c_i\le n-2$ なので、その項だけ上からの評価が $\dfrac1{n^i}$ 小さくなり、$t\le1-\dfrac1{n^i}<1$ である。逆に、すべての $c_j$ が $n-1$ なら $t=\sum_j\dfrac{n-1}{n^j}=1$ である。
段 2（1 の証明）。prf-bnn-fraction の段 3・4 から、$x-\sum_{k=1}^K\dfrac{d_k}{n^k}=x-\dfrac{a_K}{n^K}$ である。これを $n^K$ 倍した $n^Kx-a_K$ は、定義により $0$ 以上 $1$ 未満である。一方、左辺は $\sum_{k>K}\dfrac{d_k}{n^k}$ なので、$n^K$ 倍すると $\sum_{j\ge1}\dfrac{d_{K+j}}{n^j}$ になる。もし $K$ より先の数字がすべて $n-1$ なら、段 1 によりこれは $1$ に等しく、「$1$ 未満」に反する。よって、どの $K$ についても $K$ より先に $n-1$ でない数字がある。
段 3（2 の証明）。$t_K:=\sum_{j\ge1}\dfrac{e_{K+j}}{n^j}$ とおくと、$e$ の列は $K$ より先にも $n-1$ でない数字を含むので、段 1 により $0\le t_K<1$ である。$x=\sum_{k=1}^K\dfrac{e_k}{n^k}+\dfrac{t_K}{n^K}$ を $n^K$ 倍すると
$$ n^Kx=\bigl(e_1n^{K-1}+e_2n^{K-2}+\cdots+e_K\bigr)+t_K $$
で、括弧の中は整数、$t_K$ は $0$ 以上 $1$ 未満なので、括弧の中は $\lfloor n^Kx\rfloor=a_K$ に等しい。$K-1$ についても同じで、$a_{K-1}=e_1n^{K-2}+\cdots+e_{K-1}$ である。$n$ 倍して引くと $a_K-na_{K-1}=e_K$ となり、$e_K=d_K$ である。これがすべての $K\ge1$ で成り立つ。$\square$

方針：「$K$ 桁以内の有限小数で書ける」を「$n^Kx$ が整数」に、さらに「$b$ が $n^K$ を割り切る」に言いかえ、最後に素因数で判定する。
段 1（有限小数 $\iff$ ある $K$ で $n^Kx$ が整数）。$x=0.d_1\cdots d_K{}_{(n)}$ なら $n^Kx=d_1n^{K-1}+\cdots+d_K$ は整数である。逆に $n^Kx=M$ が整数なら、$0\le M< n^K$ なので、thm-bnn-unique により $M$ を $n$ 進法で書き、上に $0$ を補って $K$ 桁 $M=c_{K-1}\cdots c_0{}_{(n)}$ にできる。すると $x=M/n^K=0.c_{K-1}\cdots c_0{}_{(n)}$ である（$M=0$ なら $x=0$）。
段 2（$n^Kx$ が整数 $\iff$ $b\mid n^K$）。$n^Kx=\dfrac{an^K}b$ なので、これが整数であることは $b\mid an^K$ と同値である。$a$ と $b$ は互いに素なので、$b\mid an^K$ は $b\mid n^K$ と同値である（互いに素な数についての割り算の性質。整数の割り算と互除法）。
段 3（必要）。ある $K$ で $b\mid n^K$ とし、$p$ を $b$ の素因数とする。$p\mid n^K=n\cdot n\cdots n$ で、素数が積を割り切るなら因数のどれかを割り切る（素因数分解の一意性 の Euclid の補題）ので、$p\mid n$ である。
段 4（十分）。$b=p_1^{e_1}\cdots p_s^{e_s}$ と素因数分解し、どの $p_i$ も $n$ を割り切るとする。$K:=\max(e_1,\dots,e_s)$ とおくと、$p_i\mid n$ から $p_i^{e_i}\mid n^{e_i}\mid n^K$ である。$p_1^{e_1},\dots,p_s^{e_s}$ はどの 2 つも互いに素なので、その積 $b$ も $n^K$ を割り切る（整数の割り算と互除法）。段 1・2 により $x$ は $K$ 桁以内の有限小数である。$\square$

方針：3 進法で数字 $0$ と $1$ だけを使って書ける $0$ 以上の整数の集合を $T$ とする。$T$ の数どうしの足し算では繰り上がりが起こらないことを使って、$T$ に $x+z=2y$ となる相異なる 3 数がないことを示す。そのうえで $T$ の小さい方から $1983$ 個をとり、全体に $1$ を足す。
段 1（$T$ から $1983$ 個選べる）。$0\le i\le1982$ の整数 $i$ を 2 進法で書き、その数字の並びを 3 進法として読んだ数を $f(i)$ とする。たとえば $i=5=101_{(2)}$ なら $f(5)=101_{(3)}=10$ である。$f(i)$ は $T$ に入る。$i\ne j$ なら 2 進法の数字の並びが違い（thm-bnn-unique）、3 進法として読んだ数も違う（thm-bnn-unique の一意性を 3 進法で使う）ので、$f(0),f(1),\dots,f(1982)$ は $1983$ 個の相異なる数である。
段 2（大きさ）。$1982<2048=2^{11}$ なので、$i\le1982$ は 2 進法で $11$ 桁以下である（prop-bnn-digits）。よって $f(i)$ は 3 進法で $11$ 桁以下の、数字が $0$ か $1$ の数であり
$$ f(i)\le11111111111_{(3)}=1+3+\cdots+3^{10}=\frac{3^{11}-1}2=88573 $$
である。$f(i)+1\le88574\le10^5$ である。
段 3（$T$ の中で $x+z=2y$ なら $x=z$）。$x,y,z\in T$ が $x+z=2y$ をみたすとし、3 進法で $x=\sum x_k3^k$、$y=\sum y_k3^k$、$z=\sum z_k3^k$（$x_k,y_k,z_k\in\{0,1\}$。上の位は $0$ で補って桁をそろえる）と書く。すると
$$ x+z=\sum_k(x_k+z_k)3^k,\qquad 2y=\sum_k2y_k3^k $$
で、$x_k+z_k$ も $2y_k$ も $0,1,2$ のどれかなので、どちらの右辺も 3 進法の表し方になっている（繰り上がりが起こらない）。$x+z=2y$ なので、thm-bnn-unique の一意性により、すべての $k$ で $x_k+z_k=2y_k$ である。右辺は $0$ か $2$ なので、$x_k+z_k$ は $0$（$x_k=z_k=0$）か $2$（$x_k=z_k=1$）で、どちらでも $x_k=z_k$ である。よって $x=z$ である。
段 4（答え）。$A:=\{f(i)+1\mid0\le i\le1982\}$ とする。段 1・2 により、$A$ は $10^5$ 以下の相異なる正の整数 $1983$ 個からなる。$A$ の 3 数 $x+1< y+1< z+1$ が等差数列の連続 3 項なら、$(x+1)+(z+1)=2(y+1)$ から $x+z=2y$ で、段 3 により $x=z$ となり、$x< z$ に反する。よって $A$ のどの 3 個も等差数列の連続 3 項にならない。$\square$