2015 年のカナダの数オリ第 3 問を解いてみました。
On a
square grid, a turtle can move between squares sharing a side.
The turtle begins in a corner square of the grid and enters each square exactly once, ending in the square where she started.In terms of n, what is the largest positive integer k such that there must be a row or column that the turtle has entered at least k distinct times ?
http://www.artofproblemsolving.com/community/c6h1081581p4756469
正確な訳は省略しますが，だいたいこんな感じです。
のマス目の四隅の 1 つをスタートして，すべてのマスを 1 回ずつ通って元のマスに戻ってくるカメの一歩一歩を行や列への出入りと考える。
「入り」の回数を行ごと，列ごとに数えたときの最大値の最小値を求めよ。
解法は「不等式評価した後，具体例を作る」というものです。その具体例がすごく変でした。公式解答には の例が載っていて，ナスカの地上絵のような図になります。
この手の問題は極端な場合が最大値や最小値を与えることが多いのですが，毎回曲がるわけでもなく，できるだけ直進するわけでもない場合が答えを与えるのが面白く，そして難しいと思います。
でも，解くときには普通 から考えますよね。この場合の経路はハーケンクロイツです。こんなのありなのか…… 政治的に正しいのか，と思いました。
