『割り切れる？ Part7』解答

◆三重県　鳥居 さんからの解答。

2n-1 個の自然数を x₁, x₂, ..., x_2n-1 とする。

n が素数の場合と合成数の場合に分けて証明する。
まず、n が素数 p の場合を扱う。

x₁, x₂, ..., x_2p-1 は p で割った剰余が小さいものから並んでいるものとする。

2p-1 個の自然数のうち、剰余が同じであるものが p 個以上あれば、そこから p 個を取り出すと、その和は p の倍数となり、問題の答えは「可能」となる。

よって以下では、剰余が同じであるものが p-1 個以下であるとする。

このとき x₁, x₂, ..., x_2p-1 は、同じ剰余が p 個以上並ばないため、
j-i ≧ p-1 であるとき、x_j と x_i との差は p の倍数にならない。

ここで、y_i = x_p+i- x_i (0 ≦ i ≦p-1) とおく。
y_i は p の倍数ではない。

さらに、S_k (0≦k≦p-1) を
f₁ y₁ + f₂ y₂ + ... + f_k y_k
(ただし f₁, ..., f_k は 0 または 1) が取り得る、法 p の下での剰余の集合とする。

S_k の中で、同じ剰余を与えるものは、要素数を 1 個として数えるものとする。
また S_k には、要素 {0} を必ず含む。

特に、S₀ = {0} であり、要素数は 1。
S₁ = {0, y₁} であり、要素数は 2。

S₂ は 0, y₁, y₂, y₁ + y₂ の４つが要素の候補となるが、これらの中には法 p の下で剰余が等しくなるものがあるかも知れない。

さて、S_k-1 に t 個の要素があって、
S_k-1 = {0, a₁, ..., a_t-1} であるとする。

S_k-1 の各要素に y_k を加えたものを要素とする集合を R_k とすると、
R_k = {y_k, a₁ + y_k, ..., a_t-1 + y_k} である。

R_k の要素の和と S_k-1 の要素の和をそれぞれ求め、それらの差を求めると、

[y_k + (a₁ + y_k) + ... + (a_t-1 + y_k)] - (0 + a₁ + ... + a_t-1) = t y_k である。

ここで、1 ≦t＜ p であれば、t y_k は p で割り切れない。

R_k と S_k-1 は要素数が同じであるが、それぞれの要素数の和は法 p の下で剰余が等しくないことになる。
これは、R_k には S_k-1 にない要素が少なくとも１つはあることを意味する。

S_k = S_k-1 ∪ R_k であるから、S_k の要素数は S_k-1 よりも多くなる。

もし t = p ならば、S_k-1 には p 個の要素があり、法 p の下の剰余をすべて尽くしている。
こうなると S_k, S_k+1, ... は、要素数が p 個である状態が続いていく。

よって、S_k の要素は k+1 個以上あるが、p 個が上限である。
特に、S_p-1 は要素数が p 個で、法 p の下の剰余がすべて含まれる。

すると、S_p-1 の中から適切な要素を選び出すことにより、

(x₁ + ... + x_p) + (f₁ y₁ + ... + f_p-1 y_p-1) が p の倍数になるような
f₁, ..., f_p-1 が存在することになる。

上式を変形すると、

(x₁ + ... + x_p) + [f₁ (x_p+1 - x₁) + ... + f_p-1 (x_2p-1 - x_p-1) ]
= (1 - f₁) x₁ + ... + (1 - f_p-1) x_p-1 + x_p + f₁ x_p+1 + ... + f_p-1 x_2p-1
= (f_i = 0 となる x_i の和) + (f_i = 1 となる x_p+iの和) + x_p

となって、p 個の自然数の和が p の倍数となることが示される。

以上のように、n が素数のとき問題の答えが「可能」であることが証明された。

次に、n が合成数の場合を扱う。
n の素因数の一つを p とし、n = pm とする。

ここで、自然数の個数が
2pm - 1 = p (2m - 1) + (p - 1)
のように変形できることに着目する。

n が素数の場合で示したような方法で、2pm-1 個の自然数の中から適切な選び出しにより、p 個の自然数の和が p の倍数にすることができる。

選び出しから漏れた自然数の中から、適切な選び出しを繰り返していくと、
p 個の自然数の和が p の倍数となる自然数の組が 2m-1 組でき、
最終的に組に入りそこなった自然数が p-1 個となるようにできる。

ここで作った各組に対して、 p 個の自然数の和を p で割った値を
z₁, z₂, ..., z_2m-1とする。

すると、2m-1 個の自然数から適切に m 個を取り出して m の倍数を作ることができるかという問題に帰着される。

もし帰着された問題の答えが「可能」ならば、
pm 個の自然数の和を pm の倍数とすることができる。

この問題の帰着を、n の素因数１つずつに対して繰り返していくと、最後は素数の場合の問題に帰着され、その答えは前に示したように「可能」である。

よって、n が合成数の場合でも、問題の答えが「可能」であることが証明された。

参考までに、2n-2 個の自然数の中から n 個を取り出してその和を n の倍数とすることは、一般に不可能である。
不可能の例として、1 が n-1 個、n が n-1 個の場合が考えられる。

◆出題者のコメント

鳥居さん、解答ありがとうございます。
出題から半年以上も無解答だったので、とても嬉しいです。
（ヒントを出そうかと迷っていた矢先の解答です。）
それにしても、みごとな証明ですね。

＞「さて、…」から、＞「こうなると…」までのくだりは、まさに「立て板に水」のごとし。　
とても感動しました。（出題者が感動してどうする。^^；）

おまけに、内ｎ個の和でｎで割り切れるものが常に存在する自然数の最少個数は、(2n-1)個であることまで示して頂きありがとうございます。

ちなみに、問題考案当初は以下でしたが品がなくて失礼なので、シンプルに改題したのが本問です。

『毎日する公平な山分け』 問題

ｎ人のスリ集団が、全員でｎ個の財布を毎日スルのだが、仲間同士の掟として、山分けするときは、必ずｎ個の財布の現金すべてを、ｎ人全員で公平に分けなければならない。
掟に従った山分けを、スリ仕事が終わってから毎日するには、前もって最低何個の財布があれば可能か？

ただし、山分け前の財布には必ず現金が入っているものとし、両替は可能であるものとする。

解答が困難のようなら、以下のヒント。

（１）　最初(ｎ−１)個の財布があれば、その後は毎日掟に従った山分けが可能であることを示せ。
　　↑（十分条件）

（２）　(ｎ−１)個が条件を満たす最低個数であることを示せ。
　　↑（必要条件)

ですから、改題前の問題なら鳥居さんの解答は必要十分条件を示してくれたことになります。

　『割り切れる？ Part7』へ

　数学の部屋へもどる