和が１０　　　　　　　　　　 　　　　　　　　　　　　　　　　　　　

　平成２０年９月８日付けで当ＨＰの掲示板「出会いの泉」に、当ＨＰがいつもお世話になっ
ているＨＮ「ｚｋ４３」さんが、次のような問題を出題された。

　２０＝ｘ₁＋ｘ₂＋・・・＋ｘ₁₁　（ｘ_ｋ≧１）と、２０を１１個の自然数の和に分解するとき、

必ず、｛ｘ_ｋ｝の部分集合で和が10になるものが存在することを示せ。

　この問題に対して、当ＨＰがいつもお世話になっているらすかるさんが、速攻で解かれた。
（多少文言を補充させていただきました。）

（解）　１１個の数について、

（１）　１が１０個の場合　・・・　残りの１個が１０なので、それを採用すればよい。

（２）　１が９個の場合　・・・　残りの２数の組合せは、

　　　　　　　　　　　２＋９　、　３＋８　、　４＋７　、５＋６

　　の何れかである。何れにしても、１は４個以上あるので、和が１０となる組を作ることが
　　できる。

（３）　１が８個の場合　・・・　残りの３数の組合せは、

　　　２＋２＋８　、　２＋３＋７　、　２＋４＋６　、３＋３＋６　、２＋５＋５　、３＋４＋５　、

　　　４＋４＋４

　　の何れかである。何れにしても、１は６個以上あるので、和が１０となる組を作ることが
　　できる。

（４）　１が７個の場合　・・・　残りの４数の組合せで、最大の数は、　４　、５　、６　、７　の

　　何れかを取り得る。何れにしても、１は６個以上あるので、和が１０となる組を作ること
　　ができる。

（５）　１が６個の場合　・・・　残りの５数の組合せで、最大の数は、　３　、４　、５　、６　の

　　何れかを取り得て、さらに、最小の数は、２ である。このとき、最大の数と最小の数の

　　和は、　５　、６　、７　、８　の何れかである。何れにしても、１は５個以上あるので、和

　　が１０となる組を作ることができる。

（６）　１が５個の場合　・・・　残りの６数の組合せで、最大の数は、　３　、４　、５　の何れ

　　　かを取り得て、さらに、最小の数は、２ である。このとき、最大の数と最小の数の和

　　　は、　５　、６　、７　の何れかである。何れにしても、１は５個以上あるので、和が１０

　　　となる組を作ることができる。

（７）　１が４個の場合　・・・　残りの７数の組合せで、必ず２は、５個または６個ある。

　　よって、２を５個組み合わせて、和が１０となる組を作ることができる。

（８）　１が３個の場合　・・・　残りの８数の中に、２は、７個ある。

　　よって、２を５個組み合わせて、和が１０となる組を作ることができる。

（９）　１が２個の場合　・・・　残りの９数は全て、２となる。

　　よって、２を５個組み合わせて、和が１０となる組を作ることができる。

（１０）　１が１個以下の場合は起こり得ない。

　　以上から、必ず和が１０となる組を作ることができる。　　（終）


　次のように、全ての可能性を書きだしても示される。

　和が１０となる組合せは、赤色の数字で示される。（組合せは一意には定まらない。）

　多分「ｚｋ４３」さんの真意は、「もっとエレガントな解法を．．．」ということなのだろうが、こ
れは今後の研究課題としておこう。

（追記）　平成２０年９月１２日付け

　「ｚｋ４３」さんからの情報によると、この問題は、「鳩ノ巣原理」を用いて解けるらしいが、
まだ、その方針が不明なままである。（→　解決しました！）

　当ＨＰがいつもお世話になっている加俊さんが、次のような解法を当ＨＰの掲示板「出会
いの泉」に寄せられた。（平成２０年９月１１日付け）

　多少、文言を加筆修正して紹介したいと思う。

　自然数 ａ₁、ａ₂、・・・、ａ_ｎ を用いて、　１０ ＝ ａ₁ ＋ ａ₂ ＋ ・・・ ＋ ａ_ｎ　と、１０ をいくつか

の自然数の和に分解することができる。このとき、ｎ は、 １ 以上１０以下の自然数である。

　そこで、　ｍ＝１１−ｎ　とおくと、 ｍ も １ 以上１０以下の自然数である。

このとき、　１０ ＝ ｂ₁ ＋ ｂ₂ ＋ ・・・ ＋ ｂ_ｍ　となる自然数 ｂ₁、ｂ₂、・・・、ｂ_ｍ が存在する。

　実際に、１０を、１０個の１と考え、　ｂ₁、ｂ₂、・・・、ｂ_ｍ、ｂ₁、ｂ₂、・・・、ｂ_ｍ、・・・・　という数

列の最初から順次１０個の１を割り振っていけばよい。

　よって、 ２０ ＝ ａ₁＋ａ₂＋・・・＋ａ_ｎ＋ｂ₁＋ｂ₂＋・・・＋ｂ_ｍ　において、ｎ＋ｍ＝１１　であり、

　２０＝ｘ₁＋ｘ₂＋・・・＋ｘ₁₁　（ｘ_ｋ≧１）と、２０ を１１個の自然数の和に分解するとき、必ず、

｛ｘ_ｋ｝の部分集合で和が １０ になるものが存在することが示された。

（コメント）　当ＨＰの掲示板「出会いの泉」の平成２０年９月１２日付けで、らすかるさんが
　　　　　　指摘されているように、１１項の一部の項の和で１０となるものがあるかという問
　　　　　　題に対して、加俊さんの解答では、和が１０となる場合があることを前提にしたも
　　　　　　のでした。（私もウッカリしました．．．ｆ(^^;) ）
　　　　　　　構成的な方法でいいアイデアだと思ったのですが．．．。

（追記）　平成２０年９月１３日付け

　当ＨＰの掲示板「出会いの泉」に、この話題についてのある解法をＨＮ「３１５６」さんが書
き込まれた。多少、文言を加筆修正して紹介したいと思う。

　２０を１１個の自然数に分解したときに出来る項の中で最大の数を、ｎ とする。このとき、

分解された項の中には、少なくとも ｎ 個の １ が存在する。
（まず、１ を１１個並べ、それに残りの９個の １ を加えるという発想を用いれば明らかだろう。）

そこで、

（１）　ｎ ≧ ５ のとき、 ｎ に １０−ｎ 個（１０−ｎ≦５）の １ を加えれば、１０ となる。

（２）　ｎ = ４ のとき、 少なくとも１個の４と少なくとも４個の１で、８を作ることが出来る。

　　　上記で用いた１個の４と４個の１を除いた残りの６項について同様に考えて、

　　最大数が４の場合、残りは１が２個なので、この１が２個と上記の８を加えて１０となる。
　　最大数３が１個の場合、残りは２が４個と１が１個なので、この２と上記の８を加えて１０
　　となる。

　　最大数３が２個の場合、残りは２が２個と１が２個なので、この２と上記の８を加えて１０
　　となる。

　　最大数３が３個の場合、残りは１が３個なので、このうちの１を２個と上記の８を加えて
　　１０となる。

（３）　ｎ = ３ のとき、 少なくとも１個の３と少なくとも３個の１で、６を作ることが出来る。

　　　上記で用いた１個の３と３個の１を除いた残りの７項について同様に考えて、

　　最大数３が０個の場合、７項すべてが２なので、この２を２個と上記の６を加えて１０とな
　　る。

　　最大数３が１個以上３個以下の場合、必ず１が１個出来るので、この１と３と上記の６を
　　加えて１０となる。

（４）　ｎ = ２ のとき、 ９個の２と２個の１に分解されるので、５個の２で、１０を作ることが出
　　来る。

（コメント）　「３１５６」さん、証明をお寄せいただきありがとうございます。最大数に着目した
　　　　　　点、感動しました！

（追記）　平成２０年９月１４日付け

　当ＨＰがいつもお世話になっているらすかるさんが、別解を考えられた。
（多少文言を補充させていただきました。）

（解）　２０＝ｘ₁＋ｘ₂＋・・・＋ｘ₁₁　（ ｘ₁≧ｘ₂≧・・・≧ｘ₁₀≧ｘ₁₁　で、ｘ_ｋ は自然数） と分解され

　　　ているものとする。

　　　まず、　ｘ₁≦１０　である。

　　　実際に、ｘ₁≧１１　とすると、　ｘ₂、ｘ₃、・・・、ｘ₁₀、ｘ₁₁　は自然数なので、

　　　　　ｘ₁＋ｘ₂＋・・・＋ｘ₁₁≧１１＋１×１０＝２１　で矛盾である。よって、　ｘ₁≦１０

　　　また、　ｘ₁₁＝１　である。

　　　実際に、ｘ₁₁≧２　とすると、　ｘ₁、ｘ₂、・・・、ｘ₉、ｘ₁₀　は２以上の自然数となり、

　　　　　ｘ₁＋ｘ₂＋・・・＋ｘ₁₁≧２×１１＝２２　で矛盾である。よって、　ｘ₁₁＝１

　　　また、　ｘ₁₀＝１　である。

　　　実際に、ｘ₁₀≧２　とすると、　ｘ₁、ｘ₂、・・・、ｘ₈、ｘ₉　は２以上の自然数となり、

　　　　　ｘ₁＋ｘ₂＋・・・＋ｘ₁₁≧２×１０＋１＝２１　で矛盾である。よって、　ｘ₁₀＝１

　　　次に、　ｘ₂＋ｘ₃＋ｘ₄≦１０　である。

　　　実際に、ｘ₂＋ｘ₃＋ｘ₄≧１１　とすると、　３ｘ₂≧ｘ₂＋ｘ₃＋ｘ₄≧１１　から、

　　　 ｘ₂≧１１/３　すなわち、　ｘ₂≧４　となる。

　　　　このとき、　ｘ₁≧ｘ₂　より、　ｘ₁≧４　でなければならない。

　　　　しかるに、　ｘ₁＋ｘ₂＋・・・＋ｘ₁₁≧ｘ₁＋（ｘ₂＋ｘ₃＋ｘ₄）＋（ｘ₅＋・・・＋ｘ₁₁）

　　　　　　　　　　　　　　　　　　　　　　≧４＋１１＋１×７＝２２　で矛盾である。

　　　　よって、　ｘ₂＋ｘ₃＋ｘ₄≦１０　である。

　　　次に、　ｘ₅≦２　である。

　　　実際に、ｘ₅≧３　とすると、　ｘ₁＋ｘ₂＋・・・＋ｘ₁₁≧（ｘ₁＋・・・＋ｘ₅）＋（ｘ₆＋・・・＋ｘ₁₁）

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　≧３×５＋１×６＝２１　で矛盾である。

　　　　よって、　ｘ₅≦２　である。

　　　このとき、　ｘ₆≦２　、ｘ₇≦２　、ｘ₈≦２　、ｘ₉≦２　となる。

　　　そこで、

　　　ｘ₂＋ｘ₃＋ｘ₄＝１０　ならば、　ｘ₂、ｘ₃、ｘ₄　が求めるものである。

　　　ｘ₂＋ｘ₃＋ｘ₄＝９　ならば、　ｘ₂、ｘ₃、ｘ₄、ｘ₁₁　が求めるものである。

　　　ｘ₂＋ｘ₃＋ｘ₄＝８　ならば、　ｘ₂＋ｘ₃＋ｘ₄＋ｘ₅　は、９または１０である。

　　　　　　　ｘ₂＋ｘ₃＋ｘ₄＋ｘ₅＝１０　ならば、　ｘ₂、ｘ₃、ｘ₄、ｘ₅　が求めるものである。

　　　　　　　ｘ₂＋ｘ₃＋ｘ₄＋ｘ₅＝９　ならば、　ｘ₂、ｘ₃、ｘ₄、ｘ₅、ｘ₁₁　が求めるものである。

　　　以下同様にして、ｘ₂＋ｘ₃＋ｘ₄　に順次、２以下の自然数 ｘ₅、ｘ₆、ｘ₇、ｘ₈、ｘ₉、ｘ₁₀ を加

　　　えることにより、途中の和で必ず、９または１０となる場合がある。

　　　　　和が１０であれば、その数列が求めるものである。

　　　　　和が９であれば、その数列に ｘ₁₁ を加えたものが求めるものである。

　　したがって、　２０＝ｘ₁＋ｘ₂＋・・・＋ｘ₁₁　（ｘ_ｋ≧１）と、２０ を１１個の自然数の和に分解

　　するとき、必ず、｛ｘ_ｋ｝の部分集合で和が １０ になるものが存在する。　（終）

（コメント）　らすかる様、いつも解答をお寄せいただきありがとうございます。

　　　　　２０という数の分解に現れる項のいろいろな性質を調べられて、和が１０となるもの
　　　　を構成していくという手法に感動しました。

（追記）　平成２２年５月１６日付け

　この話題について、当ＨＰがいつもお世話になっているＨＮ「ＦＮ」さんが一般化を考えられ
た。（当ＨＰ掲示板「出会いの泉」　平成２２年５月１１日付け）

多少文言等を補足・修正して紹介したいと思う。

　ｎ＋１ 個の自然数の和が ２ｎ であるとき、そのうちの何個かを取りだして和を n に
できる。

（証明）　ｎ に関する数学的帰納法による。

　ｎ＝１　のときは明らかである。

　ｎ−１ 以下では成り立つものと仮定して、ｎ （ｎ ≧２）のときを考える。

　　ｎ＋１ 個の自然数のうち、最大のものを Ｍ とする。 明らかに、Ｍ≧２　である。

　　このとき、１は、Ｍ個以上あることを確認する。

　　　いま、１ が ｋ 個あるとする。

　　　ｋ 個の１と、１個のＭ以外をすべて2に変えると、

　　　　ｋ＋２（ｎ−ｋ）＋Ｍ＝２ｎ−ｋ＋Ｍ≦２ｎ　より、　ｋ≧Ｍ　である。

　　ｎ＋１ 個の自然数から、１個のＭとＭ−２個の１を取り除いたもの（Ａ）を考える。

　　Ａに含まれる要素の個数は、

　　　ｎ＋１−（１＋Ｍ−２）＝ｎ−Ｍ＋２＝（ｎ−Ｍ＋１）＋１　で、

　　その和は、　２ｎ−（Ｍ＋Ｍ−２）＝２ｎ−２Ｍ＋２＝２（ｎ−Ｍ＋１）　である。

　　Ｍ≧２　より、ｎ−Ｍ＋１≦ｎ−１　なので、帰納法の仮定より

　　　Ａ から何個かを取りだして、その和を ｎ−Ｍ＋１ にできる。

　　このとき残ったものの和も、 ｎ−Ｍ＋１ である。

　　ところで、Ａには少なくとも２個の１があるから、必要なら取りだしたものと残ったものを

　　入れ替えることで残ったものの中に１があるようにできる。

　　あとは、取りだしたもの(和が ｎ−Ｍ＋１)に、Ｍ−１個の１を加えれば和は ｎ になる。

　　（はじめに、Ｍ−２個の１を取り除いていて、残った中に１が少なくとも１個あるから、こ
　　れは可能である。）
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（証終）

　さらに、ＦＮさんによれば、次の形に一般化したほうがいいかもしれないとのこと。

　ｎ＋１ 個の自然数の和が ２ｎ であるとき、そのうちの何個かを取りだして和を １ 以
上 ２n 以下の任意の自然数にできる。

　「重さが１ｇの整数倍の分銅をうまく使って、１ ｇから ｎ ｇ まですべて測れるようにせよ。」
といった形の問題があるが相当へたな選び方をしても、和が ｎ ｇ で、個数が ｎ/２＋１ 個
ほどであれば、１ｇから ｎｇ まですべて測れるということを示しているとのことである。

　さらにＦＮさんは、上記を一般化して、（平成２２年５月１２日付け）

　ｎ 個の自然数の和Ｓが ２ｎ−１ 以下であるとき、そのうちの何個かを取りだして和
を Ｓ 以下の任意の自然数にできる。

とのこと。

（コメント）　証明がとても分かり易かったです。ＦＮさんに感謝します。


（追記）　平成２７年５月２日付け

　当ＨＰ読者のＨＮ「Seiichi　Manyama」さんが、上記の一般化された問題について、数学的
帰納法を使わない証明を考えられた。（一部文言等を加筆修正させていただきました。）

　n = 1 のときは自明なので、n≧2 のときを考える。　x₁ ≦ x₂ ≦ … ≦ x_n としてもよい。

　ｎ 以下の任意の自然数 t に対し、　0 ＜ x₁ + x₂ + … + x_t ＜ 2t …（*）　が成立。
(∵ 0 ＜ x₁ + x₂ + … + x_t ≦ t/n × (x₁ + x₂ + … + x_n) = 2t - t/n ＜ 2t)

　1≦i≦t　に対し、A(i) ≡ x₁ + x₂ + … + x_i 　（mod t）　と定める。

　あるt₀に対し、A(t₀) ≡ 0 （mod t）　となるならば、（*）より、x₁ + x₂ + … + x_t0 = t となり、

命題は成立。そうでないならば、A(1)〜A(t)はいずれも 1〜t - 1 のいずれかなので、

　A(t₁) = A(t₂) 　(t₁ < t₂)　なる t₁、t₂ が存在。よって、A(t₂) - A(t₁) = 0。

　（*）より、　0 ＜ x_{(t1+ 1)} + … + x_t2 ＜ x₁ + … + x_t2 ＜ 2t₂ ≦ 2t

　ゆえに、　x_{(t1+ 1)} + … + x_t2 = t となり、命題は成立。


（コメント）　Seiichi　Manyamaさん、証明をご投稿いただき、ありがとうございます。証明の基
　　　　　　本的なアイデアは、下記でＦＮさんが示された鳩ノ巣原理を用いた証明と相通じる
　　　　　　ものがありますね！


（追記）　平成２２年１０月６日付け

　ＦＮさんが、冒頭の問題について、鳩ノ巣原理を用いて解決された。次の形の鳩ノ巣原理
を用いるとのこと。

　鳩ノ巣原理

　１０個の巣に１０匹の鳩を入れれば、すべての巣に鳩が入るか、どれかの巣に２匹
以上入る。

　この原理を用いて、次の問題

　２０＝ｘ₁＋ｘ₂＋・・・＋ｘ₁₁　（ｘ_ｋ≧１）と、２０を１１個の自然数の和に分解するとき、

必ず、｛ｘ_ｋ｝の部分集合で和が10になるものが存在することを示せ。

を考える。

（解）　１１個の自然数 ｘ₁、ｘ₂、・・・、ｘ₁₁ の和が２０であるとする。１以上１０以下の自然数 ｋ

　に対して、 ｘ₁＋ｘ₂＋・・・＋ｘ_ｋ を１０で割った余りをＳ（ｋ）とする。

Ｓ（１）、Ｓ（２）、・・・、Ｓ（１０）は、０、１、２、・・・、９のどれかであるから、鳩ノ巣原理により、

（１）　Ｓ（１）、Ｓ（２）、・・・、Ｓ（１０）はすべて異なる場合

（２）　異なる ｋ、ｊ に対して、　Ｓ（ｋ）＝Ｓ（ｊ）となる場合

のどちらかである。

　（１）のときは、ある ｋ について、Ｓ（ｋ）＝０　となる。

　　　ここで、　１≦ｘ₁＋ｘ₂＋・・・＋ｘ_ｋ ≦１９　より、１０で割った余りが０になるのは、

　　　　　ｘ₁＋ｘ₂＋・・・＋ｘ_ｋ＝１０

　（２）のときは、　ｋ＜ｊ　とすると、　Ｓ（ｋ）＝Ｓ（ｊ）　は、１０で割り切れる。すなわち、

　　　１≦ｘ_ｋ+1＋ｘ_ｋ+2＋・・・＋ｘ_ｊ ≦１９　で、これを１０で割った余りが０であるから、

　　　　　ｘ_ｋ+1＋ｘ_ｋ+2＋・・・＋ｘ_ｊ＝１０　　（終）


　ＦＮさんによれば、一般化した次の命題も全く同じでできるとのこと。

命題
　　　　ｎ＋１個の自然数の和が２ｎであるとき、そのうちの何個かを取りだして和を
　　　ｎにできる。

　上の証明を見ると、和が２０は和が２０以下でいいし、ｘ₁₁ はほとんど役割を持たないので
次の形に一般化した方がよさそうです。

命題
　　　　ｎ個の自然数の和が２ｎ−１以下であるとき、そのうちの何個かを取りだして
　　　和をｎにできる。

（コメント）　鳩ノ巣原理を用いた証明、簡明で分かり易いですね！感動しました。ＦＮさんに
　　　　　　感謝します。