鳩の巣原理 [2016 神戸大・理(後)]

 m を 2 ≦ m ≦ 9 をみたす自然数とする。 xy 平面上の点のうち、 x 座標と y 座標がともに整数のものを格子点という。 x 座標と y 座標がともに -1 , 0 , 1 のいずれかである 9 個の格子点を考える。これらの格子点から異なる m 個の格子点を選ぶ。選ばれた m 個の格子点のうち、どの異なる2点の中点も格子点とならないような m 個の格子点を選ぶ選び方の総数を am とおく。 am ( 2 ≦ m ≦ 9 )を求めよ。

[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点が異なるグループに属していることである。

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

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

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

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

  • ①と②と③から点を選ぶ方法は 1 × 2 × 2 = 4 通り
  • ①と②と④から点を選ぶ方法は 1 × 2 × 4 = 8 通り
  • ①と③と④から点を選ぶ方法は 1 × 2 × 4 = 8 通り
  • ②と③と④から点を選ぶ方法は 2 × 2 × 4 = 16 通り
となる。以上より、
  a3 = 4 + 8 + 8 + 16 = 36
である。

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

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

解説

鳩の巣原理

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

例題(中点が格子点タイプ)

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

 x – y 平面において、 x 座標、 y 座標が共に整数である点 ( x , y ) を格子点という。いま、互いに異なる 5 つの格子点を任意に選ぶと、その中に次の性質をもつ格子点が少なくとも一対は存在することを示せ。
 一対の格子点を結ぶ線分の中点がまた格子点となる。

[1996 早稲田大・政経]

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

例題(割り算の余りタイプ)

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

 次の(1)、(2)を証明せよ。
(1) 任意に与えられた相違なる4つの整数 x0 , x1 , x2 , x3 を考える。これらのうちから適当に2つの整数を選んで、その差が3の倍数となるようにできる。
(2) n を1つの正の整数とする。このとき、 n の倍数であり、桁数が ( n + 1 ) を超えず、かつ 33…3000…0の形で表される整数がある。

[1977 神戸大・理]

【解答】
(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 で割り切れる。よって題意は示された。

広島大の過去問

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

次の文章は、ある条件を満たすものが存在することを証明する際に、よく使われる「鳩ノ巣原理」(または抽出し論法とも言う)を説明したものである:
m個のものが、n個の箱にどのように分配されても,m > nであれば,2個以上のものが入っている箱が少なくとも1つは存在する。このことを鳩ノ巣原理という。例えば、3つの整数が与えられたとき,このうちの少なくとも2つはともに偶数であるか,又はともに奇数である。なぜならば、3つの整数を偶数であるものと奇数であるものとの2組に分けると、鳩ノ巣原理( m = 3 , n = 2)により,偶数の組または奇数の組に2つ以上の整数が入っているからである。この原理を用いて、次の命題(1)、(2)が成り立つことを証明せよ。ただし,証明はこの原理をどのように使ったかが分かるようにせよ。
(1) 1辺の長さが2の正三角形の内部に、任意に5個の点を取ったとき、そのうちの2点で、距離が1より小さいものが少なくとも1組存在する。
(2) 座標空間で、その座標がすべて整数であるような点を格子点という。座標空間に9個の格子点が与えられたとき、そのうちの2点で、中点が又格子点であるものが少なくとも1組存在する。

[1989 広島大・教育(後)]

シェアする

  • このエントリーをはてなブックマークに追加

フォローする