Michael is at the centre of a circle of radius $100$ metres. Each minute, he will announce the direction in which he will be moving. Catherine can leave it as is, or change it to the opposite direction. Then Michael moves exactly $1$ metre in the direction determined by Catherine. Does Michael have a strategy which guarantees that he can get out of the circle, even though Catherine will try to stop him?
Problem
Source: Tournament of Towns 2007 - Fall - Junior A-Level - P3
Tags: combinatorics unsolved, combinatorics, combinatorial geometry
chaotic_iak
03.09.2011 11:51
For the first move, choose a random direction.
For each of the next move, choose one of the two directions perpendicular to the line formed by joining Michael's current spot and the center of the circle. This will always make Michael to get farther from the center of the circle. (In fact, if Michael was $\sqrt{x}$ meters away from the center, Michael will be $\sqrt{x+1}$ meters away from the center with Pythagorean Theorem.) Thus in 10000 moves, Michael will be on the boundary of the circle, and the next move will bring him outside the circle.
parmenides51
23.10.2024 17:06
discussed also here
sansgankrsngupta
24.10.2024 08:49
OG! The answer is yes Strategy and proof that it works : Michael, initially will move 1m away from the center(O). Let he be at a point $A_1$, next Michael choses a direction perpendicular to $OA_1$, so irrespective of whether Alice flips the direction or not, he shall move 1m perpendicular to $OA_1$. Let he be at the new point $A_2$, then he again, choses choses a direction perpendicular to $OA_2$, so irrespective of whether Alice flips the direction or not, he shall move 1m perpendicular to $OA_2$ and then he continues the process until he is at point $A_{10001}$. We shall prove by induction on $n$ that $AO_n = \sqrt(n) meters$. Note that here lengths are in meters:- $n=1$ is trivial. Assume it hold for $n=k$. We know that $OA_{n+1}$ is a right triangle at $A_{n}$ thus, by the pythagorean theorem, we have ${OA_{n+1}}^2={OA_{n}}^2+{A_{n}A_{n+1}}^2$, by induction hypothesis, ${OA_{n}}= \sqrt{n}$ and since he moves 1m away in each step so, ${A_{n}A_{n+1}}=1$. Thus we get ${OA_{n+1}}^2=n+1$ or ${OA_{n+1}}= \sqrt{n+1}$. Hence, induction is complete. Now we can ensure that $OA_{10001}= \sqrt{10001}m>100m$ and so we are done. Q.E.D Remark: A nice problem would be to find the minimum no. of moves Michael requires to escape. (According to me it should be the same i.e. 10001 moves$.
AshAuktober
03.12.2024 12:46
Wow, this is nice. We claim that indeed Michael can get out of the circle. We propose the following algorithm: At each move, Michael draws the radial line which he is on (in his head, not physically) and decides to move perpendicular to that. It can be seen by induction that his distance from the circle at the end of the $n$th move is precisely $\sqrt{n}$ metres. Therefore, at the end of the $10001$th move, his distance from the centre is $\sqrt{10001} > \sqrt{10000} = 100$ metres, so he will be out of the circle. Remark: That's a long amount of time to be in one circle. Hopefully Mr. Beast doesn't take inspiration @above indeed that is true and can be proven by seeing that the distance from the centre after n moves is at most $\sqrt{n}$.