クイズ大陸クイズ大陸

参加型クイズサイト『クイズ大陸』へようこそ!
(2017/10/10) 10/19頃から11/10までwikiが表示できませんでした。現在は復旧しています。
(2017/11/05) 10/19頃から11/05までお問い合わせ、投稿キーの受付ができませんでした。現在は復旧しています。
(2016/09/12) クイズの問題文中に画像を添付できるようになりました。
(2016/04/25) 投稿キーの受付を再開しました。

FAQ
feedRSS


n個の自然数の部分的な和
難易度:  
?具無しのとんぺい 2017/09/02 12:16
任意のn個の自然数に対して、そのうちの何個か(1個〜n個)を選んで和を求めると、
そのなかにはnの倍数となるようなものが必ず存在することを証明してください。

ヒント@(2017.9.9)
この手の問題ではnで割った余りに関して議論を進めていきます。そして、最善を尽くすことでn-1個までは上記の条件を満たさない数の選び方ができるが、そこにn個目の数が加わると、その数が何であろうと上記の条件が満たされてしまうことを示します。この証明をコンパクトにまとめる場合はつまり「あの原理」を使うことになります。

=========================
解答公開日は、出題から3週間後の9月23日あたり、ロックは9月30日あたりを予定しています。

解答公開しました!(2017.9.23)

ロックしました!(2017.10.8)
Answer※簡潔な説明はスレの方に任せることにします。

結局のところ、n個の自然数をnで割った余り(=0,1,2,...,n-1)の和が0またはnの倍数となることを示せばいいので、以下それを示していきます。

ーーーーーーーーーーーーーーーーーーーーー(ここは分かっている人は、はしょって可です)
n個の自然数の中に余りが0(つまりnの倍数)のものが存在する場合は、その数によって題意が満たされるので、n個の自然数の余りが1,2,...,n-1の場合を考えます。

@ まず、n個の中から適当に1個だけ自然数(a1)を選択します。このときの余りをr1とします。

A 次にさらに1個、数(a2)を選択して1個目との和を求めます。このときの和の余りがr1となるのはa2の余りが0(a2がnの倍数)の場合なので、この和の余りはr2(≠r1)となります。

B さらに1個、数(a3)を選択して上との和を求めます。このときの和の余りがr1またはr2となる場合は、それぞれa2+a3またはa3の余りが0(つまりnの倍数)となることから、題意が満たされます。したがって、ここでは3数の和の余りがr3(≠r1,r2)となる場合を考えます。

C さらに1個、数(a4)を選択して上との和を求めます。このときの和の余りがr1またはr2またはr3となる場合は、それぞれa2+a3+a4またはa3+a4またはa4の余りが0となることから、題意が満たされます。したがって、ここでは4数の和の余りがr4(≠r1,r2,r3)となる場合を考えます。
  ・
  ・
  ・
ーーーーーーーーーーーーーーーーーーーーーーーー
(このように、)題意が満たされないようにうまく選んだ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の倍数となる和が存在します。(証明終)
■
回答募集は終了しました。

このクイズのヒント

    ヒント知らないよ

このクイズの参加者(5人)

ジャンル・キーワード

携帯用ページ


携帯電話のQRコード読み取り機能でこのページを見られます。

広告 お買い物は下記のリンクからどうぞ

広告
クイズ大陸関連書籍