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
Problem
Source: INMO 2023 P5
Tags: combinatorics, inequalities, INMO, INMO 2023, graph theory
15.01.2023 16:04
Solution. (Pranjal Srivastava) We change Euler and Gauss to Barista and coffee cups to the original phrasing of the proposal. We first prove that the barista writes down at most $n$ even numbers. For each even number $2k$ that the barista writes down, choose a single pair of cups whose distance lies between $2^{2k}$ and $2^{2k+1}$. Connect these points with a red edge. We claim there cannot be a cycle: indeed, if the edges corresponding to the distinct even integers $2k_1,\dots, 2k_m,2k_{m+1}$ form a cycle in that order, then the sum of distances for the first $m$ edges is at most $$2^{2k_1+1}+\cdots+2^{2k_m+1}\le 2^{2k_m+1}(1+2^{-2}+2^{-4}+\cdots)\le \frac{2^{2k_m+1}}{1-\frac1{2^2}}<2^{2k_m+2}\le 2^{2k_{m+1}},$$ i.e. less than the distance corresponding to the last edge: a contradiction to triangle inequality. So there are at most $n-1$ red edges. This implies that the barista only writes at most $n-1$ even numbers, and similarly at most $n-1$ odd numbers. Thus, the barista writes down at most $2n-2$ numbers in total.$\square$
15.01.2023 16:08
The above solution is super nice , congratulations Pranjal! Not relevant to solving the problem, but it is possible to achieve $2n-3$ distinct values by inductively picking points. First pick $2$ points arbitrarily, then pick large $k$ and tiny $\epsilon$ and choose a new point $P$ such that the closest distance to it from previous ones is $2^k - \epsilon$ and some other goes above $2^k$, giving two new values each time.
15.01.2023 18:49
@above, Thank you! Also, nice observation! If I'd realized that the bounds were actually tight, I would have simply asked for the largest number of distinct values. For some reason, I only was looking for an O(n) thing (In fact, the original wording didn't even have 2 as the constant but 100 instead). (I feel like it should be possible to tweak the proof so it gives $2n-3$ instead of $2n-2$.) EDIT: In fact, Anant's post below points out that this is indeed true!
15.01.2023 18:56
Nothing much to add but I do lament not having the original flavour text in favour of the more bland one
15.01.2023 19:03
p_square wrote: @above, Thank you! Also, nice observation! If I'd realized that the bounds were actually tight, I would have simply asked for the largest number of distinct values. For some reason, I only was looking for an O(n) thing (In fact, the original wording didn't even have 2 as the constant but 100 instead). (I feel like it should be possible to tweak the proof so it gives $2n-3$ instead of $2n-2$.) Hi Pranjal! Can you share the motivation behind coming up with this elegant problem?
15.01.2023 20:24
honestly, t'was inspired more from the (now missing) flavor text, since I like both coffee and rabbits. If Anant is fine, I'll go ahead and post the final version flavor text he came up with?
15.01.2023 20:30
p_square wrote: honestly, t'was inspired more from the (now missing) flavor text, since I like both coffee and rabbits. If Anant is fine, I'll go ahead and post the final version flavor text he came up with? need you ask, mate?
15.01.2023 21:19
Tejaswi points out the following. It was too late to consider the one-dimensional variant though. NVT wrote: Let $n$ be a natural number with $n \ge 2$ and let $S$ be a set of $n$ distinct real numbers. For elements $s, t$ in $S$ we define $d(s, t)$ to be the integer such that $2^{d(s,t)} \le |s-t| <2^{d(s,t)+1}$. Show that the set $D(S) = \{d(s, t)| s, t \in S\}$ has at most $2n-3$ elements. We prove by induction on $n$; the base case n = 2 is obvious. Now suppose that $n>2$ and that the result is true for all proper subsets S with at least two elements. We assume the contrary to the statement of the problem. For $s$ in $S$, define $C(s)$ to be the elements in $D(S)$ but not in $D(S \setminus \{s\})$. By the induction hypothesis, $D(S \setminus \{s\})$ has at most $2n-5$ elements, so $C(s)$ should have at least three elements for any $s$ in $S$. Let $s_1<s_2<\dots<s_n$ be the elements of $S$. For an integer $i$ with$1\le i\le n$,we say that $s_i$ is right-critical if there exists integers $j, k$ with $i< j < k \le n$ with $D(s_i, s_j)$ and $D(s_i, s_k)$ in $C(s_i)$. Simiarly, we say that $s_i$ is left-critical if there exists integers $j, k$ with $i>j>k\ge 1$ with $D(s_i, s_j)$ and $D(s_i, s_k)$ in $C(s_i)$. Note that each element of $S$ is either right-critical or left-critical by pigeonhole principle. Also note that $s_1$ is right-critical and $s_n$ is left-critical. Therefore, there exists an integer $i$ with $1 \le i < n$ such that $s_i$ is right-critical and $s_{i+1}$ is left-critical. Therefore, there exists integers $j, k$ with $1 \le j < i < i + 1 < k \le n$ such that $D(s_j, s_{i+1})$ is in $C(s_{i+1})$, $D(s_i, s_k)$ is in $C(s_i)$, and $D(s_j, s_{i+1}) \ne D(s_i, s_{i+1}) \ne D(s_i, s_k)$. Let $D(s_i, s_{i+1}) = a, D(s_j,s_{i+1}) = b,$ and $D(s_i, s_k) = c$. Note that $a<b$ and $a<c$. Without loss of generality we assume $b<c$. Note that $D(s_j, s_k) \ge c+1$ (for otherwise $c$ is not in $C(s_{i+1})$). Similarly, $D(s_j, s_i) \le b-1 \le c-2$ and $D(s_{i+1}, s_k) \le c-1$. Also, note that $D(s_i, s_{i+1})=a \le c-2$. This implies that $s_i-s_j < 2c-1, s_{i+1}-s_i < 2c-1$ and $s_k - s_{i+1} < 2c$. Summing these up we get $s_k - s_j < 2c+1$, a contradiction. This completes the induction. The argument pretty much comes from the case $n=4$. The key in the argument is the ordering and hence it does not seem to extend naturally to the two-dimensional version. The bound $2n-3$ is the best one can do. For example, if we take $s_1 =0, s_2 =1$ and $s_i = 2^{2i-2} + 1/2$, then $D(S) = \{0, 1, 2, . . . , 2n-4\}$ has exactly $2n-3$ elements. Even in the two-dimensional case, the bound $2n-3$ holds true. The original proof by the proposer can easily be extended to show the bound. That is if $r$ is the smallest element in $D(S)$, and without loss of generality if we assume $r$ is odd, then by taking one edge for every even element of $D(S)$ and also an edge for $r$, we can conclude that there could be at most $n-2$ even numbers (and $n-1$ odd numbers) in $D(S)$. Any typos are mine, oops. It's late now so I'll leave it just like this. Apologies, for the double-post.
15.01.2023 21:54
redacted
15.01.2023 22:21
What do you mean the bound is weak? A constant of $2$ doesn't make the bound weak. And definitely, the bound $2n-2$ compared to the construction $2n-3$ is not weak at all.
16.01.2023 21:22
Okie Anant's flavor text: An old angora rabbit places $n$ hot cocoa cups, represented by points, on the Euclidean plane. For every pair of cups, a barista writes down $\lfloor \log_2 d \rfloor$ where $d$ is the distance between the cups. Prove that the barista lists down at most $2n$ distinct numbers.
10.02.2023 16:36
p_square wrote: @above, Thank you! Also, nice observation! If I'd realized that the bounds were actually tight, I would have simply asked for the largest number of distinct values. For some reason, I only was looking for an O(n) thing (In fact, the original wording didn't even have 2 as the constant but 100 instead). (I feel like it should be possible to tweak the proof so it gives $2n-3$ instead of $2n-2$.) EDIT: In fact, Anant's post below points out that this is indeed true! To directly modify your approach: Use induction. If $2n-2$ labels are possible, then both the set of odd and even edges contain spanning trees consisting of different labels. Assume WLOG the longest edge $e$ has even label. Note that $$2^k> \sum_{i=1}^{2n-3} 2^{k-i}$$, hence the path between any two vertices on different sides of $e$ in the even spanning tree must go through the the odd edge $o$ with 1 lower label in the odd spanning tree. Deleting $e$ and $o$ then gives a partition of the set of vertices into two, each subset also containing odd and even spanning trees, contradiction.
12.01.2024 14:09
19.09.2024 18:30
If any one wants to check, please do; this is one of the first Graph Theory Problems I have done so chances of mistake is high (so sad I did not learn Graph Theory two years ago ) Assume the contrary that for some points, Gauss write down atleast $2n$ distinct values. Consider a graph $G$ with vertices as the $n$ points and two vertices are incident only if $ \left \lfloor \log_2d \right \rfloor$ where $d$ is the distance between them is one of the $2n$ values and make sure each number only corresponds to one edge. Now take a spanning subgraph of $G$ with atleast $n$ edges such that the difference between the numbers corresponding to any two edges is atleast $2$. Hence we get some cycle, and assume the largest number in one of those edges is $k$. So by extended triangle inequality we have that \[2^k<2^{k-1}-1+2^{k-3}-1+\dots \leq 2^k\]which is a contradiction.
30.01.2025 04:16
lelouchvigeo wrote:
Why at most 2 values? You were discussing about k and k-1, what about the smaller ones?