足し算カード～不思議な数式の謎 後編
みなさんこんにちは。Calendar Watcherの鈴木です。全二回にわたって自作の数学問題を紹介するシリーズの今回は後編です。問題は「足し算カード」という表と裏に数字が書かれたカードについてのものでした。
今回はその謎を解き明かす回となります。まだ問題に挑戦してないという方は先に前編を見てみてからこちらを見ていただくことをおすすめします。
利用した結果
除算アルゴリズムの定理．任意の整数$${a}$$と正整数$${b}$$に対して，$${a=bq+r, 0 \leq r < b}$$を満たす整数$${q}$$,$${r}$$が一意的に存在する．
結果1．整数$${a}$$および正整数$${b}$$について，$${a}$$を$${b}$$で割った商は$${\lfloor a/b \rfloor}$$に等しい．
定義
任意の整数$${a}$$と正整数$${b}$$に対して，$${a=bq+r, 0 \leq r < b}$$を満たす整数$${q}$$,$${r}$$が一意的に存在します（除算アルゴリズムの定理）．このとき，$${a}$$を$${b}$$で割った商は$${q}$$，余りは$${r}$$であるといいます．
足し算カードの問題.
表1に示された6種類のカードがゲームボード上に置かれています. これらのカードは表と裏に数値が記されており, それぞれのタイプごとに定められた枚数があります. プレイヤーはゲームボード上からカードをランダムに除外することによって, 0枚以上15枚以下の任意の枚数のカードを選びます. 選ばれたカードについて, 表の数値の合計が$${n}$$のとき, 裏の数値の合計が$${n + \left\lfloor \frac{n}{5} \right\rfloor - \left\lfloor \frac{n}{50} \right\rfloor + \left\lfloor \frac{n}{100} \right\rfloor}$$となることを証明してください.
表1:
$$
\begin{array}{c:c:c}
\text{表} & \text{裏} & \text{枚数}\\ \hline
500 & 595 & 1 \\ \hdashline
100 & 119 & 4 \\ \hdashline
50 & 59 & 1 \\ \hdashline
10 & 12 & 4 \\ \hdashline
5 & 6 & 1 \\ \hdashline
1 & 1 & 4 \\
\end{array}
$$
解答
$${n}$$と$${s_i, i=1,2,\ldots,6}$$は整数であって,
(1) $${n=500s_1+100s_2+50s_3+10s_4+5s_5+1s_6}$$.
(2) $${0 \leq s_1 \leq 1, 0 \leq s_2 \leq 4, 0 \leq s_3 \leq 1, 0 \leq s_4 \leq 4, 0 \leq s_5 \leq 1, 0 \leq s_6 \leq 4}$$.
が成り立つとします. 私たちの目標は, このとき
(3) $${595s_1+119s_2+59s_3+12s_4+6s_5+1s_6=n+\left\lfloor \frac{n}{5} \right\rfloor - \left\lfloor \frac{n}{50} \right\rfloor + \left\lfloor \frac{n}{100} \right\rfloor}$$
であることを示すことです.
始めに(1)と(2)から, 補題1により，ある整数$${t_i, i=1,2,\ldots,6}$$によって，
$${n=500s_1+t_1, 0 \leq t_1 < 500}$$,
$${t_1=100s_2+t_2, 0 \leq t_2 < 100}$$,
$${t_2=50s_3+t_3, 0 \leq t_3 < 50}$$,
$${t_3=10s_4+t_4, 0 \leq t_4 < 10}$$,
$${t_4=5s_5+t_5, 0 \leq t_5 < 5}$$,
$${t_5=1s_6+t_6, 0 \leq t_6 < 1}$$
が成立します．するとこのとき, 補題2より(3)が成り立つことが分かります．■
補題1．
任意の整数$${x}$$に対して，$${q_i, i=1,2,\cdots,6}$$を
$${x=500q_1+100q_2+50q_3+10q_4+5q_5+1q_6}$$,
$${0 \leq q_2 \leq 4, 0 \leq q_3 \leq 1, 0 \leq q_4 \leq 4, 0 \leq q_5 \leq 1, 0 \leq q_6 \leq 4}$$
を満たす整数とする．するとこのとき，ある整数$${r_i, i=1,2,\ldots,6}$$により
$${x=500q_1+r_1, 0 \leq r_1 < 500}$$,
$${r_1=100q_2+r_2, 0 \leq r_2 < 100}$$,
$${r_2=50q_3+r_3, 0 \leq r_3 < 50}$$,
$${r_3=10q_4+r_4, 0 \leq r_4 < 10}$$,
$${r_4=5q_5+r_5, 0 \leq r_5 < 5}$$,
$${r_5=1q_6+r_6, 0 \leq r_6 < 1}$$
が成り立つ．
証明
始めに，$${r_1=100q_2+50q_3+10q_4+5q_5+1q_6}$$とおきます．このとき，
$${x=500q_1+100q_2+50q_3+10q_4+5q_5+1q_6=500q_1+r_1}$$
かつ
$${0=100\cdot 0+50\cdot 0+10\cdot 0+5\cdot 0+1\cdot 0 \leq 100q_2+50q_3+10q_4+5q_5+1q_6 \leq 100\cdot 4+50\cdot 1+10\cdot 4+5\cdot 1+1\cdot 4=499 < 500}$$
より, $${0 \leq r_1 < 500}$$となります．
次に，$${r_2=50q_3+10q_4+5q_5+1q_6}$$とおきます．このとき
$${r_1=100q_2+50q_3+10q_4+5q_5+1q_6=100q_2+r_2}$$
かつ
$${0=50\cdot 0+10\cdot 0+5\cdot 0+1\cdot 0 \leq 50q_3+10q_4+5q_5+1q_6 \leq 50\cdot 1+10\cdot 4+5\cdot 1+1\cdot 4=99 < 100}$$
より, $${0 \leq r_2 < 100}$$です．
同様にして，
$${r_3=10q_4+5q_5+1q_6}$$,
$${r_4=5q_5+1q_6}$$,
$${r_5=1q_6}$$,
$${r_6=0}$$
とおくと，このとき
$${r_2=50q_3+r_3, 0 \leq r_3 < 50}$$,
$${r_3=10q_4+r_4, 0 \leq r_4 < 10}$$,
$${r_4=5q_5+r_5, 0 \leq r_5 < 5}$$,
$${r_5=1q_6+r_6, 0 \leq r_6 < 1}$$
であることは容易に示すことができます．■
補題2．
任意の整数$${x}$$に対して，$${q_i, r_i, i=1,2,\cdots,6}$$を，
$${x=500q_1+r_1, 0 \leq r_1 < 500}$$,
$${r_1=100q_2+r_2, 0 \leq r_2 < 100}$$,
$${r_2=50q_3+r_3, 0 \leq r_3 < 50}$$,
$${r_3=10q_4+r_4, 0 \leq r_4 < 10}$$,
$${r_4=5q_5+r_5, 0 \leq r_5 < 5}$$,
$${r_5=1q_6+r_6, 0 \leq r_6 < 1}$$
を満たす整数とする．するとこのとき，
$${595q_1+119q_2+59q_3+12q_4+6q_5+1q_6=x+\left\lfloor \frac{x}{5} \right\rfloor - \left\lfloor \frac{x}{50} \right\rfloor + \left\lfloor \frac{x}{100} \right\rfloor}$$
が成り立つ．
証明
$${o_i, p_i, i=1,2,3}$$を
$${x=100o_1+p_1, 0 \leq p_1 < 100}$$,
$${x=50o_2+p_2, 0 \leq p_2 < 50}$$,
$${x=5o_3+p_3, 0 \leq p_3 < 5}$$
である整数とします．このとき結果1より
$${o_1=\left\lfloor \frac{x}{100} \right\rfloor}$$,
$${o_2=\left\lfloor \frac{x}{50} \right\rfloor}$$,
$${o_3=\left\lfloor \frac{x}{5} \right\rfloor}$$
なので，私たちの目標は
$${(1) 595q_1+119q_2+59q_3+12q_4+6q_5+1q_6=x+o_3-o_2+o_1}$$
を示すことにあります．
ではまず
$${x=500q_1+100q_2+r_2=100(5q_1+1q_2 )+r_2}$$
に注目します．ここで$${5q_1+1q_2}$$, $${r_2}$$は整数であり， $${0 \leq r_2 < 100}$$なので，除算アルゴリズムの定理により$${o_1=5q_1+1q_2}$$, $${p_1=r_2}$$となります．
次に，
$${x=500q_1+100q_2+50q_3+r_3=50(10q_1+2q_2+1q_3 )+r_3}$$
に注目します．ここで$${10q_1+2q_2+1q_3}$$, $${r_3}$$は整数であり，$${0 \leq r_3 < 50}$$なので，除算アルゴリズムの定理により$${o_2=10q_1+2q_2+1q_3}$$, $${p_2=r_3}$$となります．
次に，
$${x=500q_1+100q_2+50q_3+10q_4+5q_5+r_5=5(100q_1+20q_2+10q_3+2q_4+1q_5 )+r_5}$$
に注目します．ここで$${100q_1+20q_2+10q_3+2q_4+1q_5}$$, $${r_5}$$は整数であり，$${0 \leq r_5 < 5}$$なので，除算アルゴリズムの定理により$${o_3=100q_1+20q_2+10q_3+2q_4+1q_5}$$, $${p_3=r_5}$$となります．
したがって，
$${595q_1+119q_2+59q_3+12q_4+6q_5+1q_6=(500+100-10+5) q_1+(100+20-2+1) q_2+(50+10-1) q_3+(10+2) q_4+(5+1) q_5+1q_6}$$
$${=(500q_1+100q_2+50q_3+10q_4+5q_5+1q_6 )+(100q_1+20q_2+10q_3+2q_4+1q_5 )-(10q_1+2q_2+1q_3 )+(5q_1+1q_2 )}$$
$${=x+o_3-o_2+o_1}$$
となり(1)が成立します．■