Question

По кругу стоят 4096 шкатулок. В каждой шкатулке либо лежит монетка, либо не лежит. На каждой шкатулке имеется надпись: «Если здесь лежит монетка, то в соседней шкатулке монетки нет». Известно, что все надписи не соответствуют действительности. В скольких шкатулках лежит монетка?

Answer 1

Если надписи не соответствуют, то 2048

Answer 2

Предположим, что в каждой шкатулке нет монетки. Тогда по условию в каждой шкатулке должна быть монетка, так что это предположение противоречит условию задачи. Следовательно, в как минимум одной шкатулке должна быть монетка.

Рассмотрим эту шкатулку с монеткой. Согласно надписи, в каждой из соседних шкатулок монетки нет. Это означает, что две соседние шкатулки, находящиеся по обе стороны от шкатулки с монеткой, не могут содержать монетки. Таким образом, мы можем исключить эти две шкатулки из рассмотрения.

Рассмотрим теперь две соседние шкатулки, находящиеся по обе стороны от этих исключенных шкатулок. Согласно надписям на этих шкатулках, в каждой из них не может быть монетки. Это означает, что две соседние шкатулки, находящиеся по обе стороны от этой пары исключенных шкатулок, не могут содержать монетки. Мы можем исключить эти две шкатулки из рассмотрения.

Продолжая этот процесс дальше, мы можем последовательно исключать пары соседних шкатулок, находящихся по обе стороны от уже исключенных шкатулок, и приходить к новым парам шкатулок, в которых не может быть монеток. В конце концов, мы рассмотрим все 4096 шкатулок и исключим из рассмотрения 2048 пар шкатулок. Оставшиеся 2048 шкатулок должны содержать монетки.

Таким образом, ответ на задачу: в 2048 шкатулках лежит монетка.