| For All Solvers
OMC209 (for beginners)

OMC209(C) - 解説補足

ユーザー解説 by zplc

　より正確には，組 (x1,x2,x3,x4)∈{−6,0,6}4(x_1, x_2, x_3, x_4) \in \{-6, 0, 6\}^4 が異なれば x1+10x2+100x3+1000x4x_1 + 10x_2 + 100 x_3 + 1000 x_4 の値も異なることを示さなければいけません．これを示すことを目標にします．

ヒント 　対偶を取って，以下を示せばよいですね．ここで，xi,yix_i, y_i がすべて {6,0,−6}\{6, 0, -6\} の元であることを仮定しています． x1+10x2+100x3+1000x4=y1+10y2+100y3+1000y4　  ⟹  　(x1,x2,x3,x4)=(y1,y2,y3,y4)x_1 + 10x_2 + 100 x_3 + 1000 x_4 = y_1 + 10y_2 + 100 y_3 + 1000 y_4　\implies　(x_1, x_2, x_3, x_4) = (y_1, y_2, y_3, y_4) 「順番に見ていく」というのがヒントです．より具体的には，〇〇の位から見ていくと示せます．

解答 　「ヒント」タブの命題を，一般に nn 変数の場合で証明しよう．すなわち，x1,x2,⋯ ,xn,y1,y2,⋯ ,yn∈{−6,0,6}x_1, x_2, \cdots, x_n, y_1, y_2, \cdots , y_n \in \{-6, 0, 6\} について，以下の命題： x1+10x2+⋯+10n−1xn=y1+10y2+⋯+10n−1yn　  ⟹  　(x1,x2,⋯ ,xn)=(y1,y2,⋯ ,yn)x_1 + 10x_2 + \cdots + 10^{n-1} x_{n} =y_1 + 10y_2 + \cdots + 10^{n-1} y_{n}　\implies　(x_1, x_2, \cdots, x_n) = (y_1, y_2, \cdots , y_n) を示そう．n=1n=1 の場合は示すべきことはない．
　n=kn=k の場合に成立していると仮定する． x1+10x2+⋯+10kxk+1=y1+10y2+⋯+10kyk+1x_1 + 10x_2 + \cdots + 10^{k} x_{k+1} =y_1 + 10y_2 + \cdots + 10^{k} y_{k+1} が成立するとすると，1010 で割った余りを考えることで，x1=y1x_1 = y_1 が従う．よって， 10x2+⋯+10kxk+1=10y2+⋯+10kyk+110x_2 + \cdots + 10^{k} x_{k+1} =10y_2 + \cdots + 10^{k} y_{k+1} x2+10x3+⋯+10k−1xk+1=y2+10y3+⋯+10k−1yk+1x_2 + 10x_3 + \cdots + 10^{k-1} x_{k+1} =y_2 + 10y_3 +\cdots + 10^{k-1} y_{k+1} が順に従う．仮定を適用すれば，(x2,x3,⋯ ,xk+1)=(y2,y3,⋯ ,yk+1)(x_2, x_3, \cdots, x_{k+1}) = (y_2, y_3, \cdots, y_{k+1}) を得る．x1=y1x_1=y_1 と合わせることで，n=k+1n=k+1 の場合も成立することが得られる．従って，帰納法より示された．

　雑談．　P⇒QP\Rightarrow Q の形の命題があるとき，PP を前件，QQ を後件と呼ぶらしいです．聞いたことなかったです．
　雑談2．　解答から分かるように，{6,0,−6}\{6,0,-6\} ではなくても，要素を 1010 で割った余りがすべて異なれば同様のことが言えますね．