Alice and Bob are playing hide and seek. Initially, Bob chooses a secret fixed point $B$ in the unit square. Then Alice chooses a sequence of points $P_0, P_1, \ldots, P_N$ in the plane. After choosing $P_k$ (but before choosing $P_{k+1}$) for $k \geq 1$, Bob tells "warmer'' if $P_k$ is closer to $B$ than $P_{k-1}$, otherwise he says "colder''. After Alice has chosen $P_N$ and heard Bob's answer, Alice chooses a final point $A$. Alice wins if the distance $AB$ is at most $\frac 1 {2020}$, otherwise Bob wins. Show that if $N=18$, Alice cannot guarantee a win.
Problem
Source: Baltic Way 2020, Problem 10
Tags: combinatorics, combinatorics proposed
Tintarn
17.11.2020 20:03
Effectively, what Alice can do is to choose $18$ lines and she will find out on which side of this line, the point $B$ happens to be (with the case of $B$ being on that line belonging to one specific side of that line). One can now argue in two different ways that she cannot win too quickly:
Via areaIn the worst case, the point $B$ is always in the remaining part which has the larger area. So no matter which $18$ lines she chooses, it can happen that the remaining possible part has area at least $\frac{1}{2^{18}}$.
But supposing she can win, she would have to know that $B$ is in a certain disc with radius $\frac{1}{2020}$.
But this disc has area $\frac{\pi}{2020^2}<\frac{4}{1024^2}=\frac{1}{2^{18}}$.
Via lattice pointsConsider the $(N+1)^2$ points with coordinates multiples of $\frac{1}{N}$ inside the unit square. In the worst case, the point $B$ is always in the remaining part which has the larger number of these points. So no matter which $18$ lines she chooses, it can happen that the remaining possible part has at least $\frac{(N+1)^2}{2^{18}}$ points in it.
If $N=2^9$, this is more than one, so it can happen that there are two points in this part with distance at least $\frac{1}{N}=\frac{1}{512}$.
So she cannot do better than half the distance of these points, i.e. not better than $\frac{1}{1024}>\frac{1}{2020}$.
JustKeepRunning
05.04.2021 20:22
Notice that if we can show that in the worst case scenario, Alice is unable to win with the optimized algorithm, then we are done. Notice that if $P_k$ is "warmer" than $P_{k+1},$ this just means that if I draw the perpendicular bisector of $P_kP_{k+1}$ and this splits the remaining possible area into two regions, then that means the region containing $P_k$ also contains $B$. Notice that we just want to minimize the larger area, and evidently, if we make the two areas $m_1$ and $m_2,$ then $m_1+m_2=1\implies 2max(m_1,m_2)\geq 1\implies max(m_1,m_2)\geq \frac{1}{2}$ of the remaining possible area. (Notice that we can assume the perpendicular bisector of the two points divides the remaining possible area into two regions because if it doesn't even intersect the area, then the whole area is a region, clearly non-optimal). This minimum case is achievable because there obviously exists a line which divides the remaining area into two equal parts which does not pass through $P_k,$ and reflection $P_k$ over this line is sufficient to make it so that Bob's response halves the possible area. Therefore, after hearing Bob's comments for $P_1, \cdots P_{18},$ the best Alice can gurantee the area down to is $\frac{1}{2^{18}}$. Notice that if Alice can guarantee a win, she can put a disk which complete covers the square, meaning that $\pi \cdot \frac{1}{2020^2}\geq \frac{1}{2^{18}}$ must be true. However, this rearranges to $\pi \geq \frac{2020^2}{2^18} > \frac{1024^2}{2^{18}}=4$, clearly a contradiction. We are done.