ACGNmath wrote: $99$ identical balls lie on a table. $50$ balls are made of copper, and $49$ balls are made of zinc. The assistant numbered the balls. Once spectrometer test is applied to $2$ balls and allows to determine whether they are made of the same metal or not. However, the results of the test can be obtained only the next day. What minimum number of tests is required to determine the material of each ball if all the tests should be performed today? Proposed by N. Vlasova, S. Berlov First note that $98$ checks are enough; pick a ball and toss it in with each of the other balls, one by one. We will obtain a set of balls which are the same metal as the chosen one and another set; which is not. Clearly, the set with $50$ balls is made of copper. Now we show that $97$ checks are not sufficient to determine the metals involved (if any lesser number of checks work just make arbitrary ones to reach $97$). Note that checking the pairs $(i_1, i_2), (i_2, i_3), \dots, (i_k, i_1)$ is pointless as we can deduce the last one given previous results. Think of the metal balls as vertices of a graph and checks as edges between them. Let blue be copper and green be zinc. Claim. If a tree is coloured and edges are assigned "true" or "false" values of whether the endpoints match; then the colouring is always consistent. (Proof) The only way inconsistency can happen is if one path between $u$ and $v$ gives different information than another path. However trees are acyclic so two paths between $u$ and $v$ do not exist. $\blacksquare$ Now since we have $97$ edges; the graph is not connected. Let $C_1, \dots, C_k$ be the connected components. Then each component is acyclic by assumption; so all of them are trees. Then the graph has $97=\sum^k_{i=1} (|C_i|-1)=99-k$ edges so $k=2$. Now we have two trees $T_1, T_2$ with $|T_1|+|T_2|=99$. WLOG let $|T_2|$ be even. Then label half of the vertices of $T_2$ blue while the others green. Label half (floor approx) of the vertices of $T_1$ in one colour while the other half in a different colour. Assign Boolean values to the edges of the graph accordingly. Notice that we can have either $\tfrac{1}{2}(|T_1|+1)+\tfrac{1}{2}|T_2|=50$ blue vertices or $\tfrac{1}{2}(|T_1|-1)+\tfrac{1}{2}|T_2|=49$ blue vertices. Thus given only the Boolean values of the graph; we cannot deduce which set of balls is blue or green. So we are done!

Hi. Are there official solutions of Tuymaada 2018?