Физтех 2024/25 · Математика · 9 кл., №10 — решение · Отборочный этап

Условие

На клетки доски $12 \times 12$ положили камни попарно различного веса (в каждую клетку положили ровно один камень). Тройку клеток назовём *хорошей*, если они расположены в виде «уголка», а камень, лежащий в «вершине» уголка, тяжелее каждого из двух камней, лежащих в двух остальных клетках уголка. Какое наибольшее количество хороших троек клеток может быть на доске? Тройки могут пересекаться.

О задаче · 9 класс

Олимпиада: Физтех (МФТИ)
Этап: Отборочный этап, второй тур (2 попытка)
Предмет / класс: Математика · 9 класс
Сезон: 2024/25

Каждый уголок лежит в каком-то квадрате $2 \times 2$ Сколько уголков в одном таком квадрате и сколько из них могут быть хорошими одновременно? В модели переставляй камни на маленькой доске. Ниже можно сверить ответ.

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Исследуй задачу

Самостоятельное исследованиеКамни на доске

Пробуй свои варианты. Разбор останется закрытым.

Исследуй задачу

Камни на доске

Сколько хороших уголков удастся собрать на маленькой доске?

Если модель не открылась (выключен JavaScript или страница загрузилась не полностью), условие, подсказки и разбор доступны и без неё.

Подсказка для решения без модели

Если модель не открылась, попробуй так. Нарисуй квадрат 2 × 2 и впиши в клетки числа 1–4 в разном порядке. Сколько уголков получается хорошими? Затем заполни доску 3 × 3 так, чтобы хороших уголков было как можно больше.

Подсказка 1

Уголок — квадрат $2 \times 2$ без одной клетки, вершина — клетка, противоположная выброшенной. В каждом квадрате $2 \times 2$ ровно $4$ уголка. Могут ли быть хорошими уголки с вершинами в двух соседних клетках?

Подсказка 2

Если вершины $V$ и $W$ — соседние клетки квадрата, то для хороших уголков нужно, чтобы $V$ был тяжелее $W$ и $W$ тяжелее $V$ Значит, в квадрате не больше двух хороших уголков. Для примера раскрась доску в шахматном порядке.

Разобрать решение по шагам

Уголки и квадраты 2 × 2

Уголок — это три клетки квадрата $2 \times 2$ вершина уголка — клетка, соседняя с двумя другими (она противоположна выброшенной клетке). Каждый уголок лежит ровно в одном квадрате $2 \times 2$ а в каждом квадрате ровно $4$ уголка — по одному с вершиной в каждой его клетке. Уголок с вершиной $V$ хороший, когда камень в $V$ тяжелее камней в двух соседних с $V$ клетках этого квадрата.

В одном квадрате не больше двух хороших

Пусть $V$ и $W$ — соседние клетки квадрата. Если уголки с вершинами в $V$ и в $W$ оба хорошие, то камень в $V$ тяжелее камня в $W$ а камень в $W$ тяжелее камня в $V$ — так не бывает. Значит, хорошими могут быть только уголки с вершинами в двух противоположных клетках квадрата: не больше двух на квадрат.

Квадрат 2 × 2 и четыре его уголка. Вершины в соседних клетках не могут быть хорошими одновременно, поэтому хорошими бывают не больше двух уголков — с вершинами в противоположных клетках.

Оценка для всей доски

Квадратов $2 \times 2$ на доске $12 \times 12$ ровно $11 \cdot 11 = 121$ (левая верхняя клетка — в одной из первых $11$ строк и $11$ столбцов). Поэтому хороших троек не больше $2 \cdot 121 = 242$

Пример на 242

Раскрасим доску в шахматном порядке и положим на чёрные клетки $72$ самых тяжёлых камня, а на белые — $72$ самых лёгких. В каждом квадрате $2 \times 2$ две чёрные клетки, и у каждой из них обе соседние клетки квадрата белые. Значит, уголки с вершинами в чёрных клетках хорошие — по $2$ в каждом квадрате, всего $242$

Проверка

Тест модели перебирает все $24$ порядка весов в квадрате $2 \times 2$ — хороших уголков никогда не больше двух — и считает хорошие тройки на случайных досках: больше $2(n-1)^2$ не бывает, а шахматная расстановка даёт ровно $2(n-1)^2$ Другие версии: $2 \cdot 13^2 = 338$ $2 \cdot 15^2 = 450$ $2 \cdot 17^2 = 578$

Ответ

$242$

Ответ

$242$

Главная идея

Каждый уголок лежит в одном квадрате 2 × 2, где хороших уголков не больше двух; квадратов 11², а шахматная расстановка (чёрные тяжелее белых) даёт по два хороших уголка в каждом квадрате.

Подсчёт фигурок на доске — разбить их по маленьким квадратам, оценить в одном квадрате и предъявить пример с раскраской.

Где легко ошибиться

Считать, что хорошими могут быть три уголка квадрата; посчитать квадраты 2 × 2 как 12² или 6²; привести оценку без примера.

Источник и авторство

Олимпиада «Физтех» · математика · 9 класс · 2024/25 · отборочный этап, второй тур (2 попытка). Задача 10, версия с ID 3902 — первая в официальном файле; другие версии этого номера (ID 3903, 3904, 3905) можно выбрать в модели.

Официальные условия (PDF организатора, стр. 9) ↗ · Ответы и решения организатора ↗ · Архив заданий олимпиады ↗

Условие — из официального файла организатора. Подсказки, решение и модель — Popov Academy. Авторское решение записано до знакомства с решениями организатора; затем ответ совпадает с ответом организатора («Решения М9 2 попытка», стр. 10 ↗: ID 3902: 242; ID 3903: 338; ID 3904: 450; ID 3905: 578.). Сверены все четыре официальные версии этого номера.

Продолжить тему: Подсчёт вариантов →

Тема, знания и приёмы

Подсчёт вариантов · Нужна школьная база

Оценка и пример
Шахматная раскраска

Приёмы решения: Оценка и достижимость · Раскраска

Задать вопрос по задаче →