Q17 Matemática (KoMaL A Problems 2020)

17 | KoMaL A Problems | 2020 | Matemática

Seja $k \geq 2$ um inteiro. Queremos determinar o peso de $n$ bolas. Uma tentativa consiste em escolher duas bolas, e nos é dada a soma dos pesos das duas bolas escolhidas. Sabemos que no máximo $k$ das respostas podem estar erradas. Seja $f_{k} (n)$ o menor número para o qual é verdade que sempre podemos encontrar os pesos das bolas com $f_{k} (n)$ tentativas (as tentativas não precisam ser decididas antecipadamente). Prove que existem números $a_{k}$ e $b_{k}$ para os quais $∣ f_{k} (n) - a_{k} n ∣ \leq b_{k}$ vale. Proposto por Surányi László, Budapeste e Bálint Virág, Toronto