С наступающим 2025

Счастье для всех, даром, и пусть никто не уйдет обиженный!
Стругацкие

Дорогие! Пусть новый год будет для вас счастливым. Всем нам – ❤️ и 🕊

Традиционное, но ничуть не формальное, СПАСИБО за то, что вы с нами!

Мы знаем, что среди наших подписчиков есть люди, которые накануне праздников непременно захотят порешать задачки. Понимая нашу ответственность, публикуем.

Пара слов про саму задачу. Наверное, не будет большим спойлером сказать, что в задачах на поиск оптимума, как правило, есть две части:

1/ привести пример решения
2/ доказать, что оно оптимально

Первая часть обычно очень весёлая. Вторая же – наоборот. Поэтому часто её пропускают за «очевидностью». Несмотря на то, что сегодняшняя задачка достаточно известная, например, вот она на бразильской олимпиаде 2005 года, мы не нашли строгого доказательства оптимальности. Среди того, что получилось найти, одни переборы. Нам удалось эту лакуну закрыть весьма эстетично на языке теории графов.

#олимпиады

• Фонарик и 8 батареек
• Решение