鳩の巣原理 ［2016 神戸大・理（後）］

イズミの解答への道

　mが小さいときは、場合の数として数え上げていきます。mが大きくなると、鳩の巣原理という原理が関係します。
　鳩の巣原理とは、「 n 個の引き出しに n + 1 個のものをいれようとすると、かならずどこかには1つ以上のものが入ってしまう」という、言われてみれば当たり前なことを指すのですが、高校ではあまり扱わないため知っている人は少ないでしょう。
　この問題はその原理について、 m が小さい方から数え上げさせることで、途中で気づかせてくれるよい問題です。

解答

　2点の中点が格子点となるためには、2点の x 座標、 y 座標のそれぞれの偶奇が一致していなければならない。
　そこで、9つの格子点を次の4グループに分ける。
　　① x , y ともに偶数： ( 0 , 0 )
　　② x が偶数、yが奇数： ( 0 , 1 ) , ( 0 , -1 )
　　③ x が奇数、yが偶数： ( 1 , 0 ) , ( -1 , 0 )
　　④ x , y ともに奇数： ( -1 , -1 ) , ( -1 , 1 ) , ( 1 , -1 ) , ( 1 , 1 )
　このとき、ある2点の中点が格子点とならない条件は、その2点が異なるグループに属していることである。

　まずは a₂ を求める。
　4つのグループの中から異なる2つのグループを選ぶのは、以下の ₄C₂ = 6通りで、それぞれの場合の数は、

• ①と②から点を選ぶ方法は2通り
  
• ①と③から点を選ぶ方法は2通り
  
• ①と④から点を選ぶ方法は4通り
  
• ②と③から点を選ぶ方法は 2 × 2 = 4 通り
  
• ②と④から点を選ぶ方法は 2 × 4 = 8 通り
  
• ③と④から点を選ぶ方法は 2 × 4 = 8 通り
  

となる。以上より、
　　a₂ = 2 + 2 + 4 + 4 + 8 + 8 = 28

　次に a₃ を求める。4つのグループの中から異なる2つのグループを選ぶのは、以下の ₄C₃ = 4 通りで、それぞれの場合の数は、

• ①と②と③から点を選ぶ方法は 1 × 2 × 2 = 4 通り
  
• ①と②と④から点を選ぶ方法は 1 × 2 × 4 = 8 通り
  
• ①と③と④から点を選ぶ方法は 1 × 2 × 4 = 8 通り
  
• ②と③と④から点を選ぶ方法は 2 × 2 × 4 = 16 通り
  

　a₄は、①、②、③、④のグループそれぞれから1点ずつを選ぶ場合なので、
　　a₄ = 1 × 2 × 2 × 4 = 16
である。

　m ≧ 5 の場合、どのように選んでも同じグループから2つ以上の点を選ばなければならなくなる。このとき同じグループから選んだ2点の中点は格子点となってしまうため、題意を満たす選び方は出来ない。
　よって、
　　a₅ = a₆ = a₇ = a₈ = a₉ = 0
である。

解説

鳩の巣原理

　n + 1 個のものを n 個の引き出しにいれると、必ずいずれかの引き出しには 2 つ入る。この当たり前の事実のことを鳩の巣原理という（あるいは、ディリクレの原理、引き出し論法などともいう）。
　大学入試でもあまり出題されることはないが、知らないと手を出しにくい問題なので、以下で過去に出題された問題に触れておこう。

例題（中点が格子点タイプ）

　まずは今の問題と似た問題を紹介しよう。

【解答】
　格子点の座標は、その成分の偶奇によって、
　　　( 偶 , 偶 ) , ( 偶 , 奇 ) , ( 奇 , 偶 ) , ( 奇 , 奇 )
の4種類に分けられるため、 5 つの格子点を任意に選ぶと、そのうちの 2 つは必ず x , y 両方の座標の奇偶が一致し、その中点は格子点となる。よって題意は示された。

例題（割り算の余りタイプ）

　次に、同じく神戸大で昔出題された問題を解いてみましょう。

【解答】
(1)　すべての整数は、3で割った時に1余る数、2余る数、余りのない数の3つのグループに分けられるので、鳩の巣原理より、4つの整数があれば、どれかのグループには2つ以上の整数がわけられる。
　その1つのグループに入った2つ以上の整数のうちの2つを a , b とすると、
　　a = 3k + r
　　b = 3l + r
となる（ k , l は整数、 r は 0 , 1 , 2 のいずれか）ので、これらの差は、
　　a – b = 3 ( k – l )
となり、3の倍数となる。以上より、4つの整数から適当に2つを選べば、その差が3の倍数となるようにできることが示された。

(2)　nで割った余りは 0 から n – 1 の n 種類ある。よって、 n + 1 個の数
　　3 , 33 , 333 , … , 33…3（ 3 が n + 1 個並ぶ数）
のうち、 n で割った余りが等しい2つが必ず存在する。それらについて、大きい方から小さい方を引くと、
　　33…3000…0
の形となり、これは n で割り切れる。よって題意は示された。

広島大の過去問

　広島大では、この鳩の巣原理を説明したうえで、それをうまく利用して解いてください、という問題が出題されている。これも紹介しておこう。