For two points $P,Q$ with integer coordinates in $2$ dimensions, we say that $P$ "sees" $Q$ iff the segment $PQ$ contains no other points with integer coordinates. Do there exist points $P_1,\ldots,P_{100}$ such that $P_i$ sees $P_{i+1}$ for $i=1,2,\ldots,99$, $P_{100}$ sees $P_1$, no other pair of points sees each other, and no three points are collinear?
(British Math Olympiad 2014/15)
If we only need $4$ points, we can use $(-1,0),(0,1),(1,0),(0,-1)$. How can we generalize to more points?
This is a construction question, so think about what the possibilities of approach are. Clearly, forward induction, backward induction, greedy algorithm are bad candidates. This leaves us with the structure avoider and finder approach. (See link for details).
Claim: Point $(x_1, y_1), (x_2, y_2) $ see each other if and only if $ \gcd ( x_1 - x_2 , y_1 - y_2 ) \neq 1 $.
This is obvious. Proof it yourself. This is the structure that we're trying to find / avoid.
General Case 1: $k+2$ points, where $k = p_2 - p_1 $ is the difference of 2 primes with $p_1 > k$.
Consider the $k+1$ points of the form $(x_n, y_n) = (n, n^2)$ from $ n = 1$ to $n = p_2-p_1 + 1$. From the above, since $ \gcd (i-j, i^2 - j^2 ) = i-j$, hence these $k$ points are only visible to their neighbors, and not anyone else.
Let the last point be denoted by $ (x_0, y_0)$.
Observe that $\gcd( x_0 - i, y_0 - i^2 ) = \gcd( x_0 - i, y_0 - x_0 ^2 ) $.
We set $x_0 = p_2+1$. This gives us $x_0 - 1 = p_2$ and $x_0 - (k+1) = p_1$.
Hence, to satisfy the conditions, we need $p_ 1 \not \mid y_0 - x_0^2 , p_ 2 \not \mid y_0- x_0^2 $, but $j \mid y_o - x_0^2 $ for all $ p_1 < j < p_2 $.
This is satisfied by taking $y_0 - x_0^2 = LCM ( j) $, since by condition $2p_1 > p_1 + k = p_2 $ and thus $p_ 1 \not \mid LCM (j)$.
Now, apply this to $ k = 98, p_1 = 101, p_2 = 199 $ and the original problem is done.
General Case 2: $p+1$ points, where $p$ is prime. It doesn't work for 100.
This is actually similar to the first, with the understanding of "$p_1 = -1$", and working around the difficulties that arise. I actually came up with this case first, then tried to generalize it further.
Now, consider the $p$ points of the form $ (n, n^2)$. From the above, since $ \gcd (i-j, i^2 - j^2 ) = i-j$, hence these $p$ points are only visible to their neighbors, and not anyone else.
Let the last point be denoted by $ (x_0, y_0)$.
Observe that $\gcd( x_0 - i, y_0 - i^2 ) = \gcd( x_0 - i, y_0 - x_0 ^2 ) $.
We will pick $x_0 = p+1$, which gives us $ \gcd ( p+1 - p, y_0 - p^2 ) = 1$ for any $y_0$.
For $ i = 2$ to $p-1$, we will need $ \gcd ( p+1 - i, y_0 - i^2 ) \neq 1$, or that $\gcd( p+1 - i, y_0 - (p+1)^2 ) \neq 1 $. In fact, we will let $\gcd( p+1 - i, y_0 - (p+1) ^ 2 ) = p+1 - i$ itself. This gives us the choice of $y_0 - (p+1)^2 = K \times LCM ( 2, 3, \ldots, p-1)$.
Finally, we must ensure that $\gcd(p, y_0 -1^2 ) = 1$, which is achieved with $K=1$, since $y_0 - (p+1)^2$ will not be a multiple of $p$.
Note: The use of points on the specific polynomial $f(n) = n^2$ is not required. Any polynomial with integer coefficients will typically work, but it also has to satisfy the condition that no 3 integer points are collinear. In particular, quadratics satisfy this trivially, and so I chose the simplest quadratic.
I suspect that this statement is true for all $n$, but I don't know how to show that as yet. As seen, primes, and prime gaps, are extremely important.