Решение. Фонарик и 8 батареек (#145)
Проведём графовую интерпретацию решения. Рассмотрим граф, чьи вершины обозначают батарейки, а рёбра – выполнялась ли проверка пары соответствующих батареек в фонарике.
Поясним, первый граф из примера. Пусть после 6 проверок фонарик не зажёгся. Тогда в каждом треугольнике не более одной заряженной батарейки. Так как всего заряженных батареек ровно 4, значит две нетронутые батарейки обязаны быть заряжены. Таким образом, мы гарантированно нашли требуемое за не более чем 6 проверок.
Хотелось бы сформулировать критерий в наиболее общих терминах. Пусть всего n батареек, x из которых заряжены.
Полный (под-)граф с n вершинами будем называть Kₙ. Введём раскраску на рёбрах Kₙ:
- чёрные рёбра – была проведена проверка пары, которая оказалась неудачной
- белые рёбра – не было проверки пары
Замечание. Пусть было проверено m пар батареек, и все они не зажгли фонарик (другими словами, в графе есть ровно m чёрных рёбер), тогда в Kₙ есть белый Kₓ-подграф (то есть полный подграф с x вершинами, все рёбра которого белые).
Действительно, в исходном графе Kₙ найдутся x вершин, соответствующие заряженным батарейкам, и каждая пара по предположению должна соединяться белым ребром.
Критерий. Пусть в Kₙ есть ровно m чёрных рёбер. Задача решается за m проверок тогда и только тогда, когда пересечение всех белых Kₓ-подграфов содержит белое ребро.
Задача решается за m проверок тогда и только тогда, когда после проведения m чёрных рёбер однозначно определяются 2 вершины, соответствующие заряженным батарейкам. А это происходит тогда и только тогда, когда все белые Kₓ подграфы пересекаются минимум по двум вершинам. Что и требовалось доказать.
Вооружившись критерием и теоремой Турана (см. ниже), определим, возможно ли в исходной задаче обойтись 5 проверками.
В нашем случае n=8 (всего батареек), x=4 (хороших батареек), m=5 (проверок сделано). Таким образом, K₈ имеет m=5 чёрных и 28 - 5 = 23 белых рёбер.
Рассмотрим теперь только белый подграф. По формуле из теоремы Турана ex(n,x) = 21. Значит, любой граф из 22 рёбер на 8 вершинах содержит К₄. Но любой граф с 22 рёбрами обязан иметь минимум 8 вершин. Итак, выберем 22 ребра (а у нас их 23, значит есть ещё одно лишнее) и найдём K₄. Теперь построим ещё 6 других К₄, заменив ребро из этого К₄ на лишнее. Получим всего семь К₄ (по формуле Турана они будут), которые не пересекаются по ребру по построению. Следовательно, по критерию за 5 проверок найти работающие батарейки не получится.
Теорема Турана. Среди всех графов на n = q(x - 1) + r (0 ⩽ r < x - 1) вершинах, не содержащих подграфа Kₓ, максимально возможное количество ребёр равно
