読者です 読者をやめる 読者になる 読者になる

数学塾variée@吉祥寺

数学塾の中の人の日記

具体例が意外な図形に

数学/数オリ

2015年のカナダの第3問を解いてみました。

On a (4n+2)(4n+2) 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

正確な訳は省略しますが,

(4n+2)×(4n+2) のマス目の四隅の1つをスタートして,すべてのマスを1回ずつ通って元のマスに戻ってくるカメの一歩一歩を行や列への出入りと考える。
「入り」の回数を行ごと,列ごとに数えたときの最大値の最小値を求めよ。

という問題です。

解法は「不等式評価した後,具体例を作る」というものです。その具体例がすごく変でした。公式解答には n=3 の例が載っていて,ナスカの地上絵のような図になります。

f:id:variee:20160102235703g:plain

この手の問題は極端な場合が最大値や最小値を与えることが多いのですが,毎回曲がるわけでもなく,できるだけ直進するわけでもない場合が答えを与えるのが面白く,そして難しいと思います。

でも,解くときには普通 n=1 から考えますよね。この場合の経路はハーケンクロイツです。こんなのありなのか…… 政治的に正しいのか,と思いました。

f:id:variee:20160102235648g:plain