Let $n$ be a fixed positive integer. Ben is playing a computer game. The computer picks a tree $T$ such that no vertex of $T$ has degree $2$ and such that $T$ has exactly $n$ leaves, labeled $v_1,\ldots, v_n$. The computer then puts an integer weight on each edge of $T$, and shows Ben neither the tree $T$ nor the weights. Ben can ask queries by specifying two integers $1\leq i < j \leq n$, and the computer will return the sum of the weights on the path from $v_i$ to $v_j$. At any point, Ben can guess whether the tree's weights are all zero. He wins the game if he is correct, and loses if he is incorrect. (a) Show that if Ben asks all $\binom n2$ possible queries, then he can guarantee victory. (b) Does Ben have a strategy to guarantee victory in less than $\binom n2$ queries? Brandon Wang
Problem
Source: ELMO Shortlist 2024/C2
Tags: Elmo, combinatorics
MathGuy1729
22.06.2024 20:40
We assume $n\geq 2$ (there's no tree with less then $2$ leaves and an edge).
(a): For $n=2$ the problem is trivial, so assume $n\geq 3$. Therefore, there exists a vertex that's not a leaf, and no $2$ leaves are connected. It's clear that if any of the queries gives a nonzero answer, there exists a nonzero weight, so we only have to prove that if all answers to the queries are $0$, all edge weights are $0$.
Lemma: For any vertex $V$ that's not a leaf, the sum of weights on the path from any leaf to $V$ is $0$.
Proof: Note that $V$ has degree at least $3$, so if we root the tree at $V$, it has at least $3$ subtrees. Let leaves $A$, $B$ and $C$ be each in a different subtree (each subtree has a leaf), and let $a$, $b$ and $c$ be the sums of weights on the paths from $A$ to $V$, $B$ to $V$, and $C$ to $V$ respectively. Note that because the answers to the queries on pairs $(A, B)$, $(A, C)$ and $(B, C)$ are all $0$, we have $a+b=a+c=b+c=0$. This implies $a=b=c=0$. However, the vertex $A$ can be any of the leaves, so sum of weights on the path from any leaf to $V$ is $0$.
Now, for each edge connecting a leaf and non-leaf, we may simply apply the lemma with the non-leaf as $V$, so it has weight $0$. And for each edge connecting $2$ non-leaf vertices $A$, $B$, we may root the tree at $A$, find a leaf in the subtree of $A$ containing $B$, call it $L$, and apply the lemma for $A$ as the root and for $B$ as the root, with $L$ being the leaf in both cases, giving us that the weight of edge $AB$ is $0$. So every edge has weight $0$, which is what we wanted to prove.
(b): No. Case $n=2$ is trivial, so assume $n\geq 3$. Construct the graph as follows: Draw edges from vertex $A$ to vertex $C$ and form vertex $B$ to $C$, both of which have weight $1$. Draw an edge from $C$ to vertex $D$ with weight $-1$. Now, draw all the remaining edges so that all of them have weight $0$ and neither of the edges has an endpoint in any of the vertices $A$, $B$, $C$. This is clearly possible and can give us any number of leaves $\geq 3$. At the same time, the only query with a nonzero answer would be the query asked on $A$ and $B$, because all the other queries ask about paths composed fully of edges with weight $0$, the path from $A$ to $D$ (which has sum of weights $0$) and the path from $B$ to $D$ (ditto), and thus the sum of weights on any of these paths is $0$. Now, assume that at most $\binom n2 - 1$ queries have been asked, and let $A$, $B$ be precisely the leaves so that the query asking about the path between them hasn't been asked. Then, all the queries asked give an answer of $0$ in a tree for which there exists a nonzero weight. However, the same can obviously happen if all the weights are $0$, and Ben can't distinguish between these two cases and therefore cannot guarantee victory.