Олимпиада имени Леонарда Эйлера 2018-2019 учебный год, I тур регионального этапа

Имеется кубик, каждая грань которого разбита на 4 одинаковые квадратные клетки. Олег хочет отметить невидимыми чернилами 8 клеток так, чтобы никакие две отмеченные клетки не имели общей стороны. У Рустема есть детекторы. Если детектор помещен в клетку, чернила на ней делаются видимыми. Какое наименьшее число детекторов Рустем может поместить в клетки так, чтобы, какие бы клетки после этого Олег ни отметил, можно было определить все отмеченные клетки? ( Р. Женодаров, О. Дмитриев )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Ответ. 16.
Решение. Пример. Разобьем все 24 клетки на восемь троек, где в каждую тройку входят три клетки, примыкающие к одной вершине кубика. У любых двух клеток из одной тройки есть общая сторона. Поскольку отмеченных клеток столько же, сколько троек, в каждой тройке должна быть ровно одна отмеченная клетка. Разместим 16 детекторов так, чтобы в каждой тройке было два детектора. Если в данной тройке один из детекторов сработал, мы нашли отмеченную в этой тройке клетку, если не сработали оба детектора — отмечена клетка, где детектора нет. Оценка. Пусть мы разместили меньше 16 детекторов. Тогда найдется тройка, где есть хотя бы две клетки без детекторов (назовем их «свободными») — отметим ее клетки на изображенной справа развертке куба тёмными фоном. На этой же развёртке отметим 7 клеток буквой $A$ так, как показано на рисунке. Теперь заметим, что если отметить невидимыми чернилами семь клеток $A$ и одну из свободных клеток, то детекторы не позволят нам узнать, какая именно из свободных клеток отмечена. Поэтому меньше, чем 16 детекторами, обойтись не удастся.