Indian National Mathematical Olympiad

Let the $n$ points be $P_1, P_2, \ldots, P_n$.

Let $D$ be the set of all pairwise distances between the $n$ points. For each $d \in D$, Gauss writes down $\lfloor \log_2 d \rfloor$.

Let $d_{\min}$ and $d_{\max}$ be the minimal and maximal pairwise distances among the $n$ points.

All values written by Gauss are integers $k$ such that $2^k \le d < 2^{k+1}$ for some $d$ in $D$.

Thus, the set of distinct values written is contained in the set of all integers $k$ such that $2^k \le d_{\max}$ and $2^{k+1} > d_{\min}$, i.e.,
$$\lfloor \log_2 d_{\min} \rfloor \le k \le \lfloor \log_2 d_{\max} \rfloor$$

So the number of distinct values is at most $\lfloor \log_2 d_{\max} \rfloor - \lfloor \log_2 d_{\min} \rfloor + 1$.

Now, we bound this quantity in terms of $n$.

Let us fix the configuration of $n$ points. The minimal distance $d_{\min}$ is the smallest distance between any two points, and the maximal distance $d_{\max}$ is the largest.

Let us consider the ratio $d_{\max}/d_{\min}$.

For $n$ points in the plane, the maximal distance between any two points is at most the diameter of the convex hull of the points, and the minimal distance is at least the minimal separation between any two points.

Let us fix $d_{\min}$ and consider the maximal possible $d_{\max}$.

Suppose all points are placed so that the minimal distance is $d_{\min}$, and the maximal distance is $d_{\max}$.

Consider the following: For any point $P_i$, the number of other points within distance $2^k d_{\min}$ is at most the number of points that can be packed in a disk of radius $2^k d_{\min}$ with pairwise separation at least $d_{\min}$.

In the plane, the maximal number of points that can be packed in a disk of radius $R$ with pairwise separation at least $r$ is at most $\left(\frac{2R}{r}+1\right)^2$.

But we can use a simpler argument:

Let $d_{\max} \leq C n d_{\min}$ for some constant $C$ (since the diameter of $n$ points with minimal separation $d_{\min}$ is at most proportional to $n d_{\min}$).

Then,
$$\frac{d_{\max}}{d_{\min}} < C n$$

Therefore,
$$\lfloor \log_2 d_{\max} \rfloor - \lfloor \log_2 d_{\min} \rfloor + 1 < \log_2 (C n) + 2$$

But we need to show that the number of distinct values is less than $2n$.

Let us consider the following extremal configuration:

Suppose the $n$ points are placed on a straight line with equal spacing $d_{\min}$ between consecutive points. Then the maximal distance is $(n-1)d_{\min}$.

So,
$$\frac{d_{\max}}{d_{\min}} = n-1$$

Thus,
$$\lfloor \log_2 d_{\max} \rfloor - \lfloor \log_2 d_{\min} \rfloor + 1 \leq \lfloor \log_2 (n-1) d_{\min} \rfloor - \lfloor \log_2 d_{\min} \rfloor + 1 = \lfloor \log_2 (n-1) \rfloor + 1$$

So the number of distinct values is at most $1 + \lfloor \log_2 (n-1) \rfloor$.

But in general, for any configuration, the number of distinct values is at most $1 + \lfloor \log_2 \frac{d_{\max}}{d_{\min}} \rfloor$.

But the number of distinct pairwise distances is at most $\binom{n}{2}$, so the number of distinct $\lfloor \log_2 d \rfloor$ values is at most the number of distinct pairwise distances, which is $\binom{n}{2} < 2n$ for $n \geq 3$.

But we can do better:

Let us consider the set $\{ \lfloor \log_2 d_{ij} \rfloor : 1 \leq i < j \leq n \}$.

For each $k$, the set of pairs with $2^k \leq d_{ij} < 2^{k+1}$ is the set of pairs whose distance falls in that interval.

But for $n$ points, the number of possible intervals $[2^k, 2^{k+1})$ that contain at least one pairwise distance is at most $n-1$ (since the minimal and maximal distances differ by at most a factor of $n-1$).

Thus, the number of distinct values is at most $1 + \lfloor \log_2 (n-1) \rfloor < 2n$ for all $n \geq 1$.

Therefore, Gauss writes down less than $2n$ distinct values.