log dead field

[PR]

2024/04/26 (Fri.)

mをnで割った余りは必ず0, 1, 2, …, n - 1のいずれかになる

  ことを証明するにはどうすればよいか？ ただし m，n は整数で m > n > 0 とする。

  こないだ非常勤バイトでrand関数を扱ったときの話。C言語のrand関数は、呼び出す度に0～32768までの整数をランダムに（厳密には与えられた乱数表のとおりに）返してくれるわけですが、これをサイコロの目、1～6の範囲に収めたい。そこで返された値を6で割った余りを使います。どんな整数でも6で割った余りは必ず0～5になるので、それに1を足して使えばいいというわけ。rand関数を使う場合はほとんどこの方法で範囲をノルマライズします。コードにするとrand( ) % 6 + 1っちゅう感じ。


  しかしある一人の生徒、どうしてもこの理屈が腑に落ちない様子。

生徒「このrand( ) % 6 + 1って何ですか」
ボク「（さっき説明したじゃろうが…） これは“randが返した値を6で割った あ ま り” に1を足すってことさ、これで1～6の値が得られる」
生徒「なんで1～6になるんですか」
ボク「だってrand( )を6で割ったらその余りは絶対0～5になるじゃろ、まずここまでは認める？」
生徒「認めません」
ボク「えぇっ！？ これはそういうもんなんだって！ 実際に計算してみればわかる」

ここでホワイトボード上にてランダムな数を6で割る筆算を2例ほどしてみる。

ボク「ほら、必ず0～5になる。どんな数でも6で割った余りは必ず0～5のいずれか」
生徒「どんな数でもですか」
ボク「もちろん」
生徒「ほんとですか、証明してください」
ボク「えぇっ！？ しょ証明は…いきなりはちょっと…勘弁してつかさいｸﾋﾋｰ」

逃げました。ボクは数論は苦手なんだ。数論というか数学自体苦手だけど。


  でも逃げっぱなしではいかん、証明してみましょう。
m，n （m > n） を0でない任意の整数としたとき、m ÷ n = q，余りrだったとする。q と r ももちろん整数。
このとき r ∈ { 0, 1, 2, ..., n - 1 } であるか？ （あるいは 0 ≦ r ≦ n - 1 であるか？と書いてもよい）

まず m ÷ n = q 余り r より nq ≦ m < n (q + 1)  …(1) と言えるよね。割り算てそういうもんだから。（←すでに飛躍？） たとえば 13 ÷ 3 ならば 商は 4、余りは 1。実際 3 × 4 ≦ 13 < 3 × (4 + 1) 。
で、 r = m - nq …(2)だよね。たとえば上の例なら実際 1 = 13 - 3 × 4 。
ここで(1)よりnq ≦ m 、ゆえに m - nq ≧ 0 。よって(2)より r ≧ 0 。これで第1関門突破。

では r ≦ n - 1 はどうしたら言えるか？ 
(2)より m = r + nq 、これを(1)に代入すると r + nq ≦ n (q + 1) 。よって r < nq + n - nq = n 、すなわち r < n だからr ≦ n - 1 。
r ≧ 0 かつ r ≦ n - 1 だから 0 ≦ r ≦ n - 1 。おしまい。


  ……こんなんで大丈夫かなぁ？ やはりそもそも(1)に飛躍があるか。これ認めさせるのは、結論をそのまま認めさせるのと同じな気がする。しかも途中で気づいたんですが、「どんな数でもnで割ったら…」じゃなくて「nより大きい数はnで割ったら…」ですよね。だからさりげなくm > nって書いてあるけど、これは重要。前提条件がそもそも間違ってた（というか穴があった）わけですよ。てかこれって整数じゃなく自然数に限定しないともっとめんどくさいことになるんですかね？ ああ！ 頭が爆発しそうだ。

2009/11/02 (Mon.) Trackback() Comment(3) 大学院・研究生活