Зал кинотеатра представляет собой прямоугольник 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 хулиганов возможно, и это максимальное возможное число.