Есть 5 замков и 5 ключей к ним, но неизвестно, какой ключ к какому замку подходит. Сколько проб нужно сделать, чтобы подобрать ключ к каждому замку?

В худшем случае достаточно 10 проб (и меньше гарантированно нельзя).

Как сделать за 10 проб (стратегия)

Действуем по одному замку, каждый раз “отсекая” ключи.

1. Берём первый замок и пробуем в нём ключи по очереди.

   • Если какой-то ключ подошёл — фиксируем пару и убираем этот ключ и этот замок.

   • Если 4 ключа подряд не подошли, то 5-й ключ обязан подойти (его уже можно не пробовать: других вариантов не осталось).

   Значит, на первый замок нужно максимум 4 пробы.

2. Остаётся 4 замка и 4 ключа. Для второго замка — аналогично:

   • максимум 3 пробы (если 3 не подошли, 4-й подходит по исключению).

3. Для третьего замка — максимум 2 пробы.

4. Для четвёртого замка — максимум 1 проба.

5. Пятая пара определяется автоматически, проб не нужно.

Итого в худшем случае:
4 + 3 + 2 + 1 = 10 проб.

Почему меньше нельзя

Чтобы гарантированно определить ключ к первому выбранному замку, нужно исключить все неподходящие варианты.
Если сделать не больше 3 проб, то в худшем случае они все окажутся неудачными — и останется 2 ключа, которые ещё могут подойти к этому замку. То есть точную пару вы всё ещё не знаете.
Значит, для первого замка нужно как минимум 4 пробы в худшем случае. Аналогично дальше: после удаления найденной пары остаётся 4 замка/ключа, и для следующего замка нужно как минимум 3, затем 2, затем 1.

Следовательно, минимально возможная гарантия — это именно
4 + 3 + 2 + 1 = 10 проб.