クイズの問題文中に画像を添付できるようになりました。投稿キーの受付を再開しました。12:16任意のn個の自然数に対して、そのうちの何個か(1個〜n個)を選んで和を求めると、そのなかにはnの倍数となるようなものが必ず存在することを証明してください。ヒント�@(2017.9.9)”この手の問題ではnで割った余りに関して議論を進めていきます。最善を尽くすことでn-1個までは上記の条件を満たさない数の選び方ができるが、そこにn個目の数が加わると、その数が何であろうと上記の条件が満たされてしまうことを示します。この証明をコンパクトにまとめる場合はつまり「あの原理」を使うことになります。”=========================解答公開日は、出題から3週間後の9月23日あたり、ロックは9月30日あたりを予定しています。解答公開しました!(2017.9.23)ロックしました!(2017.10.8)【※簡潔な説明はスレの方に任せることにします。(ここは分かっている人は、はしょって可です)n個の自然数の中に余りが0(つまりnの倍数)のものが存在する場合は、その数によって題意が満たされるので、n個の自然数の余りが1,2,...,n-1の場合を考えます。n個の中から適当に1個だけ自然数(a1)を選択します。このときの余りをr1とします。次にさらに1個、数(a2)を選択して1個目との和を求めます。このときの和の余りがr1となるのはa2の余りが0(a2がnの倍数)の場合なので、この和の余りはr2(≠r1)となります。1個、数(a3)を選択して上との和を求めます。このときの和の余りがr1またはr2となる場合は、それぞれa2+a3またはa3の余りが0(つまりnの倍数)となることから、題意が満たされます。したがって、ここでは3数の和の余りがr3(≠r1,r2)となる場合を考えます。1個、数(a4)を選択して上との和を求めます。このときの和の余りがr1またはr2またはr3となる場合は、それぞれa2+a3+a4またはa3+a4またはa4の余りが0となることから、題意が満たされます。(このように、)題意が満たされないようにうまく選んだn個の自然数から1個ずつ自然数をうまく選び出して、逐一、和の余りを考える、ということをする場合、k個の自然数の和の余りrkはそれまでに出てきた余りr1,r2,...,r(k-1)と異なるものでなければいけません。(それまでに出てきた余りのどれかと一致する場合はk個の数の部分集合が題意を満たすため)しかし、0でない余りが1,2,...,n-1のn-1個しかないことから、n-1個の自然数の和まで考えたところで0でない余りはすべて使い尽くされるので、最後のn個目がどんな数であろうと、n個の自然数の和の余りは、0またはこれまでに出てきた余りとなります。(鳩の巣原理)この場合、上と同様にn個の自然数の和、またはその部分集合の和が題意を満たします。以上より、かならずnの倍数となる和が存在します。回答募集は終了しました。No.1n個の数をa_1,a_2,...,a_nとする。S_iとS_j(i<j)が存在する。よって,S_j-S_i=a_(i+1)+a_(i+2)+...+a_jはnの倍数。この証明を見ると、「順番が連続するものを選ばなければならない」という条件を付してもいけることがわかりますね。14:01アレを使う問題好きです。No.2鳩の巣論理を使う。仮に、n個の自然数(A1..An)を選んだときに、どの組み合わせの和もnの倍数にならないと仮定したときに、A1,A1+A2,A1+A2+A3,...,A1+A2+A3+...+Anのnに対する剰余は全て異なる値となる。nには0以外の相異なる剰余はn-1個しかないので矛盾する。なるような数aが含まれている場合、aはnの倍数。