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