Problem

Source: INMO 2023 P5

Tags: combinatorics, inequalities, INMO, INMO 2023, graph theory



Euler marks $n$ different points in the Euclidean plane. For each pair of marked points, Gauss writes down the number $\lfloor \log_2 d \rfloor$ where $d$ is the distance between the two points. Prove that Gauss writes down less than $2n$ distinct values. Note: For any $d>0$, $\lfloor \log_2 d\rfloor$ is the unique integer $k$ such that $2^k\le d<2^{k+1}$. Proposed by Pranjal Srivastava