Q5 Matemática  (International Olympiad of Metropolises 2021)

Existe um cofre que pode ser aberto digitando um código secreto composto por $n$ dígitos, cada um deles é $0$ ou $1$. Inicialmente, foram inseridos $n$ zeros e o cofre é fechado (portanto, todos os zeros não são o código secreto). Em uma tentativa, você pode inserir uma sequência arbitrária de $n$ dígitos, cada um deles é $0$ ou $1$. Se a sequência inserida corresponder ao código secreto, o cofre será aberto. Se a sequência inserida corresponder ao código secreto em mais posições do que a sequência inserida anteriormente, você ouvirá um clique. Em quaisquer outros casos, o cofre permanecerá trancado e não haverá clique. Encontre o menor número de tentativas que seja suficiente para abrir o cofre em todos os casos.