東久留米 学習塾 塾長ブログ

東京都東久留米市滝山の個別指導型学習塾「学研CAIスクール 東久留米滝山校」塾長白井精一郎のブログ

ジュニア数学オリンピックの簡単な問題(122)

2017-03-20 12:15:38 | 数学・算数の話
こんにちは。東久留米市の学習塾塾長です。

毎日春らしい陽気が続いています。今夜から天気は下り坂ですが、明後日には回復して、週末にはいよいよ桜の開花になるようです。春真っ盛り目前といったところです。

さて、今回は2017年ジュニア数学オリンピック予選に出題された場合の数の問題を取り上げます。

問題は、
「nを正の整数とする。 xy平面からn個の点を選ぶと、これらは次の条件をみたしていた。

● いずれもx、y座標がともに0以上2017以下の整数である。

● この中から相異なる2点(a,b)、(c,d)を選ぶと、2点の選び方によらず la-cl≠lb-dl をみたす。

このようなことが起こりうるnのうち最大のものをNとしたとき、xy平面から条件をみたすようにN個の点を選ぶ方法は何通りあるか。」
です。

早速、取り掛かりましょう。

1つ目の条件は、xy平面から選ばれたn個の点が、0≦x,y≦2017を満たす格子点であることを表しています。

2つ目の条件は、図1のように、xy平面上のある格子点(a,b)が選ばれた場合、他の点は、(a,b)を通る傾き±1の直線(紫色の直線)上にないということです。

▲図1.(a,b)が選ばれた場合、他の点は紫色の直線上にありません

これらを基にして、nの最大値Nを調べましょう。

図2のように、点Pを領域の周辺上に置いた場合、点Pを通り傾きが1の直線上(紫色の直線上)と傾き-1の直線上(赤色の直線上)にある格子点には他の点を置くことができません。


▲図2.領域の周上と内部に点を置いた場合を比べます

それに対して、領域の内部に点Qを置いた場合、点Qを通り傾きが1の直線上(紫色の直線上)と傾きが-1の直線上(青色の直線上)に他の点を置くことができません。

ここで、点Pの場合と点Qの場合を比べると、紫色の直線上にある格子点の個数は同じですが、青色の直線上にある格子点の個数は赤色の直線上にある格子点の個数より多く、点Pのように領域の周上に点を置くほうが、点Qのように領域の内部に点を置くよりも、点を置くことができる格子点を多くすることができます。

実際に図3のように、0≦x,y≦2017の領域の周上であるy軸上(0≦y≦2016)とx=2017(0≦y≦2016)に合計2017×2=4034個の点を並べた場合を考えると、これは与えられた条件を満たしています。(2点がともにy軸またはx=2017上にあるとき、la-cl=0で、このとき、1≦lb-dl≦2016、2点がy軸とx=2017に1個ずつあるとき、la-cl=2017で、このとき、0≦lb-dl≦2016です)


▲図3.y軸上とx=2017上の0≦y≦2016に点を置きました

ここで図4のように、領域の周上にある1個の点を取り除くと、の格子点に点を置くことができるようになりますが、そのなかの1つに点を置くと、で示した格子点に点を置くことができなくなります。


▲図4.領域の周上の格子点に点を置くとき、nを最大にすることができます

つまり、領域の周上の格子点に点を置くとき、点の個数を最大にすることができ、nの最大値Nは4034個になることが判ります。

あとは、領域の周上に4034個の点を置く場合の数を勘定すればお仕舞いです。

図5のように、xy平面上の0≦x,y≦2017の領域の周辺(原点、(2017,0)、(0,2017)、(2017,2017)は除く)に頂点を持つ45°傾いた長方形を考えると、この長方形の対角線上にある2点を選ぶことができます。


▲図5.45°傾いた長方形の対角線上の2点を選ぶことができます

このとき、長方形の個数は2016個で、対角線は2本なので、点の選び方は、2^2016通りです。

さらに、周辺の角に置く点の選び方は、正方形の領域の1つの辺上にある2点の選び方になるので、4通りになります。

したがって、すべての点の選び方は、2^2016×4=2^2018通りで、これが答えです。


楽しい問題です。

東久留米の学習塾学研CAIスクール 東久留米滝山校
http://caitakiyama.jimdo.com/
TEL 042-472-5533
ジャンル:
ウェブログ
コメント   この記事についてブログを書く
この記事をはてなブックマークに追加
« 平成29年度都立高校入試問... | トップ | 平成29年度都立高校入試問... »
最近の画像もっと見る

コメントを投稿


コメント利用規約に同意の上コメント投稿を行ってください。

数字4桁を入力し、投稿ボタンを押してください。

あわせて読む

トラックバック

この記事のトラックバック  Ping-URL