[spielfrieks] Boardgame-like problem at this year's International Mathematical Olympiad

[Wei-Hwa Huang [e-mail] [spielfrieks]]

[Bcc:ed to several board game mailing lists I'm on]

This year's International Mathematical Olympiad had one of their
hardest problems ever, but it was somewhat game-themed, so I figured
some folks here would be interested in thinking about it. I've
rephrased the question to be less "mathy":

You're playing a game of "catch the rabbit" on an infinite-sized
board. Each of you are on some location on the board, and you take
turns, with the rabbit going first. The goal of the rabbit is to get
far away from you; your goal is to stay close to the rabbit. Here are
the rules:

* You and the rabbit start on the same spot.

* On the rabbit's turn, it moves exactly 1 inch away, in any direction
(that is, it's somewhere on the edge of a 1-inch radius circle from
where it was).

* You don't see where the rabbit goes; it's invisible. However, you
have a rabbit tracker -- after the rabbit takes a turn, the rabbit
tracker gives you a location and says that "the rabbit is within 1
inch of this location". While the rabbit tracker can't lie, it is in
cahoots with the rabbit and can deliberately choose a location to
mislead you.

* On your turn, you must move exactly 1 inch away, in any direction.
The rabbit (and the rabbit-tracker) know exactly where you are.

* The game lasts 1,000,000,000 rounds (each of you get 1 billion turns).

Either come up with a strategy such that at the end of the game,
you're guaranteed to be within 100 inches of the rabbit -- or come up
with a strategy for the rabbit such that the end of the game, you're
guaranteed to be more than 100 inches away from the hunter.

[Clay Blankenship [e-mail] [spielfrieks]]

Some thoughts on the rabbit problem. Space added for spoiler protection
but it's just some ideas.


10


9


8


7


6


5


4


3


2


1


That is a good problem. At first, it seems like just going straight
towards the rabbit's stated location ought to keep you close to him, but
perhaps the accumulation of errors over a billion turns can add up to 100
inches (even though the further away he gets, the less he can trick you in
terms of angle). My next thought is that by aiming for somewhere midway
between his last two stated positions might make it harder for the tracker
to trick you. I'm curious as to what the solution is and how it is worked
out.

Clay