Ви маєте шість ключів від шести закритих скринь і не знаєте, який ключ від якої скрині. Яку найменшу кількість спроб треба зробити, щоб з'ясувати, який ключ від якої скрині? А якщо ключів і скринь буде 100?

Відповідь:

Якщо ключів і скринь буде 6, то найменшу кількість спроб можна зробити за два кроки:

1.Візьміть ключ від першої скрині і спробуйте його у всіх скриньках по черзі. Якщо ключ відкриває першу скриню, то вам вдалося знайти його. Якщо ні, то запам'ятайте номер скрині, яку ви спробували.

2.Візьміть наступний ключ і повторіть крок 1, спочатку спробувавши його в скрині, яку ви не пробували раніше.

Якщо ключів і скринь буде 100, то найменшу кількість спроб можна зробити за не більше ніж 199 кроків:

1.Візьміть перший ключ і спробуйте його у всіх скриньках з номерами, які є кратними на 1 (тобто 1, 2, 3, ..., 100). Якщо ключ відкриває якусь скриню, то вам вдалося знайти його. Якщо ні, то запам'ятайте номери усіх скринь, які ви пробували.

2.Візьміть наступний ключ і спробуйте його у всіх скриньках з номерами, які є кратними на 2 (тобто 2, 4, 6, ..., 100). Якщо ключ відкриває якусь скриню, то вам вдалося знайти його. Якщо ні, то запам'ятайте номери усіх скринь, які ви пробували.

3.Повторюйте крок 2 для всіх ключів від 3 до 100.

4.Залиште останній ключ до останньої спроби, коли лишається одна невідкрита скринька. Використовуйте його для відкриття цієї скриньки.

Таким чином, загальна кількість спроб у худшому випадку буде 199: 100 для першої частини (до останньої пари скриньок) і ще 99 для другої частини (для останньої скриньки).

Пояснення: