Q9 Matemática  (IMO Shortlist 2016)

líder de uma equipe da IMO escolhe os inteiros positivos $n$ e $k$ com $n>k$ e os anuncia ao vice-líder e a um competidor. O líder então secretamente diz ao vice-líder uma string binária de $n$-dígitos, e o vice-líder anota todas as strings binárias de $n$-dígitos que diferem das do líder em exatamente $k$ posições. (Por exemplo, se $n=3$ e $k=1$, e se o líder escolher $101$, o vice-líder anota $001,111$ e $100$.) O competidor pode ver as strings escritas pelo vice-líder e adivinhar a seqüência do líder. Qual é o número mínimo de palpites (em termos de $n$ e $k$) necessários para garantir a resposta correta?