数学の問題で困っています

何から手をつけていいか全くわからなくて困っています
答えがついてないんでどうかよろしくお願いします

No.2 ベストアンサー 回答者： hashioogi 回答日時： 2013/05/06 08:33

これらと同じような問題が岩波現代文庫「やわらかな思考を育てる数学問題集1」に色々と載っています。

それを参考に回答すると、
(2)
a[1]～a[n]の中のどれか（例えばa[k]）がnで割り切れることができればそれを１つだけ含む部分集合{a[k]}が答えです。
従ってa[1]～a[n]のいずれもnで割り切れないとします。
0～n-1の番号を付けたn個の箱を用意します。
そして以下のn個の部分集合を考えます。
(1) {a[1]}
(2) {a[1], a[2]}
(3) {a[1], a[2], a[3]}
:
:
(n) {a[1], a[2], a[3], …, a[n]}
上記n個の部分集合のそれぞれの合計をnで割った余りを求め、余りと同じ番号の箱に部分集合を入れます。
箱の数はn個で、考えている部分集合の数はn個なので、以下の2通りが考えられます。
（一) 全ての箱に部分集合が1つずつ入った場合。
（二) いくつかの箱が空の場合。
（一) の場合は0の番号が付けられた箱の中の部分集合が答えになります。
（二) の場合はどれかの箱には2つ以上の部分集合が入ります。そういう箱から2つの部分集合を取り出して、要素数の大きい部分集合から要素数の小さい部分集合を取り除けば新しい部分集合が出来上がります。それが答えになります。

No.1 回答者： hashioogi 回答日時： 2013/05/05 11:38

「鳩の巣箱」というのを調べればいいのではないかと…。

巣箱が4つしかない時に5羽以上の鳩を入れようとすると少なくとも１つの巣箱には2羽以上入れざるを得ないというやつです。
(1)
今n-1個の箱を用意し、1～n-1の番号を振ります。したがって0の番号の箱は用意しません。
a[0]～a[n]を上記の箱に入れます。どのように入れるかというとa[k]をnで割った余りの番号の箱に入れます。a[0]～a[n]はnで割り切れないので余りが0になることはありません。余りは必ず1～n-1になります。
箱がn-1個しかないのにn個の数字を入れるのですからどれかの箱には2個以上の数字が入るはずです。
その箱から2つの数字を取り出します。それがa[i]、a[j]です。
以下省略。