2014年03月25日
数学問題 bot
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 がどちらに入るのかを考慮すれば 25 = 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 となる要素があることが証明された。
「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 がどちらに入るのかを考慮すれば 25 = 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 となる要素があることが証明された。
