MathDB
Problems
Contests
International Contests
KoMaL A Problems
KoMaL A Problems 2019/2020
A. 763
A. 763
Part of
KoMaL A Problems 2019/2020
Problems
(1)
Finding Weights With Errors
Source: KöMaL A. 763
3/20/2022
Let
k
≥
2
k\geq 2
k
≥
2
be an integer. We want to determine the weight of
n
n
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
k
k
of the answers can be wrong. Let
f
k
(
n
)
f_k(n)
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
)
f_k(n)
f
k
(
n
)
tries (the tries don't have to be decided in advance). Prove that there exist numbers
a
k
a_k
a
k
and
b
k
b_k
b
k
for which
∣
f
k
(
n
)
−
a
k
n
∣
≤
b
k
|f_k(n)-a_kn|\leq b_k
∣
f
k
(
n
)
−
a
k
n
∣
≤
b
k
holds.Proposed by Surányi László, Budapest and Bálint Virág, Toronto
combinatorics
komal