, 2019

Let $k\ge 2$ be an integer. We want to determine the weight of $n$ balls. One try consists of choosing two balls, and we are given the sum of the weights of the two chosen balls. We know that at most $k$ of the answers can be wrong. Let $f_k(n)$ denote the smallest number for which it is true that we can always find the weights of the balls with $f_k(n)$ tries (the tries don't have to be decided in advance). Prove that there exist numbers $a_k$ and $b_k$ for which $\big|f_k(n)-a_kn\big|\le b_k$ holds.