Bumpbump

Bumping again

Main Idea

$\textcolor{red}{Lemma:}$ Amongst any $5000$ balls, Petya can choose two balls such that Petya knows the sum of them. $\textcolor{red}{Proof:}$ Petya asks all combinations among $5000$ balls. Device answers Petya $\binom{5000}{10}$ times. Each answers belongs to one of $\binom{5000}{2}$ pair sum. So there is a pair($a$ and $b$), if Petya asks all combination of $10$ balls including that pair, Petya will hear the same answer($X$) at least $c=\frac{\binom{5000}{10}}{\binom{5000}{2}}$ times. Petya will prove that sum of that pair is $X$. Assume otherwise, there is at most $2500$ different pairs whose sum is $X$. and each such pair can appear at most $\binom{4997}{7}$ if that pair includes one of $a$ or $b$, and $\binom{4996}{6}$ otherwise. Since $c> 2\cdot \binom{4997}{7}+2498\cdot \binom{4996}{6}$ we get a contradiction. $\textcolor{red}{Petya}$ $\textcolor{red}{creates}$ $\textcolor{red}{a}$ $\textcolor{red}{non-bipartite}$ $\textcolor{red}{graph}$ Petya draws a graph. Vertices are balls and Petya draws an edge between vertices if he knows sum of them. Petya starts to draw edges(by choosing $5000$ vertices with no edges between them) until he can't anymore. If graph is bipartite, Petya can find $5000$ vertices with no edge between them. $\textcolor{red}{Petya}$ $\textcolor{red}{chooses}$ $\textcolor{red}{an}$ $\textcolor{red}{odd}$ $\textcolor{red}{cycle}$ $\textcolor{red}{and}$ $\textcolor{red}{plays}$ $\textcolor{red}{the}$ $\textcolor{red}{detective}$ Petya can find an odd cycle in the non-bipartite graph. After finding an odd cycle, Petya sums all the edges in the cycle and deduces the sum of all balls in the cycle. Petya can also deduce the sum of all the balls in the cycle except one of the ball. Putting the pieces together, Petya can deduce the weight of all the numbers in the odd cycle.

Infinityfun wrote: So there is a pair($a$ and $b$), if Petya asks all combination of $10$ balls including that pair, Petya will hear the same answer($X$) at least $c=\frac{\binom{5000}{10}}{\binom{5000}{2}}$ times. Unless I misunderstand what's going on isn't $c=\tfrac{\binom{4998}{8}}{\binom{5000}{2}}$ since there are only $\binom{4998}{8}$ such choices? This would make the inequality false. And if we're considering answers across all combinations then I don't see an obvious way to figure out what the pair in question is.

An excellent Russian problem. You couldn't believe that it is possible to guess upon reading it. The solution in #5 is the official one. The balls should be sufficiently many for the idea to work. You take some 5000 balls, take all 10-elements subsets among them and ask all the questions. We get the same answer for at least $\displaystyle N:=\frac{\binom{5000}{10}}{\binom{5000}{2}}$ sets. Moreover, there is a family of at least $N$ ten-elements subsets with two common elements $\{a,b\}$ and for all of them we get the same answer $S$. It follows (a bit of straightforward calculation here) the only possibility is $a+b=S$. The rest is easier.