読者です 読者をやめる 読者になる 読者になる

数学塾variée@吉祥寺

数学塾の中の人の日記

『ピジョンの誘惑』読んでます

読書 数学/数オリ

『ピジョンの誘惑』という鳩ノ巣原理(部屋割り論法)の問題ばかり70問集めた本を読んでいます。半分くらい読んだところです。

ピジョンの誘惑  論理力を鍛える70の扉

ピジョンの誘惑 論理力を鍛える70の扉

部屋割り論法を2回使う問題がたまに出てきて新鮮です。このタイプの問題は今まで解いたことがありませんでした。

部屋割り論法 x 2

(問題11)1つの野球チームの選手の中には,誕生日の曜日が同じ人が2組以上いる。

9人を7つの曜日(=7つの部屋)に入れるので,2人以上入る部屋があります。その部屋に入る人のうち1人を除いた8人を7つの部屋に入れると,また相部屋が生じます。誕生日の曜日が同じ3人がいるか,誕生日の曜日が同じ2人が2組あるので証明終わり。

(問題33)100人の人がいる。その中に,そこにいる自分以外の50人以上の人と知り合いだという人が2人いると,その2人は知り合いか,さもなければ,2人以上の共通の知り合いがいる。

これも「鳩ノ巣原理を2回」で問いてありましたが,自分としては和集合を使う方がわかりやすいかな。知り合いが50人以上いる2人をp, qとして,それぞれの知り合いの集合をP, Qとします。集合Xの元の個数をn(x)であらわすと,

{ \displaystyle n(P\cup Q)=n(P)+n(Q)-n(P\cap Q)}

p, qが互いに知り合いでないとするとp, qはP, Qに含まれないので,n(P ∪ Q)は 100-2=98 以下。一方,n(P)とn(Q)は50以上なのでn(P ∩ Q)は2以上です。証明終わり。

数オリの問題から

さて,最近解いた問題の中にも部屋割り論法を使うものがありました。

相異なる65個の自然数が与えられており,どの数も2016以下である。
この中から次の条件をみたすように相異なる4つの数a, b, c, dを選べることを証明せよ。

(条件)a+b-c-dは2016で割りきれる
(2016 アゼルバイジャン・ジュニア)

これは和をもとに部屋を作ればOK。このタイプの問題はどこかで見たな〜と思って類題を探しました。まず,「余りが等しい」を「値が等しい」に変えた問題。

100以下の相異なる正の整数16個の中には,相異なる4つの数a, b, c, dであってa+b=c+dとなるようなものが存在することを示せ。(『数論の精選102』・基本17)

和に注目すると部屋が多すぎてうまくいかないので,条件をa-c=d-bと変形して差をもとに部屋を作ります。この発想が難しい。

次は和だけでなく,足す前の値とも等しいことを示す問題。

nは3より大きい整数とし, a0, a1, ..., anは

{ \displaystyle 1 \leqq a_0 < a_1 < \cdots < a_n \leqq 2n−3}

をみたす整数とする。このときai+aj =ak+al = am となるような相異なる整数 i, j, k, l, mが存在することを示せ。(1990 JMO本選)

これは差に注目することに加えて和集合を使います。「100人の〜」の問題で和集合を使うのはそう不自然ではありませんが,こちらで思いつくのはかなり難しいと思います。鳩ノ巣原理(部屋割り論法)を使いこなすにはかなりの修練が必要です。

組合せ論の精選102問 (数学オリンピックへの道)

組合せ論の精選102問 (数学オリンピックへの道)

数学オリンピック事典―問題と解法

数学オリンピック事典―問題と解法