2024年 日本数学オリンピック本選 第３問 解答例
$${xy}$$平面において、$${x}$$座標と$${y}$$座標が$${1}$$以上$${2000}$$以下の整数である点を良い点とよぶ。また、以下の条件をすべてみたす$${4}$$点$${A(x_1, y_1), B(x_2, y_2), C(x_3, y_3), D(x_4, y_4)}$$について、折れ線$${ABCD}$$を$${Z}$$型折れ線とよぶ。
・$${A, B, C, D}$$はすべて良い点である。
・$${x_1 < x_2, y_1 = y_2}$$.
・$${x_2 > x_3, y_2 - x_2 = y_3 - x_3}$$.
・$${x_3 < x_4, y_3 = y_4}$$.
$${n}$$個の$${Z}$$型折れ線$${Z_1, Z_2, \cdots, Z_n}$$が以下の条件をみたすとき、正の整数$${n}$$としてありうる最小の値を求めよ。
どの良い点$${P}$$についても、$${1}$$以上$${n}$$以下の整数$${i}$$が存在して、$${P}$$が$${Z_i}$$上にある。
ただし、折れ線$${ABCD}$$とは、線分$${AB, BC, CD}$$（いずれも端点を含む）を合わせた図形のことである。
考え方：
点はたくさんありますが、（特徴的な）一部の点を考えれば
必要な最小の$${n}$$を推定することができます。
そして、そのときに見つけた条件を満たすように、
$${n}$$個の条件を満たす$${Z}$$を提示すれば完成です。
第３問にしてはかなり簡単な問題だと思います。
解答例：
良い点の中で$${x}$$座標が$${1}$$または$${2000}$$の点を「端の良い点」と呼ぶとすると、これは全部で$${4000}$$個ある。
端の良い点を$${4}$$個つ通ることのできる$${Z}$$は
$${A(1, 2000), B(2000, 2000), C(1, 1), D(2000, 1)}$$で定まる$${Z}$$のみであり、
それ以外の$${Z}$$は$${1}$$つにつき
高々$${3}$$個しか端の良い点を通ることができない。
よって、$${n \geqq 1 + (4000 - 4) / 3 = 1333}$$が必要となる。
$${n = 1333}$$のとき、
$${Z_1}$$を$${A(1, 2000), B(2000, 2000), C(1, 1), D(2000, 1)}$$で定まる折れ線とし、
$${2\geqq i \geqq 667}$$に対しては$${Z_i}$$を
$${A(1, 2001 - i), B(2000, 2001 - i), C(665 + 2i, 666 + i), D(2000, 666 + i)}$$
で定まる折れ線として、
$${668\geqq i \geqq 1333}$$に対しては$${Z_i}$$を
$${A(1, 2001 - i), B(2668 - 2i, 2001 - i), C(1, i - 666), D(2000, 666 + i)}$$
で定まる折れ線とすれば条件を満たす。
解答例では2000×2000に対して同じ思想で条件を満たす書き方を記述している。
以上より$${n}$$の最小値は$${1333}$$である。
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
間違いなど見つけましたら是非お教えください。
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)