JMO対策　鳩ノ巣原理編

PCTです。今日はJMOで結構な頻度で使う鳩ノ巣原理を解説？をして最後に鳩ノ巣原理$+α$ の問題を書いていきます。

鳩ノ巣原理とは

$N$ 個のものを $M$ 個のものに分ける時少なくともある箱には $\lceil \frac{N}{M}\rceil$ 個以上のものが入っている。

自明な定理ですがどこにあるかわからなくても確実に存在するという性質が色んなところで役に立ちます。

例題

次のような有名な問題があります。これも鳩ノ巣原理で解くことが出来ます。

$x,y$ 平面において $5$ 個の格子点を選ぶ。 $2$ 個の点を上手く選ぶことによってその $2$ 個の点の中点も格子点になることを示せ。

まず格子点の状態としてあり得るものは $(偶数、偶数)$、$(偶数、奇数)$、$(奇数、偶数)$、$(奇数、奇数)$ の $4$ 個です。鳩ノ巣原理よりこの内 $2$ 個以上の点が属するものが存在します。そこから $2$ 点選ぶことにより中点も格子点となります。より示された。

では最後に鳩ノ巣原理を使う少し難しめの問題を書いて終わりにします。解説はまた書きます。

その$1$(難易度：低)
$xy$ 平面上に $3$ 以上かつ奇数個点を取る。格子点である必要はない。この時それぞれの点の距離は全て異なる。それぞれの点に対して、自分自身を除き、一番近い点に印をつけることを繰り返す。この時全ての点に印がつくような点の配置は可能か？

その$2$(難易度：高)
$n$ を正の整数とします。次の条件を満たすように区別できる $n$ 枚のカードに $1$ 個ずつ $2$ 以上の整数を書き込みます。

• 任意のカードに書かれた整数 $a$ とその素因数 $p$ において $p$ は $50$ 以下であり $p^{51}$ は $a$ を割り切らない。

• $n$ 枚のカードからどのように $1$ 枚以上 $n-1$ 枚以下カードを選んでも、選ばれたカードに書かれた整数の積は選ばれなかったカードの積で割り切れない。
  このような書き込み方が存在する $n$ として考えられる最大の値を $m$ とします。$n=m$ の時の書き込み方の個数を求めて下さい。