鳩ノ巣原理

2016年11月3日

鳩ノ巣原理の問題です。

1.(明治大)
(n-1)以下の引き出しにn個のものをしまえば,どこかの引き出しには2個以上のものが入らなくてはならない.(1)」
この至極当然の道理は,ディリクレの原理といって数学ではよく利用される.さて,この原理を使って,「どのような会合においても,その中に友人の数が同じであるような人が少なくとも2人はいる.」ことを証明しよう.ただし,友人関係は相互的であって,自分自身は友人とはいわない.
会合に集まったn人のおのおのに,その友人の数を対応させる.友人の数は最小0から最大n-1までにわたり得るが,0とn-1とが同時に現れることはない.(2)
したがって,友人の数はn-1を越えない.そこで,ディリクレの原理により,同じ友人数をもつ人が2人はいることになる.(3)
(1) なぜか,理由をわかりやすく述べよ.
(2) なぜか,理由を述べよ.
(3) ディリクレの原理をどう適用したか.

2.(愛知教育大)
Aを100以下の自然数の集合とする.また,50以下の自然数kに対し,Aの要素でその奇数の約数のうち最大のものが2k-1となるものからなる集合をA_kとする.
(1) Aの各要素は,A_1からA_{50}までの50個の集合のうちのいずれか1つに属することを示せ.
(2) Aの部分集合Bが51個の要素からなるとき,\dfrac{y}{x}が整数となるようなBの異なる要素x,~yが存在することを示せ.
(3) 50個の要素からなるAの部分集合Cで,その中に\dfrac{y}{x}が整数となるような異なる要素x,~yが存在しないものを1つ求めよ.

3.(神戸大)
次の(1), (2)を証明せよ.
(1) 任意に与えられた相異なる4つの整数x_0,~x_1,~x_2,~x_3を考える.これらのうちから適当に2つの整数を選んで,その差が3の倍数となるようにできる.
(2) nを1つの正の整数とする.このとき,nの倍数であり,桁数が(n+1)を超えず,かつ33 \cdots 3000 \cdots 0の形で表される整数がある.

4.
1をいくつか連続して並べた整数111 \cdots 1の中には2013で割り切れるものがあることを証明せよ.

5.((1) 早稲田大 (2) 神戸大)
(1) xy平面において,x座標,y座標がともに整数である点(x,y)を格子点という.いま,互いに異なる5個の格子点を任意に選ぶと,その中に次の性質をもつ格子点が少なくとも一対は存在することを示せ.
「一対の格子点を結ぶ線分の中点がまた格子点となる.」
(2) m2 \leqq m \leqq 9をみたす自然数とする.xy平面上の点のうち,x座標とy座標がともに整数のものを格子点という.x座標とy座標がともに-1,~0,~1のいずれかである9個の格子点を考える.これらの格子点から異なるm個の格子点を選ぶ.選ばれたm個の格子点のうち,どの異なる2点の中点も格子点とならないようなm個の格子点を選ぶ選び方の総数をa_mとおく.a_m~(2 \leqq m \leqq 9)を求めよ.

6.(広島大)
次の命題(1), (2)が成り立つことを証明せよ.
(1) 1辺の長さが2の正三角形の内部に,任意に5点をとったとき,そのうちの2点で,距離が1より小さいものが少なくとも1組存在する.
(2) 座標空間で,その座標がすべて整数であるような点を格子点という.座標空間内に9個の格子点が与えられたとき,その内の2点で,中点がまた格子点であるものが少なくとも1組存在する.

関連ブログはこちら
にほんブログ村 教育ブログへ にほんブログ村 受験ブログへ