MathDB

Let

k\geq 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

|f_k(n)-a_kn|\leq b_k

holds.
Proposed by Surányi László, Budapest and Bálint Virág, Toronto

Problem Statement