Weekend Mathematics／問題／問題40

４０．鳩の巣の問題

1. 鳩の巣が１００個あります。 いま、最低何羽の鳩がいれば、どこかの巣に必ず１０羽以上の鳩が入っていることになるでしょうか？
   
   
   

2. １〜１００までの数があります。 いま、これから５１個の数を適当に選びます。 すると、この中には最大公約数を１とする数２個が必ず含まれています。 これを証明してください。

問題１

解答・その１

（ペンネ−ム：ＭＩＮＩＭＩＮＩ３２）

最初、ひとつの巣に鳩が１０羽いて、残りの９９個の巣に鳩が０羽でOK！と 思いましたが、考えなおし一番アンラッキーな場合を考えてみました。

どこかの巣に”必ず”ということは、鳩が１００個の巣に９羽ずつ入って いて、もう１羽鳩がどこかの巣に入ろうとするとどこの巣に入っても必ず １０羽以上になる巣ができることになります。
よって、１００×９＋１＝９０１
ANSWER＝９０１羽だと思います。

解答・その２

（ペンネ−ム：たけ）

９０１羽
全ての巣に９羽の鴨がいるとする。
新たに鴨を１羽、１００個の巣の前に連れてくる。
この１羽をどの巣にいれても、その鴨の入った巣には１０羽の鴨がいることになる。

解答・その３

（ペンネ−ム：浜田　明巳）

まずｎ個の巣の中にそれぞれ(ｐ−１)羽ずつの鳩を入れる．
これは，すべての巣の中にｐ羽未満の鳩を入れることが出来る場合が存在するときの鳩の数の最大値は， ｎ(ｐ−１)羽であることを意味する．
したがって，これにあと１羽でも増えれば，つまりｎ(ｐ−１)＋１羽以上鳩がいれば， どこかの巣に必ずｐ羽以上の鳩が入っていることになる．
この問題の場合，ｎ＝１００，ｐ＝１０であるから，答は９０１羽である．

問題２

解答・その４

（ペンネ−ム：kiyo）

ｎを１００未満の素数とする。
ｎの倍数で最大個あるのは２の倍数で５０個である。
したがって５１個選べば少なくとも１組（２個）の最大公約数は１となる。

これだと「鳩の巣箱の原理」というより背理法になるのでしょうか。　

解答・その５

（ペンネ−ム：マサボー）

問題を以下の命題に変更します。

「１〜１００までの数のうち、最大公約数を１とする数２個（互いに素）がないよう に、51個を選ぶことができる」

ただ、実際は1は選べないので2〜100のうち51個を選ぶことになります。
素数どうしは選べませんから、1〜100のうちの素数の倍数の数を考えます。
2の倍数　50個、3の倍数　33個、5の倍数　20個、7の倍数　14個、 11の倍数　9個、13の倍数　7個、17、19の倍数　5個、
20から25までの素数の倍数　4個
26から33までの素数の倍数　3個
34から50までの素数の倍数　2個
51以上の素数の倍数　1個

以上より、最大の倍数数を持つのは2ですが、2の倍数は50個しかないため、51個目は 他の数（奇数）を選ばなくてはなりません。
2と奇数は互いに素（最大公約数は1）で すので、上記の命題は間違いであることが分かります。
よって、「１〜１００までの 数のうち、適当に５１個の数を選ぶと、この中には最大公約数を１とする 数２個が 必ず含まれている」。

解答・その６

（ペンネ−ム：夜ふかしのつらいおじさん）

１から順にｋつめごとに数をとるとｋの倍数が集められます。
Ｋ＝｛k, 2k, 3k,・・・・・・・・｝
このグループ内のどの２数も公約数としてｋをもちます。
１から１００までの数で考えたとき、

ｋの値	２	３	４	５	６	７	８	９	１０	・・・
グループの要素の個数ｎ（Ｋ）	５０	３３	２５	２０	１６	１４	１２	１１	１０	・・・

ｋが素数でないときはその因数の最小の数の場合まで１以外に公約数をもつ要素を 増やせます。
例えば、ｋ＝１０とすると、グループの要素の個数は１０個しかありませんが、 １０＝２×５なので　２の場合の５０個まで２を公約数とする要素の個数を増やせます。
さて、ｋが素数の場合、ｋの倍数のグループＫにｋの倍数以外の数ｐを入れてみま しょう。
するとｐはｋと必ず互いに素になります。 なぜなら、ｐはｋを因数にもたないからです。
１から１００までについては、ｎ（Ｋ）＝５０個までは公約数をもつ数を集められ ます。　（ｋ＝２の場合）
しかし、それ以上は集めることができません。
５１個になるとどうしても１以外に公約数のない２数ができてしまします。

解答・その７

（ペンネ−ム：かつ）

「一般の自然数では隣り合う自然数は公約数が１になる」と言うことです。 これは、容易にわかると思います。
一つの自然数は次のように表すことができます。
ｎ＝ａ^αｂ^β・・・ｄ^γ とできる。
つまりその隣り合う自然数はこれに１をたす（ひく）ことで表される。
ｎ＋１＝ａ^αｂ^β・・・ｄ^γ＋１ となる。
よってこの二つの自然数には共通する約数は無い。 つまり公約数は１である。

と言うことで、実際の問題に行きましょう。
１〜１００までの自然数から５１個の数を取り出します。
上のものから隣り合ってしまうと公約数が１になってしまうので一つおきにとります。
すると５０個しか取れません。つまり１個数字を取らなければならないので、必ずどこかと隣り合うわけです。
よって上の話から、１〜１００までの自然数から５１個取り出すと、 最低でも一つは公約数が１となるものが現れるわけです。
これは１００個の中から５１個取るところにこの問題の本質があるようです。

解答・その８

（ペンネ−ム：安里歩安彼）

１〜１００までを、次のような５０個に分ける。

（１）…１，２　（２）…３，４　（３）…５，６　…　（５０）…９９，１００

このとき、すくなくともひとつのグループに関して，そのグループに含まれる二つと もが，選ばれた５１個に含まれる。
（鳩ノ巣原理より）また、ｎとｎ＋１の公約数は、１の約数となるので１．
よって、その二つは互いに素となり、示された。

＊：かの数学者，ポール・エルデシュはこの問題がお気に入りだったらしいです。

解答・その９

（ペンネ−ム：浜田　明巳）

１からｎ（ｎ≧２）までの自然数からｍ個の数を適当に選ぶ．
するとこの中には最大公約数を１とする２数が必ず含まれることを証明する．
ただしｍ＝［(ｎ＋１)／２］＋１（［　］はガウス記号）である．
ｍ個の数をａ(１)，ａ(２)，・・・，ａ(ｍ)
　　（１≦ａ(１)＜ａ(２)＜・・・＜ａ(ｍ)≦ｎ）とする．
ａ(ｉ＋１)−ａ(ｉ)（１≦ｉ≦ｍ−１）の最小値が２以上であるとすると，

ａ(ｉ＋１)	≧ａ(ｉ)＋２（１≦ｉ≦ｍ−１）
∴ａ(ｍ)	≧ａ(ｍ−１)＋２×１
	≧ａ(ｍ−２)＋２×２
	≧・・・
	≧ａ(１)＋２(ｍ−１)
	＞２(ｍ−１)

ここでｎが偶数のときｍ＝ｎ／２＋１であり，ｎが奇数のときｍ＝(ｎ＋１)／２＋１であるので，
２(ｍ−１)＝ｎ　or　２(ｍ−１)＝ｎ＋１
　　∴２(ｍ−１)≧ｎ
　　∴ａ(ｍ)＞２(ｍ−１)≧ｎ
　　∴ａ(ｍ)＞ｎ
これはａ(ｍ)≦ｎであることに矛盾する．
故にａ(ｉ＋１)−ａ(ｉ)（１≦ｉ≦ｍ−１）の最小値は１である．
あるｋ（１≦ｋ≦ｍ−１）を選び，ａ(ｋ＋１)−ａ(ｋ)＝１であるとする．
ａ(ｋ＋１)＝ａ(ｋ)＋１とａ(ｋ)の最大公約数をｇとする．
ｇ＞１とし，ａ(ｋ)＋１＝ｂｇ，ａ(ｋ)＝ｃｇ（ｂ，ｃの最大公約数は１）とする．
　　∴ａ(ｋ)＝ｂｇ−１＝ｃｇ
　　∴(ｂ−ｃ)ｇ＝１
　これはｂ−ｃが整数であり，ｇ＞１であることに矛盾する．
　　∴ｇ＝１
　これで証明された．
　この問題は，ｎ＝１００の場合である．

鳩の巣が５つあって、鳩が６羽いたとする。 そうすると必ずどこかの巣には２羽以上の鳩がいることになる、これが「鳩の巣原理」と呼ばれるものです。

問題１については、解答・その１でＭＩＮＩＭＩＮＩ３２さんがおっしゃっているように、 最もアンラッキ−なケ−スを考えなければなりません。（誰にとってアンラッキ−か、ですって？）
解答・その３で浜田　明巳 さんが一般形を示してくださいました。

問題２について、解答・その４のkiyoさんの解答を私なりにもう少しかみくだくと、 一番倍数の数の多い２の倍数でも５０個しかとれない、従って５１個目は２の倍数とはならない。 そうなると、その５１番目の数は、他の５０個すべてと１以外の公約数をもつのは不可能である、ということでしょうか。 解答・その５のマサボーさんの解答もそういう意味だと思います。

解答・その７のかつさんや解答・その８の安里歩安彼さん がおっしゃっている、 「隣り合う自然数の最大公約数は１である」を自明としている件はいいですかね？
任意の２数a,b(a＞b)の公約数をpとすれば、a-bもpでわれるはずです。 隣り合った２数では、a-b=1ですからp=1以外にはありえません。
解答・その９の浜田　明巳さんの解答は、お二方と似ているようで微妙に異なりますね。
１００個の整数の中から５１個の整数を選ぶと、間隔が１(つまり互いに素)になるところが必ずできてしまう、 ということを一般形で示してくださいました。

E-mail 戻る ホ−ムペ−ジ