1982年(昭和57年)東京大学-数学(文科)[4] - [別館]球面倶楽部零八式markIISR

2023.08.23記

[4] $A=\begin{pmatrix} \dfrac{1}{2} & -\dfrac{1}{2} \\ 0 & 1 \end{pmatrix}$ ， $B=\begin{pmatrix} 1 & 0 \\ -\dfrac{1}{2} & \dfrac{1}{2} \end{pmatrix}$ とおく． $xy$ 平面において， $(1,1)$ を座標とする点 $\mbox{P}_0$ から始めて，点列 $\mbox{P}_0$ ， $\mbox{P}_1$ ， $\mbox{P}_2$ ，…，をつぎのような手続きで作っていく． $\mbox{P}_n$ の座標を $(x_n,y_n)$ とするとき，

(イ) $x_n+y_n\geqq\dfrac{1}{100}$ のときは， $(x_{n+1},y_{n+1})$ を $\begin{pmatrix} x_{n+1} \\ y_{n+1}\end{pmatrix}=A\begin{pmatrix} x_n \\ y_n\end{pmatrix}$ または $\begin{pmatrix} x_{n+1} \\ y_{n+1}\end{pmatrix}=B\begin{pmatrix} x_n \\ y_n\end{pmatrix}$ のどちらかが成りたつように決める．

(ロ) $x_n+y_n\lt \dfrac{1}{100}$ のときは， $(x_{n+1},y_{n+1})$ を $\begin{pmatrix} x_{n+1}\\y_{n+1}\end{pmatrix}=A\begin{pmatrix} x_n\\y_n\end{pmatrix}$ によって決める．

このようにするといろいろな点列ができるが，それらについてつぎの問に答えよ．

(1) $\mbox{P}_2$ として可能な点をすべて求め，図示せよ．

(2) $x_n+y_n$ を $n$ で表わせ．

(3) $\mbox{P}_{10}$ として可能な点は何個あるか．

本問のテーマ

2進法(2023.08.23)

2020.11.27記

（2023.08.23追記
$y_1=1,0$ ，
$y_2=1,\dfrac12,0,-\dfrac12$ ，
$y_2=1,\dfrac{3}{4},\dfrac12,\dfrac14,0,-\dfrac14,-\dfrac12,-\dfrac{3}{4}$ ，
となるので $2^{n-1}y_n=Y_n$ は
$Y_1=1$ ，
$Y_2=2,1,0,-1$ ，
$Y_3=4,3,2,1,0,-1,-2,-3$
となる．よって，）

$X_n=2^{n-1}x_n$ ， $Y_n=2^{n-1}Y_n$ とおくと簡単になる．
多くの解答では(3)の論証が難しいと書いてあるが上記の置き換えだとそんなに難しくない．

[解答]
(1) $\begin{pmatrix} x_1 \\ y_1 \end{pmatrix}=\begin{pmatrix} 0 \\ 1 \end{pmatrix}，\begin{pmatrix} 1 \\ 0 \end{pmatrix}$ により
$\begin{pmatrix} x_2 \\ y_2 \end{pmatrix}=\dfrac{1}{2}\begin{pmatrix} -1 \\ 2 \end{pmatrix}$ ， $\dfrac{1}{2}\begin{pmatrix} 0 \\ 1 \end{pmatrix}，\dfrac{1}{2}\begin{pmatrix} 1 \\ 0 \end{pmatrix}，\dfrac{1}{2}\begin{pmatrix} 2 \\ -1 \end{pmatrix}$

(2) $\begin{pmatrix} x_{n+1} \\ y_{n+1} \end{pmatrix}=\dfrac{1}{2}\begin{pmatrix} x_n-y_n \\ 2y_n \end{pmatrix}$ または $\dfrac{1}{2}\begin{pmatrix} 2x_n \\ -x_n+y_n \end{pmatrix}$ だから，いずれにせよ
$x_{n+1}+y_{n+1}=\dfrac{1}{2}(x_n+y_n)$
となり， $x_1+y_1=2$ から $x_n+y_n=\dfrac{1}{2^{n-1}}$

(3) $X_n=2^{n-1}x_n$ ， $Y_n=2^{n-1}y_n$ とおくと $X_n+Y_n=1$ で $Y_n$ と $\begin{pmatrix} X_{n} \\ Y_{n} \end{pmatrix}$ は一対一に対応するので， $Y_n$ の個数を数えれば良い．

ここで $Y_0=\dfrac{1}{2}$ で整数ではないので， $Y_1=0$ または $1$ から出発して考える．

$X_n+Y_n \geqq \dfrac{2^{n-1}}{100}$ ，つまり $1\leqq n\leqq 7$ のとき，
$Y_{n+1}=2Y_n$ または $2Y_n-1$ であり，
$2Y_n$ ， $2Y_n-1$ の奇遇は異なるから， ${\rm P}_{n+1}$ として可能な点の個数は ${\rm P}_{n}$ として可能な点の個数の丁度2倍になる．

$X_n+Y_n \lt \dfrac{2^{n-1}}{100}$ ，つまり $n\geqq 8$ のとき，
$Y_{n+1}=Y_n$ であるから， ${\rm P}_{n+1}$ として可能な点の個数は ${\rm P}_{n}$ として可能な点の個数と同じになる．

よって， ${\rm P}_{10}$ として可能な点の個数は ${\rm P}_{8}$ として可能な点の個数と等しく， ${\rm P}_{1}$ として可能な点の個数 $2$ の $2^7$ 倍の $2^8=256$ 個
（ $Y_8$ となりうるのは $-127$ 以上 $128$ 以下の256個の整数）

2023.08.23記
[解答] の議論をより精密にするには

$Y_n$ （ $1\leqq n\leqq 8$ ）のとり得る値は $-2^{n-1}+1\leqq N\leqq2^{n-1}$ なる全ての整数であることを帰納法で示せば良い．

$Y_1=1$ はOK
$Y_k$ でOKのとき
$2Y_k$ は $-2^{k}+2\leqq N\leqq2^{k}$ なる全ての偶数，
$2Y_k-1$ は $-2^{k}-1\leqq N\leqq2^{k}-1$ なる全ての奇数
となりうるので， $Y_k$ は $-2^{k}-1+2\leqq N\leqq2^{k}$ なる全ての整数となりうる．

ということになる．

[解答]では $Y_n$ を数えたが， $X_n+Y_n=1$ のペアである $Z_n=X_n-Y_n$ を数えても良い．このとき $Z_n$ は $-2^{n+1}+1$ から $2^{n+1}-1$ の全ての奇数をとり得ることになる．

[別解]
(3) $X_n=2^{n-1}x_n$ ， $Y_n=2^{n-1}y_n$ とおくと $X_n+Y_n=1$ で $Z_n=X_n-Y_n$ と $\begin{pmatrix} X_{n} \\ Y_{n} \end{pmatrix}$ は一対一に対応するので， $Z_n$ の個数を数えれば良い．

ここで $Z_0=0$ であり，
$\begin{pmatrix} X_{n+1} \\ Y_{n+1} \end{pmatrix}=\begin{pmatrix} X_n-Y_n \\ 2Y_n \end{pmatrix}$ または $\begin{pmatrix} 2X_n \\ -X_n+Y_n \end{pmatrix}$ だから，
$X_n=\dfrac{1+Z_n}{2}$ ， $Y_n=\dfrac{1-Z_n}{2}$
により，
$Z_{n+1}=X_n-3Y_n=2Z_n-1$ 　または $2Z_n+1$
となる．

$X_n+Y_n \geqq \dfrac{2^{n-1}}{100}$ ，つまり $1\leqq n\leqq 7$ のとき，
$Z_{n+1}=2Z_n\pm 1$ ， $Z_0=0$
から，帰納的に
$Z_{n+1}$ は $-2^{n+1}+1$ から $2^{n+1}-1$ までの任意の奇数となり得るので， $2^{n+1}$ 個の値をとり得る．

$X_n+Y_n \lt \dfrac{2^{n-1}}{100}$ ，つまり $n\geqq 8$ のとき，
$Z_{n+1}=2Z_n-1$ であるから， ${\rm P}_{n+1}$ として可能な点の個数は ${\rm P}_{n}$ として可能な点の個数と同じになる．

よって， ${\rm P}_{10}$ として可能な点の個数は ${\rm P}_{8}$ として可能な点の個数と等しく， $2^8=256$ 個

$Y_{n+1}=2Y_n$ または $2Y_n-1$ から2進数が想起される．これを
$W_{n+1}=2W_n$ または $2W_n+1$ となるように工夫すると負の2進数が登場しなくなって良い．

[うまい解答]
（[解答]の途中から）
$W_n=Y_n+2^{n}-1$ とおくと
$W_0=1$ ， $W_{n+1}=2W_n+1$ または $2W_n$
が成立する．2進数で考えると， $W_{n+1}=2W_n+1$ または $2W_n$ は末尾に1または0の数字を追加することに相当する

$X_n+Y_n \geqq \dfrac{2^{n-1}}{100}$ ，つまり $1\leqq n\leqq 7$ のとき，
2進数で考えると， $W_{n+1}=2W_n+1$ または $2W_n$ は末尾に1または0の数字を追加することから，
${\rm P}_{n+1}$ として可能な点の個数は ${\rm P}_{n}$ として可能な点の個数の丁度2倍になる．

$X_n+Y_n \lt \dfrac{2^{n-1}}{100}$ ，つまり $n\geqq 8$ のとき，
2進数で考えると， $W_{n+1}=2W_n+1$ は末尾に1を追加することから，
${\rm P}_{n+1}$ として可能な点の個数は ${\rm P}_{n}$ として可能な点の個数と同じになる．

よって， ${\rm P}_{10}$ として可能な点の個数は ${\rm P}_{8}$ として可能な点の個数と等しく， ${\rm P}_{1}$ として可能な点の個数 $2$ の $2^7$ 倍の $2^8=256$ 個

$W_{10}$ として可能な数は，2進数で表現すると 11桁の2進数で、最上位と下2桁が1であるものとなり，
$4k+2051$ （ $0\leqq k\leqq 255$ ）
となる．