Условие
В классе 25 мальчиков и 5 девочек, все они разного роста. Каждый день всех учеников рассаживают по 5 человек за 6 столов, и за каждым столом самого высокого назначают дежурным. Могло ли через 31 день оказаться, что все мальчики отдежурили поровну раз?
Второй вариант этой задачи
На олимпиаде соседи по парте получают разные варианты. Условие второго варианта:
В классе 6 мальчиков и 24 девочки, у всех разные даты рождения. Каждый день всех учеников рассаживают по 6 человек за 5 столов, и за каждым столом самого старшего назначают дежурным. Могло ли через 31 день оказаться, что все девочки отдежурили поровну раз?
Его решение и ответ — в последнем шаге разбора.
О задаче · 6 класс
Сначала попробуй сам: придумай, как могут стоять по росту мальчики и девочки, и составь расписание хотя бы на несколько дней — кто с кем сидит и кто дежурит. Сколько всего дежурств набирается за день и сколько из них тогда достанется каждому мальчику? В модели «Журнал дежурств» ты сам расставляешь класс по росту и назначаешь дежурных на каждый день: модель проверяет, можно ли так рассадить учеников, показывает столы и считает, сколько раз дежурил каждый.
Ответ — «да» с примером расписания или «нет» с объяснением, почему так не бывает ни при каком расписании.
Записать идеюЕсть запись
Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.
Черновик не сохраняется: текст только в этой вкладке.
Черновик изменён в другой вкладке. Твой текущий текст пока сохранён здесь, автоматическая запись остановлена.
Исследуй задачу
Самостоятельное исследованиеЖурнал дежурств
Пробуй свои варианты. Разбор останется закрытым.
Исследуй задачу
Журнал дежурств
Расставь 30 учеников по росту и составь журнал дежурств на 31 день. Получится ли, чтобы все мальчики отдежурили поровну? (Во 2 варианте — 6 мальчиков и 24 девочки, дежурит самый старший, поровну должны отдежурить девочки.)
Если модель не открылась (выключен JavaScript или страница загрузилась не полностью), условие, подсказки и разбор доступны и без неё.
Подсказка для решения без модели
Без JavaScript модель не работает. Нарисуй на листке строй из 30 учеников по росту и отметь, кто из них девочки. Выбери на день 6 дежурных и проверь, можно ли рассадить остальных по 5 за столы так, чтобы за каждым столом дежурный был выше всех. Составь несколько дней и посчитай, сколько раз дежурил каждый мальчик.
Подсказка 1
Не пытайся сразу составить всё расписание на день. Посмотри на крайних учеников: кто дежурит каждый день, как бы ни рассаживали, и кому подежурить труднее всех? Что это значит, если все мальчики дежурили поровну?
Подсказка 2
Самый высокий ученик класса дежурит все день — подумай, может ли это быть мальчик. Самый низкий мальчик должен хоть раз подежурить (почему каждый день дежурит хотя бы один мальчик?) — кто тогда сидел с ним за столом? Узнав, где по росту стоят девочки, посчитай, сколько девочек дежурит каждый день и сколько дежурств набирают мальчики за день.
Разобрать решение по шагам
Считаем дежурства
Каждый день за столами дежурят человек, поэтому за день набирается
дежурств. Пусть все мальчики отдежурили поровну — каждый по раз. Тогда мальчики вместе отдежурили раз.
Может ли быть , то есть мальчики не дежурили ни разу? Нет. Девочек , а столов , поэтому каждый день хотя бы за одним столом нет ни одной девочки — там дежурит мальчик. Значит, мальчики дежурили, и не меньше .
Самый высокий дежурит каждый день
Возьмём самого высокого ученика всего класса. За каким бы столом он ни сидел, он там выше всех, значит, дежурит каждый день — все раз.
Если это мальчик, то : каждый мальчик дежурил раз, и мальчики вместе отдежурили
раз. А всех дежурств только . Так не бывает.
Значит, выше всех в классе — девочка, и она дежурит все день.
Самый низкий мальчик
Теперь возьмём самого низкого из мальчиков. По шагу 1 он хоть раз дежурил. В такой день, кроме него, за его столом сидят ещё человека, и все они ниже него — ведь дежурит самый высокий. Но все остальные мальчики выше него. Значит, эти человека — девочки, и они ниже всех мальчиков.
Итак, девочки стоят по росту только так: девочки ниже всех мальчиков, а пятая — выше всех в классе (рисунок ниже).
Маленькие девочки не дежурят никогда
Возьмём одну из четырёх «маленьких» девочек. Если за её столом есть хоть один мальчик, он выше неё, и дежурит не она. Если мальчиков за столом нет, то за столом девочек — то есть все пять, и среди них самая высокая в классе. И снова дежурит не маленькая девочка.
Значит, из девочек дежурит только самая высокая — каждый день ровно одна девочка. Остальные дежурных каждый день — мальчики (рисунок ниже).
Не делится
За день мальчики отдежурили
раз. С другой стороны, это раз. Но на не делится:
Противоречие: как бы ни стояли ученики по росту и как бы их ни рассаживали, поровну мальчики отдежурить не могли.
Ответ: нет, не могло.
Второй вариант
Во втором варианте мальчиков и девочки, все с разными датами рождения, поэтому из любых двоих один старше. Каждый день их рассаживают по человек за столов, дежурит самый старший за столом, и спрашивают, могли ли девочки отдежурить поровну. Каждый день дежурных, за день —
дежурств.
Буквальное прочтение: да. В отличие от первого варианта, мальчиков () больше, чем столов (), и мальчик может сидеть за каждым столом. Пусть мальчиков старше всех девочек. Каждый день за первый стол сажаем мальчиков и девочки, за остальные четыре — по мальчику и девочек. За каждым столом старший — мальчик, поэтому девочки не дежурят ни разу, и через день все девочки отдежурили поровну — по раз.
Если каждая девочка дежурила хотя бы раз: нет. Пусть каждая девочка дежурила раз, . Рассуждаем, как в шагах 2–5, поменяв роли мальчиков и девочек.
- Самый старший в классе дежурит все день. Если это девочка, то , и девочки вместе отдежурили раза — больше, чем всех дежурств. Значит, старше всех — мальчик.
- Самая младшая девочка хоть раз дежурила. В тот день её соседей младше неё, а все остальные девочки старше — значит, это мальчиков, младше всех девочек. Шестой мальчик — самый старший в классе.
- Маленький мальчик не дежурит никогда: если за его столом есть девочка, она старше него; если девочек нет, за столом все мальчиков, и среди них самый старший.
Значит, каждый день дежурит ровно один мальчик и ровно девочки, и за день девочки отдежурили
раза. Но это , а на не делится:
Противоречие.
Ответ: при буквальном прочтении — да, могло (все девочки по раз); если каждая девочка дежурила хотя бы раз — нет, не могло.
Проверка
Рассуждение проверено перебором на компьютере. Сначала проверено правило рассадки: набор из дежурных возможен ровно тогда, когда у каждого из них хватает недежурных соседей ниже: у самого низкого дежурного ниже него не меньше недежурных, у второго снизу — не меньше , и так далее (правило сверено со всеми рассадками маленьких классов). Затем для каждой из расстановок пяти девочек среди мест по росту перебраны все возможные дни и все наборы из дня: ни в одной расстановке мальчики не набирают поровну — даже если следить только за общим числом их дежурств, за самым высоким и за самым низким мальчиком. Самый низкий мальчик может дежурить только тогда, когда девочки стоят на местах –, и там в любой день дежурит не больше одной девочки. Почти поровну бывает: если девочки — четыре самых низких и самая высокая, а мальчики дежурят «лесенкой» (№5, №10, №15, №20, №25, на другой день №6, №11, №16, №21, №26 и так далее), каждый мальчик дежурит или раз — но не поровну. Для второго варианта перебраны все расстановок шести мальчиков: поровну по раз девочки не набирают ни в одной, а по раз — набирают.
1 вариант. Нет, не могло. Если бы все мальчики дежурили поровну, то выше всех в классе была бы девочка, а остальные четыре девочки — ниже всех мальчиков; тогда каждый день дежурят ровно мальчиков, за день — раз, а на не делится.
2 вариант. При буквальном прочтении — да, могло: если мальчиков старше всех девочек и каждый день за каждым столом сидит хотя бы один мальчик, ни одна девочка не дежурит, и все девочки отдежурили поровну — по раз. Если считать, что каждая девочка дежурила хотя бы раз, — нет, не могло: тогда каждый день дежурят ровно девочки, за день — раза, а на не делится.
Ответ
1 вариант. Нет, не могло. Если бы все мальчики дежурили поровну, то выше всех в классе была бы девочка, а остальные четыре девочки — ниже всех мальчиков; тогда каждый день дежурят ровно мальчиков, за день — раз, а на не делится.
2 вариант. При буквальном прочтении — да, могло: если мальчиков старше всех девочек и каждый день за каждым столом сидит хотя бы один мальчик, ни одна девочка не дежурит, и все девочки отдежурили поровну — по раз. Если считать, что каждая девочка дежурила хотя бы раз, — нет, не могло: тогда каждый день дежурят ровно девочки, за день — раза, а на не делится.
Главная идея
Смотреть на крайних. Самый высокий в классе дежурит каждый день, поэтому он не может быть мальчиком. Самый низкий мальчик хоть раз дежурил (мальчики дежурят каждый день: девочек меньше, чем столов), а для этого нужны девочки ниже всех мальчиков. Тогда из девочек дежурит только самая высокая, мальчики набирают ровно дежурств, а на не делится.
Если в процессе «в каждой группе выигрывает самый большой» спрашивают, могло ли что-то распределиться поровну, посмотри на крайних участников: самый большой выигрывает всегда, а самому маленькому для победы нужно особое окружение. Это сильно ограничивает, кто где стоит, и дальше остаётся посчитать.
Где легко ошибиться
Составить одно-два неудачных расписания и ответить «нет»: неудачные попытки ничего не доказывают, нужно объяснить, почему не выйдет ни при каком строе и ни при каком расписании. Другая ошибка — считать только общее число дежурств: их , мальчикам можно отдать , девочкам — и кажется, что всё сходится. Такой счёт не замечает, что самый высокий дежурит каждый день, а самому низкому мальчику нужны четыре девочки ниже него.
Источник и авторство
Санкт-Петербургская олимпиада школьников по математике · 88-я олимпиада (2022 год) · I тур (районный), 4 декабря 2021 г. · 6 класс, задача 4.
Условия (PDF организатора, первый вариант) ↗ · Листки олимпиады, оба варианта (ZIP организатора) ↗ · Страница олимпиады 2022 года ↗ · Сайт олимпиады ↗
Условие первого варианта — из файла организатора, второй вариант переписан с листка. Подсказки, решение и модель — Popov Academy. Организатор не публикует решений районного тура. Ответы обоих вариантов получены двумя независимыми решениями и совпали; где можно, проверены перебором или вычислением.
На сайте олимпиады: «Распространение представленных материалов разрешается и приветствуется.»
Тема, знания и приёмы
Гарантии и принцип Дирихле · Продвинутая подготовка
- Если каждый из 25 мальчиков дежурил k раз, то все вместе — 25· k раз
- Принцип Дирихле: 5 девочек не могут сидеть за всеми 6 столами
- Чтобы ответить «нет», нужно доказать, что не выйдет ни при каком раскладе
Приёмы решения: Принцип Дирихле или худший случай · Логический вывод и исключение вариантов · Последовательный подсчёт без повторов