Зал кинотеатра представляет собой прямоугольник 6×10 мест. На сеанс привели класс, в котором учатся отличники и хулиганы. Отличники всегда говорят правду, хулиганы всегда лгут.…

Ответ: 15.

Пояснение:

• Пусть H — множесто хулиганов, T — честных школьников. Ребята сидят в 6×10 раскладке, соседями считаются все клетки, соединённые по стороне или по диагонали (8-соседи).

• Правила задачи эквивалентны следующим условиям:

  • Хулиганы не сидят рядом друг с другом (иначе два хулигана были бы соседями и хотя бы один из них говорил бы правду, что противоречит тому, что они лгут).
  • Каждый честный школьник имеет хотя бы одного соседа-хулигана (его утверждение истинно). Значит H — независимое множество, которое одновременно является доминирующим (каждую не-H-позицию доли邻 соседствует с некоторым H).

• Верхняя граница: разбиваем доску на 2×2 блоки. В любом 2×2 блоке любые две клетки — соседи (они же соседствуют по стороне или по диагонали). Следовательно, в каждом блоке может быть не более одного хулигана. На доске 6×10 разложение на 2×2 даёт 3×5 = 15 блоков. Значит число хулиганов не может превышать 15.

• Пример достижимого расположения: поместим хулигана вTop-left клетки каждого 2×2 блока. Тогда хулиганы будут на клетках с координатами (1,1), (1,3), (1,5), (1,7), (1,9), (3,1), (3,3), (3,5), (3,7), (3,9), (5,1), (5,3), (5,5), (5,7), (5,9) — всего 15.

  • Никакие два хулигана не соседствуют друг с другом (они лежат по разным 2×2 блокам).
  • В каждом 2×2 блоке остальные три клетки соседствуют с тем самым хулиганом в этом блоке, поэтому каждый не-хулиган имеет соседа-хулигана.

Таким образом, 15 хулиганов возможно, и это максимальное возможное число.