gooドクター有料プランが1ヶ月間無料!

部屋割り論法を利用する問題の解き方の方針などを教えてください。

⑴ 1 辺の長さが1 の正六角形の周および内部に7 個の点をとったとき,そのうちの
  2 点で,距離が1 以下となるようなものが少なくとも1 組存在することを示せ。
⑵ n を自然数とするとき,相異なるn + 1 個の整数の中に,その差がn の倍数
  である2 数が必ず存在することを示せ。
⑶ 100 以下の自然数から51 個を選ぶと,必ず和が101 になる2 数が存在すること
  を示せ。
⑷ 100 以下の自然数から21 個を選ぶと,この中にa + b = c + d をみたす4 数a,b,
  c,d が必ず存在することを示せ。

gooドクター

A 回答 (1件)

「鳩ノ巣論法」とも呼ばれます。



(1) 正六角形を、一辺の長さが1の正三角形6つに分ける。この正三角形は「その正三角形の3つの頂点を中心とする半径1の3つの円弧で囲まれてできる図形」の内部に収まりますから、つまり正三角形1個の中にもし2つの点があれば、これらの点同士の距離は1以下です。で、正三角形は6つ、点は7つ。

(2)自然数mも自然数kもnで割った余りが同じ、すなわち m/n = u余りr で、k/n = v余りr であるなら、
  m = nu + r
  k = nv + r
なので、
  m-k = n(u-v)
だから差がnの倍数である。さて、自然数をnで割った余りは0,1,2,...,n-1のn通りしかありません。

(3) 一つずつ選んでいくとしましょう。選んだ数がnだとすると、それ以降、nと101-nはもはや選べない。つまり1回選択するたびに、以降に選べる候補は2個ずつ減る訳です。
 言い換えれば、{1〜100}は、{n, 101-n}(n=1〜50)という50個の集合に(重複なく)分割される。1つ数を選ぶと、それはこれら50個の集合のうちのどれかに含まれ、その集合の要素は二度とは選べない。さて集合は50個で、選ぶ数の個数は51個。

(4)まず、1~100の自然数から21個を選んだとします。で、その21個の中から2個p,qを(重複なく)選んで和(p+q)を作ると、p,qはどちらも1以上100以下なので、和(p+q)は3以上199以下、つまり(p+q)は高々197通りの値のうちのどれか、ということです。一方、相異なるn個の数から2つp,qを(重複なく)選ぶ選び方は nC2 = n(n-1)/2 通り。だから n=21の場合、210通りのペア{p,q}がある訳です。
    • good
    • 1

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

gooドクター

このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング