パズル万華鏡

面白いパズルの紹介と解説をします。

ロシア式乗算問題(1)

 ロシア式乗算問題(1)を紹介します。

 

問題(1)

 昔のロシアでは、「2倍すること」,「半分にすること」,「足し算」を用いて2個の正整数a,bを掛け合わせていた。すなわち、

①一方の整数を2で割り、商と余りを求める。他方の数を2倍する。

②この操作を一方の整数が0になるまで続ける。

③最後に、余りが1となったときに対応する他方の整数を合計する。

 たとえば、12×345=4140で、一方の数aを12,他方の数bを
345としたときの計算過程はつぎのようになる。

f:id:isemba:20151003110428j:plain

この方法の正しさを示せ。

f:id:isemba:20151003110440j:plain