パズルの国のアリス

缶もキャンディも 平等に!(解答)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 缶の数が2n−2以下では,どのn缶を開けてもキャンディの合計数がnの倍数にならない場合があることを,まず一般のnの場合に証明してしまおう。これは簡単で,どの缶にもnの倍数個かnで割ると1個余る数のキャンディが入っている場合を考えてみるといい。n缶を選びその合計数をnの倍数にするには,どちらか一方のタイプの缶だけを選ぶしかないが,両タイプが半々に分かれている場合,どちらもn缶には足りないので,それは不可能だ。

 では,2n−1缶あれば,その中からうまくn缶を選んでキャンディの合計数をnの倍数にできるだろうか。グリフォンの言葉は,少なくともn=7の場合には,必ずそうできることを示唆しているようだ。その通りなのだが,このままでは証明が難しそうなので,ちょっと意外なアイデアを導入しよう。それは,もう1つ缶を増やして缶を全部で14個にすることだ。ただし増やす缶には,14缶全部を合わせると合計が7の倍数になるようにキャンディを入れておく。

 さてこの状況で,増やした缶も含めた14缶からうまく7缶を選べば,中のキャンディの合計を7の倍数にできることを示そう。i番目の缶の中のキャンディ個数を7で割った余りの数値をaiとする。もちろん,7で割った余りだから,0から6までのいずれかだ。a1a2,…,a14の中に同じ余りが7つ以上あれば,その中のどれでも7缶を選べば合計キャンディ数は7で割り切れる。したがって,同じ余りが7つはないとして,缶を並べかえaiが広義単調に増加するようにする。すなわち,

  a1a2≦ … ≦a14

となるように,14個の缶を並べかえるのだ。aiai+7を対にして考える。同じ余りが7つはないので,aiai+7である。次に0から6までの数値の集合Akを次のように定義する。まずA1={a1a8}とする。またAi+1=(Aiai+1)∪(Aiai+8)とする。ここで記法BaBの各要素baを加えて7で割った余りの集合,すなわち,

  {(ba)mod 7|bB

を表すことにする。集合Akが何を表しているかというと,各対{aiai+7}からその要素biを1つずつ選び,(b1+…+bk)mod7を計算した結果を集めたものであることは納得していただけるであろう。実例を挙げると,たとえばa1からa14までを0,0,0,1,1,1,2,2,2,5,5,5,5,6とする場合,

  A1={0,2}
  A2={0,2,4}
  A3={0,2,4,5}
  …

である。さて,集合Bの要素数を#Bと書くことにすれば,任意のaについて#B=#(Ba)であることは明らかだ。なぜなら,Baの要素はBの要素をaだけ順繰りにずらしたのにすぎないのだから。従って

  2=#A1≦#A2≦…≦#A7≦7

であり,#Ai=#Ai+1となるiが存在しなければならない。Ai+1=(Aiai+1)∪(Aiai+8)だから,このことはAiai+1Aiai+8を意味する。これはAiai+8ai+1ずらすと元に戻るということだが,7は素数であり,ai+1ai+8だから,これはAiが空集合か全体集合{0,1,…,6}でないと起こりえない。#A1=2だから,もちろん空集合ということはありえず,従って#Ai=#Ai+1=…=#A7=7ということになる。すると,当然0∈A7だから,(b1b2+…+b7)mod7=0となるように各biを{aiai+7}から選べるわけであり,その7つの缶が目的のものである。

 では,元の問題,つまり缶13個の場合にうまく7缶を選べるかというと,14番目の缶を導入したときに合計キャンディ数を7の倍数にしておいたのがミソである。もし上で選んだ7缶の中にその14番目の缶が含まれていたら,選ばれなかったほうの7缶を考える。全体のキャンディ数が7の倍数で,選んだ缶の合計キャンディ数が7の倍数なのだから,残った缶の合計キャンディ数も7の倍数だ。よって代わりに残ったほうの7缶を選べばやはり目的は達成される。

 次に一般のn匹で分け合う場合を考えよう。この場合も缶が2n−1個あればうまくいくようだ。ところが,上と同様の論法を適用しようとすると,ほとんど問題ないのだが,ただ1点,7の特殊性を利用しているところでつまずく。それは7が素数だということで,一般のnではAiAi+1からAi={0,1,…,n−1}は導かれないのだ。逆に言えば,nが素数であれば,証明はそのままで成り立つ。では一般にはどうするかというと,nを素因数分解し,素因数の数に関する数学的帰納法を適用するとうまくいく。

 今,nnpqp>1,q>1)と分解され,p匹やq匹で分け合う場合にはそれぞれ2p−1缶,2q−1缶があれば十分としよう。このとき2pq−1缶が与えられれば,その中からpq缶を選び,中のキャンディ数の合計をpqの倍数にできることは次のように示される。2p−1個以上の缶があれば,その中からp個の缶を選んで,中身の合計をpの倍数にできるのだから,2pq−1個の缶に対して何度もこの選択を行うことで,p個ずつの缶からなる重なりのない集合B1B2,…,B2q−1を選び出せて,各Biのキャンディ合計数をpの倍数pkiにできる(最後にp−1缶が残るが,これは放っておけばよい)。次にk1k2,…,k2q−1個のキャンディが入っている缶がそれぞれあると考えると,これらからq個を選んで,その中のキャンディ合計をqの倍数にできる。つまりki1+…+kiqqsとなるようにi1,…,iqを選べる。そこでBBi1∪…∪BiqとすればBnpq個の缶からなり,そのキャンディ数の合計はpqsだからnpqの倍数となる。

 これで,証明は完結したが,筆者には上の証明がやや不満で,帰納法に頼らなくても一般のnの場合を証明する方法があるのではないかと思っている。読者のお知恵を拝借したい。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004),
Mathematical Mind-Benders(2007) P. Winkler。
邦訳は『とっておきの数学パズル』(2011年),『続・とっておきの数学パズル』(2012年),ピーター・ウィンクラー著,坂井公・ 岩沢宏和・小副川健訳,日本評論社。

問題はこちらです