11の倍数判定問題
ICPCアジア地区予選の模擬選があったので、参加資格は無いが問題だけ貰い解いてみた。
その中に11の倍数を判定する問題があったので、
11の倍数というものは10進数表示した整数にどのような特徴で現れるのかを調べてみた。
まず、1桁の場合。
数をと置くと、これが11の倍数であるのは
の場合だけである。
次に、2桁の場合。
数をと置くと、これが11の倍数であるのは
の場合だけである。
更に、3桁の場合。
数をと置く。
直感では分からないので、となるような数を考える。
右辺を展開して整理すると、
左辺と比較すると、
が得られる。
真ん中の式に左右の式を代入してやると、
となる。
つまり、100の位の数と1の位の数の合計が10の位の数となるわけだ。
実際には、が繰り上がりを起こすことがあるため、
とすれば全ての場合に対して正しくなる。
4桁の場合は、説明は省略するけれど
は11の倍数ならが成り立つ。
ここで、
1桁の場合の11の倍数である条件を、 と変形し、
2桁の場合の11の倍数である条件を、 と変形する。
そしてこれを一般化してわかることは、
「任意の整数nが11の倍数である時、nの偶数桁の数字の合計と奇数桁の数字の合計は、11を法として合同である」ということ(証明省略)。
そしてこれは実は必要十分条件であるので(また証明省略)、この命題の逆を取って
「任意の整数nの偶数桁の数字の合計と奇数桁の数字の合計が11を法として合同であるとき、nは11の倍数である」が成り立つ。
こういうこと。
ちなみに、Wikipediaの11のページにちょっと違う形で普通に書いてあった。。