Popov AcademyУсловие
Фигура «скрипач» бьёт клетку слева по стороне (локтем) и справа вверху по диагонали (смычком), если он правша, и, наоборот, правую клетку по стороне и левую верхнюю по диагонали, если левша (все скрипачи сидят лицом к нам). Посадите как можно больше «скрипачей» в «оркестр» клеток, чтобы они не били друг друга. (Вы можете использовать любое количество как правшей, так и левшей.)
О задаче · 6 класс
Посади сначала простой оркестр — например, заполни столбцы через один. Сколько получилось? Можно ли больше? В модели «Рассади оркестр» нажимай на клетки, чтобы посадить правшу или левшу, — она покажет, кого бьёт каждый скрипач, и запомнит твой лучший результат.
Записать идеюЕсть запись
Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.
Черновик не сохраняется: текст только в этой вкладке.
Черновик изменён в другой вкладке. Твой текущий текст пока сохранён здесь, автоматическая запись остановлена.
Исследуй задачу
Самостоятельное исследованиеРассади оркестр
Пробуй свои варианты. Разбор останется закрытым.
Исследуй задачу
Рассади оркестр
Нажимай на клетки, чтобы посадить правшу или левшу. Модель покажет, кого бьёт каждый скрипач, и запомнит твой лучший оркестр без конфликтов.
Если модель не открылась (выключен JavaScript или страница загрузилась не полностью), условие, подсказки и разбор доступны и без неё.
Как исследовать без модели
Нарисуй доску 8×8 и сажай скрипачей буквами П и Л. После каждого отмечай крестиком две клетки, которые он бьёт. Потом раздели доску на полосы по два столбца и посчитай скрипачей в каждой.
Подсказка 1
Посмотри, как могут сидеть двое соседей в одной строке и что они бьют в строке выше. Потом раздели доску на вертикальные полосы шириной в две клетки.
Подсказка 2
Двое соседей в строке — это только «правша слева, левша справа», и тогда обе клетки над ними побиты. Поэтому в полосе из двух столбцов не больше скрипачей, и только при занятых верхних клетках полосы — . Могут ли две соседние полосы обе иметь по ?
Разобрать решение по шагам
Соседи в одной строке
Пусть два скрипача сидят рядом в одной строке. Правый не может быть правшой — он бил бы левого локтем. Левый не может быть левшой — он бил бы правого. Значит, такая пара — это правша слева и левша справа.
Трое подряд сидеть не могут: средний был бы правым в одной паре (значит, левша) и левым в другой (значит, правша).
Пара закрывает две клетки над собой
Правша из пары бьёт смычком клетку справа сверху — это клетка прямо над левшой. Левша бьёт клетку слева сверху — прямо над правшой. Так что над парой «правша, левша» обе клетки пусты.
Можно посадить
Легко посадить скрипача: например, занять столбцы через один — в столбце никто никого не бьёт. Но можно больше. На рисунке скрипача, и никто никого не бьёт: проверь стрелки сам или в модели (кнопка «Пример на 34»).
В полосе из двух столбцов — не больше , а иногда
Разделим доску на вертикальные полосы шириной в две клетки. В каждой строке полосы — не больше двух скрипачей.
Если в какой-то строке полосы (не в верхней) сидят двое, то это пара «правша, левша», и строка над ними в этой полосе пуста (шаг 2). Объединим такую строку со строкой над ней: в двух строках — скрипача, по на строку. В остальных строках полосы не больше скрипача — кроме, может быть, верхней строки доски: над ней ничего нет, и там могут сидеть двое.
Итак, в полосе не больше скрипачей, а — только если в верхней строке полосы сидят двое.
Больше нельзя
Если бы в двух соседних полосах было по , то в верхней строке доски сидели бы скрипача подряд, а даже трое подряд не могут (шаг 1). Значит, полос с скрипачами не больше двух (например, первая и третья), а в остальных — не больше :
Вместе с примером из шага 3 это значит, что наибольшее число скрипачей — .
Проверка
Проверим на компьютере. Программа перебрала все расстановки по строкам (какие скрипачи в строке, с учётом того, кого бьют скрипачи предыдущей строки): наибольшее число на доске — ровно . Тот же счёт для досок из строк даёт — каждая новая строка добавляет . В примере на рисунке программа проверила каждого скрипача: никто никого не бьёт.
Можно посадить скрипача, больше — нельзя.
Ответ
Можно посадить скрипача, больше — нельзя.
Главная идея
Два соседа в строке возможны только как «правша, левша», и тогда обе клетки над ними побиты. Поэтому в полосе из двух столбцов в среднем не больше одного скрипача на строку, и только верхняя строка может дать лишнего. Две соседние полосы не могут обе дать лишнего — в верхней строке было бы четверо подряд. Итого , и пример на есть.
Признаки: «расставьте как можно больше фигур, чтобы они не били друг друга». Нужны две части: пример и оценка. Для оценки разбей доску на одинаковые куски (здесь — полосы шириной ) и оцени каждый кусок; особые места (верхний край) учти отдельно.
Где легко ошибиться
Остановиться на (столбцы через один) и решить, что больше нельзя, — без доказательства. Обратная ошибка — найти и не доказать, что невозможно. Ещё одна — забыть, что верхняя строка особая: над ней никого не бьют.
Источник и авторство
Математический праздник 2023 года · классический вариант · 6 класс, задача 5 [до 7 баллов] · автор задачи М. А. Хачатурян.
Условия 2023 года (сайт праздника) ↗ · Бланк 6 класса (PDF) ↗ · Решения организатора (PDF) ↗ · Сайт Математического праздника ↗
Условие — с сайта праздника, рисунок перерисован по оригиналу. Подсказки, решение, рисунки и модель — Popov Academy. Задача сначала решена самостоятельно, затем ответ сверен с решением организатора: Ответ 34 совпадает с ответом организатора; оценка организатора тоже использует полосы шириной в две клетки.
Тема, знания и приёмы
Подсчёт вариантов · Продвинутая подготовка
- Пример и оценка в задачах «наибольшее число»
- Разбиение доски на части
Приёмы решения: Оценка и достижимость · Принцип Дирихле или худший случай