Условие:
Андрей хочет покрасить клетки бесконечной доски в несколько цветов так, чтобы в любом клетчатом прямоугольнике 3*5 все цвета были попарно различны (прямоугольники можно поворачивать). Какое наименьшее количество цветов ему понадобится?
Решение:
- Заметим, что любой прямоугольник размера 3×5 (а по условию можно брать его поворот, то есть 5×3) состоит ровно из 15 клеток. Чтобы цвета всех клеток в этом прямоугольнике были попарно различны, необходимо, чтобы в нём встречались 15 различных цветов. Поэтому очевидно, что использовать меньше 15 цветов нельзя – это дает нижнюю границу.
- Теперь нужно показать, что существует раскраска бесконечной доски 15 цветами, удовлетворяющая условию, то есть такая, что каждая группа клеток, образующая прямоугольник 3×5 (или 5×3), содержит все 15 разли...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи