Условие:
В каждой клетке доски размером 5×5 стоит крестик или нолик, причём никакие три крестика не стоят подряд ни по горизонтали, ни по вертикали, ни по одной из диагоналей. Какое наибольшее количество крестиков может быть на доске?
Решение:
- Прежде всего заметим, что если рассматривать только строку из 5 клеток, то максимальное число крестиков, которое можно в ней расставить при условии, что никакие три подряд не могут быть крестиками, равно четырём. Например, последовательность X X О X X удовлетворяет условию – в ней есть две группы по два подряд, но нет трёх подряд. Таким образом, если бы каждая строка была независима, максимум дал бы 5·4 = 20 крестиков.
- Однако клетки в строках пересекаются с клетками в столбцах и диагоналях, поэтому расстановка, оптимальная по горизонтали, может давать «слишком длинные» по...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи