読者です 読者をやめる 読者になる 読者になる

11の倍数判定問題

ICPCアジア地区予選の模擬選があったので、参加資格は無いが問題だけ貰い解いてみた。
その中に11の倍数を判定する問題があったので、
11の倍数というものは10進数表示した整数にどのような特徴で現れるのかを調べてみた。

 
まず、1桁の場合。
数をa_0と置くと、これが11の倍数であるのは
a_0=0
の場合だけである。
 
次に、2桁の場合。
数を10a_1+a_0と置くと、これが11の倍数であるのは
a_1=a_0
の場合だけである。
 
更に、3桁の場合。
数を100a_2+10a_1+a_0と置く。
直感では分からないので、100a_2+10a_1+a_0=11(10b_1+b_0)となるような数b_1, b_0を考える。
右辺を展開して整理すると、
\,11(10b_1+b_0)\\=110b_1+11b_0\\=100b_1+10b_1+10b_0+b_0\\=100b_1+10(b_1+b_0)+b_0
左辺と比較すると、
b_1=a_2,\,b_1+b_0=a_1,\,b_0=a_0
が得られる。
真ん中の式に左右の式を代入してやると、
a_0+a_2=a_1
となる。
つまり、100の位の数と1の位の数の合計が10の位の数となるわけだ。
実際には、10(b_1+b_0)が繰り上がりを起こすことがあるため、
a_0+a_2\eq a_1\,(mod\,11)とすれば全ての場合に対して正しくなる。
 
4桁の場合は、説明は省略するけれど
1000a_3+100a_2+10a_1+a_0は11の倍数ならa_0+a_2\eq a_1+a_3\,(mod\,11)が成り立つ。
ここで、
1桁の場合の11の倍数である条件を、a_0\eq 0\,(mod\,11) と変形し、
2桁の場合の11の倍数である条件を、a_0\eq a_1\,(mod\,11) と変形する。

そしてこれを一般化してわかることは、
「任意の整数nが11の倍数である時、nの偶数桁の数字の合計と奇数桁の数字の合計は、11を法として合同である」ということ(証明省略)。
そしてこれは実は必要十分条件であるので(また証明省略)、この命題の逆を取って
任意の整数nの偶数桁の数字の合計と奇数桁の数字の合計が11を法として合同であるとき、nは11の倍数である」が成り立つ。
こういうこと。
 
 
ちなみに、Wikipediaの11のページにちょっと違う形で普通に書いてあった。。