Problem

Source: IOM 2021 #5

Tags: combinatorics



There is a safe that can be opened by entering a secret code consisting of n digits, each of them is 0 or 1. Initially, n zeros were entered, and the safe is closed (so, all zeros is not the secret code). In one attempt, you can enter an arbitrary sequence of n digits, each of them is 0 or 1. If the entered sequence matches the secret code, the safe will open. If the entered sequence matches the secret code in more positions than the previously entered sequence, you will hear a click. In any other cases the safe will remain locked and there will be no click. Find the smallest number of attempts that is sufficient to open the safe in all cases.