第102回 冒険ビット(後編)

「正の数の和が負の数になってしまうというのは……」と僕は言った。
$2$ 進法に興味を持った方は、こちらもどうぞ!
『数学ガールの秘密ノート/整数で遊ぼう』

『数学ガールの秘密ノート/整数で遊ぼう』
『数学ガールの秘密ノート/整数で遊ぼう』(Kindle版)
$ \newcommand{\BIGUL}[1]{\underline{\Large#1}} \newcommand{\SUM}{\displaystyle\sum} \newcommand{\BAR}[1]{\bar{#1}} $
登場人物紹介
:数学が好きな高校生。
ユーリのいとこの中学生。のことを《お兄ちゃん》と呼ぶ。

$-2$ 進数

$2$ 進数の話をしているとき、 ユーリが言い出した《 $-2$ 進数(マイナスにしんすう)》に話が発展して……(第101回の続き)。

ユーリ「ぐちゃぐちゃじゃん!」

「いや、少し考えればわかるよ……こうかな」

$-2$ 進数で数を表したらどうなるか
$$ \begin{array}{rrl} \text{ $-2$ 進数} & \text{ $10$ 進数} & \text{メモ} \\ \hline 0 & 0 & \\ 1 & 1 & \\ 110 & 2 & \text{ $(-2)^2 = 4$ に、負数 $(-2)^1 = -2$ を加える} \\ 111 & 3 & \text{ $2$ に $1$ 加える} \\ 100 & 4 & \text{ $(-2)^2 = 4$ } \\ 101 & 5 & \text{ $4$ に $1$ 加える} \\ 11010 & 6 & \text{ $(-2)^4 = 16$ に、負数 $(-2)^3 = -8$ と $(-2)^1 = -2$ を加える} \\ 11011 & 7 & \text{ $6$ に $1$ 加える} \\ \vdots & \vdots & \vdots \\ \end{array} $$

ユーリ「あれ……お兄ちゃん! パターンが見える! ほらほら、縦読みすれば!」

「ほんとだ! よし、もっと先まで書いてみようか」

そのとき玄関のベルが鳴り、少ししてがやってきた。

「ミルカさんと、もう一人、お友達がいらしたわよ」

「ミルカさん!」

ユーリ「ミルカさま!」

ミルカ「今日はリサを連れてきた」

リサ「……」

リサミルカさんの親戚で、僕たちの後輩にあたる。 無造作に切った赤い髪。 彼女はいつも真っ赤なノートブック・コンピュータを持ち歩いている。

ミルカ「君の家に来たがったのはリサなんだが。来たくてしょうがないと」

「え?」

リサ「誇張」

登場人物紹介(追加)
ミルカさん:数学が好きな高校生。のクラスメート。長い黒髪の《饒舌才媛》。
リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。

ミルカ「今日は何を?」

ユーリ「マイナス $2$ 進数です、ミルカさま」

ミルカ「ふうん……楽しそうだな」

リサ「 $-2$ 進数?」

「いま、 $-2$ 進数と $10$ 進数の対応表を作ろうとしていたんだ」

リサ「手で?」

「『手で?』ってどういう意味?」

ミルカ「リサは、プログラムでできると言いたいんだよ」

「ああ、そうか。リサちゃんならコンピュータでできるんだ!」

リサ「《ちゃん》は不要」

「リサはプログラム得意だからなあ」

リサ「どこまで?」

ミルカ「切りの良いところまで」

リサ「それなら、 $256$ まで」

リサは軽く咳をしてから、コンピュータのキーボードを叩く。 ほどなくして一覧表を作り出した。
$-2$ 進数と $10$ 進数の対応表

ユーリ「ふへー……リサさんってすごいんですね」

リサ「《さん》も不要」

ユーリ「お兄ちゃん、 $-2$ 進数のパターンが見えるよ。縦読み縦読み!」

「うん。 $(-2)^0$ の位、つまり $1$ の位は縦読みで $0,1,0,1,0,1\ldots$ というパターン」

ユーリ「 $(-2)^1$ の位は、 $1,1,0,0,1,1,0,0,\ldots$ だね!  $1,1$ と $0,0$ がかわりばんこ」

「それから $(-2)^2$ の位、つまり $4$ の位は $1,1,1,1$ と $0,0,0,0$ が交互に来る」

ユーリ「下から四桁目の $(-2)^3$ の位は、 $1$ が $8$ 個と、 $0$ が $8$ 個がかわりばんこ」

「 $(-2)^4$ の位は、 $1$ が $16$ 個と、 $0$ が $16$ 個……もう一般化できるなあ」

《 $-2$ 進数のパターン》
$(-2)^k$ の位を縦読みすると、 《 $1$ が $2^k$ 個》と《 $0$ が $2^k$ 個》が交互に現れる。
ただし、 $k = 0,1,2,\ldots$ とする。

桁の増加

ミルカ「桁の増加にもパターンが見える」

ユーリ「そーそー! ユーリ気付いてたよ! 桁が増えるときって、必ず $2$ 桁ずつ増えるの。しかも、増える数字は必ず $11$ で。 そしてしばらく進むと、そこんとこが $10$ に変わる」

$$ \begin{array}{rrl} 0 & 0 & \\ 1 & 1 & \\ 110 & 2 & \text{ $11$ が増えた} \\ 111 & 3 & \\ 100 & 4 & \text{ $10$ に変わった} \\ 101 & 5 & \\ 11010 & 6 & \text{ $11$ が増えた} \\ 11011 & 7 & \\ 11000 & 8 & \\ 11001 & 9 & \\ 11110 & 10 & \\ 11111 & 11 & \\ 11100 & 12 & \\ 11101 & 13 & \\ 10010 & 14 & \text{ $10$ に変わった} \\ 10011 & 15 & \\ 10000 & 16 & \\ 10001 & 17 & \\ 10110 & 18 & \\ 10111 & 19 & \\ 10100 & 20 & \\ 10101 & 21 & \\ \vdots & \vdots & \\ \end{array} $$

「縦読みしたときに交互になるという意味では、 $2$ 進数のパターンと少し似ているところもあるけど、 $2$ 進数と $-2$ 進数ではまったく違うなあ」

ミルカ「まったく違うだろうか?」

「え?」

ミルカ「たとえば $0$ や $1$ を考えると、 $2$ 進法で表記しても $-2$ 進法で表記しても同じだ」

「そりゃそうだけど」

ユーリ「 $4$ も! 両方 $100$ になる!」

ミルカ「では問題」

問題1
$n$ は $0$ 以上の整数とする。
$n$ を $2$ 進法で表記した場合と、 $-2$ 進法で表記した場合に、 同じ表記になるのはどんなときか。 $n$ についての条件を求めよ。

「……」

ユーリ「……」

「そうか……もしかすると、 $4$ の冪乗?」

リサ「できた」

ミルカ「プログラムで表を作っても、条件を求めたとはいえない」

リサ「なぜ」

ミルカ「たとえば、『 $n = 341$ のとき、 $2$ 進法と $-2$ 進法で表記が同じになるか?』 という問いに答えられないから」

リサ「表を $341$ までに」

ミルカ「ならば $n = 1501199875790165$ のときは? 切りがない」

「表を作り直さなくても、 $341$ や、その……すごく大きな数の表記を調べるだけでいいよね」

ミルカ「プログラムで確かめられたとしても、条件を求めるのは別の話」

「ところで、条件は見つかったよ。《 $n$ が $4$ の冪乗の和で表されること》が求める条件だ」

ミルカ「正解」

ユーリ「 $4$ のべきじょうの……わ?」

「 $4^0, 4^1, 4^2, 4^3, \ldots$ つまり $4^k$ の形で表される数を何個か選ぶんだよ。そしてそれらを足し合わせる。 たとえば、 $4^0$ と $4^2$ を選んだとする。 そうすると、 $4^0 + 4^2 = 1 + 16 = 17$ だよね。 リサが作ってくれた表を見ると、確かに $17$ は同じ表記になっている」

リサ「 $17$ 確認完了 $10001$ 」

ユーリ「でも、なんで? どっから $4$ が出てきたの?」

「 $4 = (-2)^2$ だよ。ほら、 $-2$ 進数を一般的に書いた式があるよね。あれでわかった」

ユーリ「へー」

「 $2$ 進数と $-2$ 進数を一般的に書いてみるとこうなる」

$2$ 進数
$$ a_{n-1}2^{n-1} + \cdots + a_32^3 + a_22^2 + a_12^1 + a_02^0 $$
$-2$ 進数
$$ a_{n-1}(-2)^{n-1} + \cdots + a_3(-2)^3 + a_2(-2)^2 + a_1(-2)^1 + a_0(-2)^0 $$

ユーリ「ぜんぜん違うじゃん」

「いやいや、 $k$ が偶数のとき、 $(-2)^k$ は、 $2^k$ に等しいよね。 だから、並べて書いてみると……」

$$ \begin{array}{cccccccccccccc} \text{ $2$ 進数} & \cdots &+& a_32^3 &+& a_22^2 &+& a_12^1 &+& a_02^0 \\ \text{ $-2$ 進数} & \cdots &+& a_3(-2)^3 &+& a_22^2 &+& a_1(-2)^1 &+& a_02^0 \\ \end{array} $$

ユーリ「そっか!  $2$ の偶数乗っていうのは、 $4$ の冪乗?」

「そうそう。 $4$ の冪乗をいくつか集めて作った和というのは、《 $2^{\text{偶数}}$ の位》にしか $1$ がない数になる。 そしてそういう数は $2$ 進法と $-2$ 進法で等しくなるんだね」

ミルカ「正解」

解答1
$n$ は $0$ 以上の整数とする。
$n$ を $2$ 進法で表記した場合と、 $-2$ 進法で表記した場合に、 同じ表記になる条件は、 $n$ が $4$ の冪乗の和で表されることである。

リサ「条件……」(咳)

ユーリ「 $-2$ 進数の表を作るプログラムって、どんなの……どんなものですか、リサさん?」

リサ「《さん》は不要」

リサはコンピュータのディスプレイを向ける。
この続きは有料会員登録をすると
読むことができます。
cakes・note会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の女子高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わってください。本シリーズはすでに何冊も書籍化されている人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

aramisakihime 初読時は途中で置いてけぼりに…。2回めでようやく把握できました。 > 3年以上前 replyretweetfavorite

chibio6 やっと最後まで読んだ(途中の理解が若干あやしいけど)。無限大だと思えるものが0だとは、すぐには理解しがたい。 3年以上前 replyretweetfavorite

shiano_blue リサとミルカさんが来てからわからなくなって…。 3年以上前 replyretweetfavorite

shtd18 途中で置いてけぼりくらった…(´・_・`) 3年以上前 replyretweetfavorite