Математика · 6 класс · Олимпиада СПб 2021/22 · районный тур

Задача 4. Дежурные за столами

Условие

В классе 25 мальчиков и 5 девочек, все они разного роста. Каждый день всех учеников рассаживают по 5 человек за 6 столов, и за каждым столом самого высокого назначают дежурным. Могло ли через 31 день оказаться, что все мальчики отдежурили поровну раз?

Второй вариант этой задачи

На олимпиаде соседи по парте получают разные варианты. Условие второго варианта:

В классе 6 мальчиков и 24 девочки, у всех разные даты рождения. Каждый день всех учеников рассаживают по 6 человек за 5 столов, и за каждым столом самого старшего назначают дежурным. Могло ли через 31 день оказаться, что все девочки отдежурили поровну раз?

Его решение и ответ — в последнем шаге разбора.

О задаче · 6 класс
Олимпиада
Санкт-Петербургская олимпиада школьников по математике, 88-я (2022)
Этап
I тур (районный)
Предмет / класс
Математика · 6 класс
Дата
4 декабря 2021 г.

Сначала попробуй сам: придумай, как могут стоять по росту мальчики и девочки, и составь расписание хотя бы на несколько дней — кто с кем сидит и кто дежурит. Сколько всего дежурств набирается за 3131 день и сколько из них тогда достанется каждому мальчику? В модели «Журнал дежурств» ты сам расставляешь класс по росту и назначаешь дежурных на каждый день: модель проверяет, можно ли так рассадить учеников, показывает столы и считает, сколько раз дежурил каждый.

Ответ — «да» с примером расписания или «нет» с объяснением, почему так не бывает ни при каком расписании.

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

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

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

Самостоятельное исследованиеЖурнал дежурств

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

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

Журнал дежурств

Расставь 30 учеников по росту и составь журнал дежурств на 31 день. Получится ли, чтобы все мальчики отдежурили поровну? (Во 2 варианте — 6 мальчиков и 24 девочки, дежурит самый старший, поровну должны отдежурить девочки.)

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

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

Без JavaScript модель не работает. Нарисуй на листке строй из 30 учеников по росту и отметь, кто из них девочки. Выбери на день 6 дежурных и проверь, можно ли рассадить остальных по 5 за столы так, чтобы за каждым столом дежурный был выше всех. Составь несколько дней и посчитай, сколько раз дежурил каждый мальчик.

Подсказка 1

Не пытайся сразу составить всё расписание на 3131 день. Посмотри на крайних учеников: кто дежурит каждый день, как бы ни рассаживали, и кому подежурить труднее всех? Что это значит, если все мальчики дежурили поровну?

Подсказка 2

Самый высокий ученик класса дежурит все 3131 день — подумай, может ли это быть мальчик. Самый низкий мальчик должен хоть раз подежурить (почему каждый день дежурит хотя бы один мальчик?) — кто тогда сидел с ним за столом? Узнав, где по росту стоят девочки, посчитай, сколько девочек дежурит каждый день и сколько дежурств набирают мальчики за 3131 день.

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

Считаем дежурства

Каждый день за 66 столами дежурят 66 человек, поэтому за 3131 день набирается

6⋅31=1866\cdot 31 = 186

дежурств. Пусть все мальчики отдежурили поровну — каждый по kk раз. Тогда мальчики вместе отдежурили 25⋅k25\cdot k раз.

Может ли быть k=0k = 0, то есть мальчики не дежурили ни разу? Нет. Девочек 55, а столов 66, поэтому каждый день хотя бы за одним столом нет ни одной девочки — там дежурит мальчик. Значит, мальчики дежурили, и kk не меньше 11.

2

Самый высокий дежурит каждый день

Возьмём самого высокого ученика всего класса. За каким бы столом он ни сидел, он там выше всех, значит, дежурит каждый день — все 3131 раз.

Если это мальчик, то k=31k = 31: каждый мальчик дежурил 3131 раз, и мальчики вместе отдежурили

25⋅31=77525\cdot 31 = 775

раз. А всех дежурств только 186186. Так не бывает.

Значит, выше всех в классе — девочка, и она дежурит все 3131 день.

3

Самый низкий мальчик

Теперь возьмём самого низкого из мальчиков. По шагу 1 он хоть раз дежурил. В такой день, кроме него, за его столом сидят ещё 44 человека, и все они ниже него — ведь дежурит самый высокий. Но все остальные мальчики выше него. Значит, эти 44 человека — девочки, и они ниже всех мальчиков.

Итак, девочки стоят по росту только так: 44 девочки ниже всех мальчиков, а пятая — выше всех в классе (рисунок ниже).

1234567……2829304 девочки№1–425 мальчиков№5–29девочка№30по ростувыше всех —дежуриткаждый день★самый низкиймальчик▼
Класс по росту, слева самый низкий. Если все мальчики дежурили поровну, то по шагам 2 и 3 строй может быть только таким: четыре девочки (№1–4) ниже всех мальчиков, потом 2525 мальчиков (№5–29), а выше всех — девочка №30. Она дежурит каждый день; самый низкий мальчик №5 может дежурить, только когда за его столом все четыре маленькие девочки.
4

Маленькие девочки не дежурят никогда

Возьмём одну из четырёх «маленьких» девочек. Если за её столом есть хоть один мальчик, он выше неё, и дежурит не она. Если мальчиков за столом нет, то за столом 55 девочек — то есть все пять, и среди них самая высокая в классе. И снова дежурит не маленькая девочка.

Значит, из девочек дежурит только самая высокая — каждый день ровно одна девочка. Остальные 55 дежурных каждый день — мальчики (рисунок ниже).

12345Стол 1678910Стол 21112131415Стол 31617181920Стол 42122232425Стол 52627282930Стол 6дежурит самый высокий за столомдежурят 5 мальчиков и 1 девочка (№30)
Один из возможных дней в таком строе: за каждым столом дежурит самый высокий (красная повязка, номер на красной метке). Маленькие девочки №1–4 сидят с мальчиком №5 и не дежурят; из девочек дежурит только №30, остальные пять дежурных — мальчики. Так в любой день: 55 мальчиков, за 3131 день — 155155 дежурств.
5

Не делится

За 3131 день мальчики отдежурили

5⋅31=1555\cdot 31 = 155

раз. С другой стороны, это 25⋅k25\cdot k раз. Но 155155 на 2525 не делится:

25⋅6=150<155<175=25⋅7.25\cdot 6 = 150 < 155 < 175 = 25\cdot 7.

Противоречие: как бы ни стояли ученики по росту и как бы их ни рассаживали, поровну мальчики отдежурить не могли.

Ответ: нет, не могло.

6

Второй вариант

Во втором варианте 66 мальчиков и 2424 девочки, все с разными датами рождения, поэтому из любых двоих один старше. Каждый день их рассаживают по 66 человек за 55 столов, дежурит самый старший за столом, и спрашивают, могли ли девочки отдежурить поровну. Каждый день 55 дежурных, за 3131 день —

5⋅31=1555\cdot 31 = 155

дежурств.

Буквальное прочтение: да. В отличие от первого варианта, мальчиков (66) больше, чем столов (55), и мальчик может сидеть за каждым столом. Пусть 66 мальчиков старше всех девочек. Каждый день за первый стол сажаем 22 мальчиков и 44 девочки, за остальные четыре — по 11 мальчику и 55 девочек. За каждым столом старший — мальчик, поэтому девочки не дежурят ни разу, и через 3131 день все девочки отдежурили поровну — по 00 раз.

Если каждая девочка дежурила хотя бы раз: нет. Пусть каждая девочка дежурила kk раз, k≥1k \ge 1. Рассуждаем, как в шагах 2–5, поменяв роли мальчиков и девочек.

  • Самый старший в классе дежурит все 3131 день. Если это девочка, то k=31k = 31, и девочки вместе отдежурили 24⋅31=74424\cdot 31 = 744 раза — больше, чем всех дежурств. Значит, старше всех — мальчик.
  • Самая младшая девочка хоть раз дежурила. В тот день 55 её соседей младше неё, а все остальные девочки старше — значит, это 55 мальчиков, младше всех девочек. Шестой мальчик — самый старший в классе.
  • Маленький мальчик не дежурит никогда: если за его столом есть девочка, она старше него; если девочек нет, за столом все 66 мальчиков, и среди них самый старший.

Значит, каждый день дежурит ровно один мальчик и ровно 44 девочки, и за 3131 день девочки отдежурили

4⋅31=1244\cdot 31 = 124

раза. Но это 24⋅k24\cdot k, а 124124 на 2424 не делится:

24⋅5=120<124<144=24⋅6.24\cdot 5 = 120 < 124 < 144 = 24\cdot 6.

Противоречие.

Ответ: при буквальном прочтении — да, могло (все девочки по 00 раз); если каждая девочка дежурила хотя бы раз — нет, не могло.

Проверка

Рассуждение проверено перебором на компьютере. Сначала проверено правило рассадки: набор из 66 дежурных возможен ровно тогда, когда у каждого из них хватает недежурных соседей ниже: у самого низкого дежурного ниже него не меньше 44 недежурных, у второго снизу — не меньше 88, и так далее (правило сверено со всеми рассадками маленьких классов). Затем для каждой из 142506142506 расстановок пяти девочек среди 3030 мест по росту перебраны все возможные дни и все наборы из 3131 дня: ни в одной расстановке мальчики не набирают поровну — даже если следить только за общим числом их дежурств, за самым высоким и за самым низким мальчиком. Самый низкий мальчик может дежурить только тогда, когда девочки стоят на местах 11–44, и там в любой день дежурит не больше одной девочки. Почти поровну бывает: если девочки — четыре самых низких и самая высокая, а мальчики дежурят «лесенкой» (№5, №10, №15, №20, №25, на другой день №6, №11, №16, №21, №26 и так далее), каждый мальчик дежурит 66 или 77 раз — но не поровну. Для второго варианта перебраны все 593775593775 расстановок шести мальчиков: поровну по k≥1k \ge 1 раз девочки не набирают ни в одной, а по 00 раз — набирают.

Ответ

1 вариант. Нет, не могло. Если бы все мальчики дежурили поровну, то выше всех в классе была бы девочка, а остальные четыре девочки — ниже всех мальчиков; тогда каждый день дежурят ровно 55 мальчиков, за 3131 день — 155155 раз, а 155155 на 2525 не делится.

2 вариант. При буквальном прочтении — да, могло: если 66 мальчиков старше всех девочек и каждый день за каждым столом сидит хотя бы один мальчик, ни одна девочка не дежурит, и все девочки отдежурили поровну — по 00 раз. Если считать, что каждая девочка дежурила хотя бы раз, — нет, не могло: тогда каждый день дежурят ровно 44 девочки, за 3131 день — 124124 раза, а 124124 на 2424 не делится.

Ответ

1 вариант. Нет, не могло. Если бы все мальчики дежурили поровну, то выше всех в классе была бы девочка, а остальные четыре девочки — ниже всех мальчиков; тогда каждый день дежурят ровно 55 мальчиков, за 3131 день — 155155 раз, а 155155 на 2525 не делится.

2 вариант. При буквальном прочтении — да, могло: если 66 мальчиков старше всех девочек и каждый день за каждым столом сидит хотя бы один мальчик, ни одна девочка не дежурит, и все девочки отдежурили поровну — по 00 раз. Если считать, что каждая девочка дежурила хотя бы раз, — нет, не могло: тогда каждый день дежурят ровно 44 девочки, за 3131 день — 124124 раза, а 124124 на 2424 не делится.

Главная идея

Смотреть на крайних. Самый высокий в классе дежурит каждый день, поэтому он не может быть мальчиком. Самый низкий мальчик хоть раз дежурил (мальчики дежурят каждый день: девочек меньше, чем столов), а для этого нужны 44 девочки ниже всех мальчиков. Тогда из девочек дежурит только самая высокая, мальчики набирают ровно 5⋅31=1555\cdot 31 = 155 дежурств, а 155155 на 2525 не делится.

Если в процессе «в каждой группе выигрывает самый большой» спрашивают, могло ли что-то распределиться поровну, посмотри на крайних участников: самый большой выигрывает всегда, а самому маленькому для победы нужно особое окружение. Это сильно ограничивает, кто где стоит, и дальше остаётся посчитать.

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

Составить одно-два неудачных расписания и ответить «нет»: неудачные попытки ничего не доказывают, нужно объяснить, почему не выйдет ни при каком строе и ни при каком расписании. Другая ошибка — считать только общее число дежурств: их 186186, мальчикам можно отдать 175=25⋅7175 = 25\cdot 7, девочкам 1111 — и кажется, что всё сходится. Такой счёт не замечает, что самый высокий дежурит каждый день, а самому низкому мальчику нужны четыре девочки ниже него.

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

Санкт-Петербургская олимпиада школьников по математике · 88-я олимпиада (2022 год) · I тур (районный), 4 декабря 2021 г. · 6 класс, задача 4.

Условия (PDF организатора, первый вариант) ↗ · Листки олимпиады, оба варианта (ZIP организатора) ↗ · Страница олимпиады 2022 года ↗ · Сайт олимпиады ↗

Условие первого варианта — из файла организатора, второй вариант переписан с листка. Подсказки, решение и модель — Popov Academy. Организатор не публикует решений районного тура. Ответы обоих вариантов получены двумя независимыми решениями и совпали; где можно, проверены перебором или вычислением.

На сайте олимпиады: «Распространение представленных материалов разрешается и приветствуется.»

Продолжить тему: Гарантии и принцип Дирихле →
Увеличенный рисунок