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$

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.

@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!

Nothing much to add but I do lament not having the original flavour text in favour of the more bland one

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?

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?

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?

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.

redacted

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.

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.

.

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.

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.

lelouchvigeo wrote:

Why at most 2 values? You were discussing about k and k-1, what about the smaller ones?