Задание №180803: Командная олимпиада 2025
Пусть m и n — натуральные числа. Некоторые клетки доски размером m × n окрашены в красный цвет. Последовательность a ,a ,...,a из 1 2 2r 2r ⩾ 4 попарно различных красных клеток называется циклом слона, если для каждого k ∈ {1,...,2r} клетки a и a лежат на диагонали, но клетки a и k k+1 k a не лежат на диагонали (полагаем a = a и a = a ). k+2 2r+1 1 2r+2 2 Определите максимально возможное количество красных клеток на доске размером m × n без цикла слона. (MEMO-2021)
Что проверяет это задание
Задание относится к теме «Командная олимпиада 2025» и рассчитано на уровень 8 класса. Для решения понадобятся:
- анализ условия
- выбор формулы
- проверка вычислений
Источник: Турнир математических боёв и командная олимпиада МЦНМО — официальный архив · 2025
Качество материала
Показываем, из чего состоит страница и можно ли проверить материал по первоисточнику.
Последняя проверка решения:
Происхождение задания
- Банк заданий
- Турнир математических боёв и командная олимпиада МЦНМО — официальный архив
- Организатор
- МЦНМО
- Год материала
- 2025
- Материалы
- 1 файл
Связанные понятия
План самостоятельного решения
- Перепишите известные данные и отдельно сформулируйте, что требуется найти или доказать.
- Свяжите условие с темой «Командная олимпиада 2025» и выберите подходящее правило, формулу или способ рассуждения.
- Запишите промежуточные шаги: это помогает заметить потерянный знак, случай или логический переход.
- Сверьте результат со всеми ограничениями условия и только затем откройте подробный разбор.
Ориентировочное время: 15 минут.
Закрепить тему
После разбора попробуйте решить ещё десять заданий по предмету «Математика». Вариант формируется заново, а ответы можно сразу проверить.
Решение по шагам
Ответ: Для полоски 1 × k или k × 1 – k, для доски m × n – 2m + 2n − 4.
Решение. В случае полоски можно закрасить все клетки. Пусть каждая сторона
доски не менее 2. В качестве примера можно закрасить два первых столбца, а
также первую и последнюю строки. При попытке построить цикл мы уйдем
вправо.
Обозначим ячейку в i-й строке и j-м столбце как (i,j). k-я положительная диа-
гональ – это множество ячеек (i,j), такое, что i + j − 1 = k. Аналогично, k-я
отрицательная диагональ – это множество ячеек (i,j), такое, что n + i − j =
k. Рассмотрим двудольный граф G с долями A = {a ,a ,...,a } и B =
1 2 m+n−1
{b ,b ,...,b }, где вершины a и b соединены ребром тогда и только тогда,
1 2 m+n−1 i j
когда клетка в пересечении i-й положительной диагонали и j-й отрицательной
диагонали красная. Заметим, что цикл слона соответствует циклу в G, и наобо-
рот. Граф G имеет как минимум две компоненты: если мы раскрасим клетки
таблицы попеременно в черный и белый цвета, как в шахматах, то рёбра графа
G, соответствующие черным клеткам, лежат в другой компоненте, чем рёбра
графа G, соответствующие белым клеткам – невозможно переместить слона
между черной и белой клетками. Кроме того, граф G имеет 2n+2m−2 верши-
ны. Если граф G ацикличен, то G – это лес, состоящий как минимум из двух
деревьев. Следовательно, граф G содержит не более 2n+2m−2−2 = 2n+2m−4
рёбер, а значит верна оценка и для красных клеток.
Используемые формулы
гональ – это множество ячеек (i,j), такое, что i + j − 1 = k.отрицательная диагональ – это множество ячеек (i,j), такое, что n + i − j =Рассмотрим двудольный граф G с долями A = {a ,a ,...,a } и B =Следовательно, граф G содержит не более 2n+2m−2−2 = 2n+2m−4
Самопроверка после решения
- Я использовал все данные из условия и не добавил неподтверждённых предположений.
- Каждый переход в рассуждении объяснён правилом, формулой или ранее доказанным фактом.
- Ответ соответствует вопросу, а обозначения и единицы измерения записаны однозначно.
- Я сравнил свой ход решения с разбором и понял причину каждого отличия.
Типичные ошибки
- Не проверить область допустимых значений.
- Потерять знак при переносе или раскрытии скобок.
- Не выполнить обратную подстановку.