Fussy's Diary

Twitter で面白いアカウントを見つけました。「数学問題 bot」というアカウントです。問題を一つ選んで挑戦してみました。

「1 から 11 までの自然数からなる集合を N とする。N をどのように 2 つの集合 A, B に分割 ( N = A ∪ Bかつ A ∩ B ＝ ∅ )しても、A または B の部分集合 S で、S に属する要素の和がちょうど 12 になるものが存在することを示せ」

要は、1 から 11 までの数をどのように二つに分けても、どちらかに和が 12 となるような組み合わせが存在するという意味です。とりあえず解いてみましたが、後で回答を見つけて確認したところ、最初だけ一致していたものの途中から異なる証明をしていました。一応合っているとは思うのですが ...

(解法)

二つの要素の和が 12 になる組み合わせは ( 1, 11 ), ( 2, 10 ), ( 3, 9 ), ( 4, 8 ), ( 5, 7 ) の 5 つ。従って、これらのペアが同じ集合に属すれば必ず和が 12 になる要素が見つかる。各組み合わせの要素が全て異なる集合に属する場合を考えると、残りの要素 6 がどちらに入るのかを考慮すれば 2⁵ = 32 通りになる。全ての場合において和が 12 になる要素が存在すれば証明できる。6 を除けば、対称性から 16 通りを考えればよいので、まずは 16 通りを調べて和が 12 となる組み合わせがなければ 6 を追加することにする (結局 6 は不要となりました)。

なお、3 つ以上の要素から和が 12 になる組み合わせは

( 1, 2, 9 ) ( 1, 2, 3, 6 ) ( 1, 2, 4, 5 )
( 1, 3, 8 ) ( 1, 4, 7 ) ( 1, 5, 6 )
( 2, 3, 7 ) ( 2, 4, 6 )
( 3, 4, 5 )

がある。

以下、A = { 1, 2, 3, 4, 5 }, B = { 11, 10, 9, 8, 7 } を初期状態として、5 桁の二値データはペアの要素を入れ替えた個所を 1 で表しているものとする。例えば、00001 ならば 5 と 7 を入れ替えたもの。二値データが二つあるのは、どちらも A, B を入れ替えただけで同じ意味になるから (ちなみにビット反転すればもう片方のデータが得られます)。

1) 00000 11111
A 1 2 3 4 5 → [1 2 4 5]
B 11 10 9 8 7

2) 00001 11110
A 1 2 3 4 7 → [2 3 7]
B 11 10 9 8 5

3) 00010 11101
A 1 2 3 8 5 → [1 3 8]
B 11 10 9 4 7

4) 00011 11100
A 1 2 3 8 7 → [1 3 8]
B 11 10 9 4 5

5) 00100 11011
A 1 2 9 4 5 → [1 2 4 5]
B 11 10 3 8 7

6) 00101 11010
A 1 2 9 4 7 → [1 4 7]
B 11 10 3 8 5

7) 00110 11001
A 1 2 9 8 5 → [1 2 9]
B 11 10 3 4 7

8) 00111 11000
A 1 2 9 8 7 → [1 2 9]
B 11 10 3 4 5

9) 01000 10111
A 1 10 3 4 5 → [3 4 5]
B 11 2 9 8 7

10) 01001 10110
A 1 10 3 4 7 → [1 4 7]
B 11 2 9 8 5

11) 01010 10101
A 1 10 3 8 5 → [1 3 8]
B 11 2 9 4 7

12) 01011 10100
A 1 10 3 8 7 → [1 3 8]
B 11 2 9 4 5

13) 01100 10011
A 1 10 9 4 5
B 11 2 3 8 7 → [2 3 7]

14) 01101 10010
A 1 10 9 4 7 → [1 4 7]
B 11 2 3 8 5

15) 01110 10001
A 1 10 9 8 5
B 11 2 3 4 7 → [2 3 7]

16) 01111 10000
A 1 10 9 8 7
B 11 2 3 4 5 → [3 4 5]

これで、全ての場合に対して和が 12 となる要素があることが証明された。