11の倍数 - てきとうなメモ

11の倍数は1の位，100の位，．．．と奇数桁(こう呼ぶのかどうかは良く知らない)を足したものと10の位，1000の位，．．．と偶数桁を足したものの差が11の倍数であるらしい．なぜそうなるかを考えてみる．

ある数aが11の倍数であるとする．11の倍数は
$b \times 10 + b \times 1$
と表せる．これは，筆算を行うときのイメージで，bとbを左に1つずらした数との足し算を表す．bの各桁を数列{b_i}で
$b_n b_{n-1} \cdots b_3 b_2 b_1$
のように表すとし，aも数列{a_i}で表すと，

$a_{i} = b_1 \text{ if } i = 1$
$a_{i} = b_i + b_{i-1} + c_i - d_i \text{ if } 1 \lt i \lt n+1$
$a_{i} = b_n \text{ if } i = n+1$

ここで，c_iは一つ下の位からの繰り上げを表す．
$c_{i} = 1 \text{ if } b_{i-1} + b_{i-2} + c_{i-1} \geq 10 \text{ and } i \gt 2$
$c_{i} = 0 \text{ otherwise }$

また，d_iは足し算が10以上になると1の位のみにしなければならないので引かれる10を表す．
$d_{i} = 10 \text{ if } b_i + b_{i-1} + c_i \geq 10 \text{ and } 1 \lt i \leq n$
$d_{i} = 0 \text{ otherwise }$

まず，どの桁の計算でも繰り上げが全くかからない場合は，c_i=0かつd_i=0なので，
$sum_{odd} = \sum_{\text{i is odd}}^{n}a_{i} = a_1 + (a_3 + a_2) + (a_5 + a_4) + \cdots + a_n = \sum_{i}^{n}a_i$
$sum_{even} = \sum_{\text{i is even}}^{n}a_{i} = (a_2 + a_1) + (a_4 + a_3) + \cdots + a_n = \sum_{i}^{n}a_i$
となり
$sum_{odd} - sum_{even} = 0$
で11の倍数になる．

繰り上がりがある場合はやや複雑になるが，奇数桁でのc_iは1つ下の偶数桁で繰り上がりがあった場合のみ1加算され，d_iは奇数桁自身に繰り上がりがあった時のみ10引かれる．そのため，奇数桁での繰り上がり回数をe，偶数桁での繰り上がり回数をfとすると
$sum_{odd} = \sum_{i}^{n}a_i + f - 10 \times e$
$sum_{even} = \sum_{i}^{n}a_i + e - 10 \times f$

よって
$sum_{even} - sum_{odd} = 11(e-f)$
で11の倍数になる．