概要

概要は（１）を御覧ください。

比較的かんたんな「あまり」の求め方

【数を並べた表】を斜めマス移動で登る方法の一般化

ここまでやってきたことを、【数を並べた表】 ―― $N$ で割り切れる数を [tex: 10^k] 区切りで並べた表―― を上へ上へと登っていく、という方法で見直してみよう。

またも細かい図だが、 $N=2,5,4,8,3,9,11$ の場合の表が、以下のようになる。

これまでは、割り切れる数(表の薄緑で強調した数)の並びを利用して、エスカレーター式に上に上がっていったり、斜め 1 マスずつで上がっていくことができた。

そして、次に挑もうとしている、 $N=7$ の【数を並べた表】を見直してみよう。

エスカレーター方式は通用しないし、斜めに登る方法も 3 桁区切りでしか使えない。しかし、斜め 1 マスずつではないにしても、特定の規則で斜めに綺麗に並んでいるのは確かなのだ。これを利用できないだろうか？

ONLY UP!: 【一番上の位から消す】編

ONLY UP! とは、最近流行りのハイストレス系ジャンプアクションゲームの一種である。同じ系統のゲームとしては、 Getting Over It (通称:壺おじ)や Jump Kingがある。今回の【数を並べた表】を登る行為とも一種の似たものを感じる (上手く登れる方法を見つけたと思ったら、一般化できてないことの連続だった)。

閑話休題。

そもそも、【数を並べた表】のマス目を移動するとはどういうことだろうか？ 10 ずつ数字を並べた場合を考えてみよう。マス目の移動の仕方は無限にパターンがあるが、最小の移動だけ考えると、次の4パターンに分けられる。

上に移動: 元の数から 10 引く。
左に移動: 元の数から 1 引く。
下に移動: 元の数に 10 足す。
右に移動: 元の数に 1 足す。

以下のようで図で見ると分かりやすい。

斜め移動を除けば、基本の移動パターンは 4 通りだ。そして、今回は数を小さくする方向に進みたいから、とりあえず下方向は無視していい。というわけで、上・左・右の 3 パターンを組み合わせて、 数が規則的な並び方(= $N$ で割り切れる規則)から外れないように、 表を上へ上へと登っていけばいい。

7 の並びの規則と登り方

では、 7 の並びの規則はどうなっているだろうか？一番基本的な並び方は、以下に図に見られるような、 $14\rightarrow{}7$ だろう。

つまり、上移動 1 回、右移動 3 回のパターンが見られる。計算の観点では、この移動は「10 の位を 1 減らそうと思うと、 1 の位を 3 増やさないといけない」という意味になる。

そして、これを繰り返すことで、表の上に登ること―― 10 の位を消すことを考えよう。 10の位の数が $a$ のとき、「 $a\times{}3$ だけ1の位を増やせば、10の位を消せる」ということになる。

つまり、どんな二桁の数についても、この方法で表の一番上にたどり着くことができる。例えば、

26 なら $2\times{}3+6=12\rightarrow{}1\times{}3*2=5$ 、
51 なら $5\times{}3+1=16\rightarrow{}1\times{}3+6=9=7+2$ 、

といったような形だ。

この方法で、最上位二桁を一桁に変換することを繰り返せば、いつかは一桁の数字になる。前に扱った例として、413,352,289 をもう一度見てみよう。

$4\times{} 3 + 1 = 13 \rightarrow{} 6$
$6\times{} 3 + 3 = 21 \rightarrow{} 0$
$0\times{} 3 + 3 = 3$
$3\times{} 3 + 5 = 14 \rightarrow{} 0$
$0\times{} 3 + 2 = 2$
$2\times{} 3 + 2 = 8 \rightarrow{} 1$
$1\times{} 3 + 8 = 11 \rightarrow{} 4$
$4\times{} 3 + 9 = 21 \rightarrow{} 0$

こうして、表を上へ上へと登っていく方法として、 7 で割り切れるかどうかの判定法 (2) が正しいことが分かった。

7 で割り切れるかどうかは、上の位から順番に、「一番上の位(の7の余り)の3倍と次の位の数を足して余りを求める」ことを繰り返す。これが最終的に 0 になると、 7 で割り切れる。

(正確には「正しそう」レベル。ちゃんと証明したい人はがんばってください。)

並びの規則と登り方の一般化

ここでは、方式を一般化しておこう。先程までは 7 で割り切れるかどうかを見てきたが、ここからは $N$ で割りきれるかどうかを見ていくことにする。 7 で割り切れるかどうかの判定法を導く工程を見直しながら、一般化を試みてみよう。

まず、先程は何も考えずに 7 と 14 を見て、「上移動 1 回、右移動 3 回のパターンが見られる」などと言ったが、 このパターンはどうやったら発見できるだろうか？

まず、後で計算するときのことを考えると、上移動は 1 回である方が楽だ。というのも、「一番上の位を消す」ということを考えたとき、上移動が 2 回以上のパターンを考えると、上移動で表の一番上を飛び越してしまう場合が出てくるからだ。ということは、「上移動 1 回、右移動 $x$ 回」という移動パターンが見られると、特殊ケースを考えなくていいので楽ということになる。

しかし、先程までは 7 という数字を考えていたが、例えば 19 という数字は、 19 の次は 38 だ。 19 と 38 の間で 10 の位は 20 離れているので、上移動を 2 回しなければいけないのではないか？

そうならないように、 10 ずつ並べていた方を調整しよう。 10 ずつ並べる代わりに、 $(k+1)$ 桁の 100...0 の形をした数([tex: =10^k]) ずつ並べることを考える。

100...0 の桁数の選び方は $N$ を超えるように選ぶ。例えば、以下のような形だ。

7 < 10 なので、 10 ずつ並べる ( $k=1$ )
19 < 100 なので、 100 ずつ並べる ( $k=2$ )

では、こう考えた上で、「上移動 1 回、右移動 $x$ 回」の $x$ をいくつにすればいいかを考えよう。

7 については 7 と 14 を見たが、これを一般化できないだろうか？例えば、数の並べ方を、一番右上に 0 が来るように拡張して、下の図のように並べてみる。すると、 7 は 0 の位置から 3 だけ左に行ったところに、 7 があることに気づく。

では、この 3 という数字はなんだろうか？　(図の中に答えが書いてあるが。) これは、 10 から 7 までの距離なのだから、言い換えれば、 10 を 7 で割った余りであると言える。実際、図中の $mod(a, b)$ というのは、「 $a$ を $b$ で割った余り」を表す数式である。 10 を 7 で割った余りは 3 だから、 10 から 3 だけ戻った数は 7 の倍数(というか 7 自身)になる。

これを一般化すると、先ほど決めた 100...0 から $N$ までの距離、つまり、 100...0 を $N$ で割った余り $R$ が、右方向の移動距離と考えて良さそうだ。例えば、 $N=19$ の場合に 100 ずつ並べたときは、 $100=19*5+5$ なので、 $R=mod(100,19)=5$ である。なので、「上移動 1 回、右移動 5 回」という移動パターンなら、 19 の倍数の並び方の規則を満たす。

というわけで、数字を 100...0 ずつ並べたとき、 $N$ で割り切れる数を眺めてみると、「上移動 1 回、右移動 $R$ 回」という移動パターンが見られるという事実を一般化したのが、下の図だ。

この【数を並べた表】では、上移動は、 $(k+1)$ 桁の数 100...0 を引くことに相当する。そして、 100...0 を $N$ で割った余り $R$ だけ足すと、 $N$ の倍数の並び方の規則を満たしながら移動することができる。

実践例 (ONLY UP!編)

13 で割り切れるか

例えば、 292,768,112 を、 13 で割れるかを確かめてみよう。

ここでは、 100 ずつ並べた【数を並べた表】を考える (図示はしない)。 100 を 13 割った余り $R$ は以下の通り、 9 になる。

$100 = 91 + 9 = 13\times 7 +9$ なので、 $R=9$

表を 100 ずつ並べたので、最上位桁は 100 の倍数ではないといけない。なので、 3 桁( $(k+1)桁$ )を取ってきて、

$292 \rightarrow 2 \times 9 + 92 = 110 \rightarrow{} 1 \times 9 + 10 = 19 = 13 + 6$

というわけで、上位 3 桁を 6 にできた。

同じように、 3 桁以上になるように注意しながら数を後ろに補充しながら計算を繰り返すと、以下のようになる。

76 を補充: $6 \times 9 + 76 = 130 \rightarrow{} 1 \times 9 + 30 = 39 = 13 \times 3 + 0$
811 を補充: $8 \times 9 + 11 = 83$
2 を補充: $8 \times 9 + 32 = 72 + 32 = 104 \rightarrow{} 1 \times 9 + 4 = 13$