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

Условие

Каждый из $11$ учеников записал к себе в тетрадь какие-то натуральные числа, не превосходящие $N$ Оказалось, что если взять любых $6$ учеников, то в их тетрадях можно найти любое натуральное число, не превосходящее $N$ а если взять любых $5$ учеников — нет (то есть найдется число, которого нет ни в одной тетради этих $5$ учеников). При каком наименьшем $N$ такое может быть?

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

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

Возьми какую-нибудь пятёрку учеников и число, которого у них нет. У кого из остальных шести это число есть? Может ли одно и то же число «обслуживать» две разные пятёрки? В модели заполняй таблицу для маленького класса. Ниже можно сверить ответ.

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

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

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

Самостоятельное исследованиеТетради маленького класса

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

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

Тетради маленького класса

Сколько чисел нужно, чтобы любые k учеников вместе имели все числа, а любые k − 1 — нет?

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

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

Если модель не открылась, попробуй так. Возьми 4 ученика: любые 3 должны вместе иметь все числа, а любые 2 — нет. Составь таблицу: какие числа у кого. Сколько чисел понадобилось? Сравни с числом пар учеников.

Подсказка 1

Пусть у пятёрки $G$ нет числа $x$ Если бы $x$ не было ещё у какого-то ученика вне $G$ то нашлись бы шесть учеников без $x$ Значит, $x$ есть у всех остальных шести.

Подсказка 2

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

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

Каждой пятёрке — своё число

Для каждой пятёрки учеников есть число, которого нет ни в одной из их тетрадей; выберем для каждой пятёрки одно такое число.

Пусть двум разным пятёркам $G$ и $G'$ выбрано одно и то же число $x$ Тогда $x$ нет ни у кого из учеников $G \cup G'$ а их не меньше шести (пятёрки разные). Но у любых шести учеников есть все числа — противоречие. Значит, разным пятёркам выбраны разные числа.

Оценка

Пятёрок из $11$ учеников

C_{11}^5 = \frac{11 \cdot 10 \cdot 9 \cdot 8 \cdot 7}{5!} = 462,

и все выбранные числа разные, поэтому $N \geqslant 462$

Пример с N = 462

Занумеруем все $462$ пятёрки числами от $1$ до $462$ Число $i$ записывают все ученики, кроме пятёрки с номером $i$ (то есть его записывают $6$ учеников).

Любые $6$ учеников: для каждого числа $i$ хотя бы один из них не входит в пятёрку $i$ и записал $i$ — все числа есть. Любые $5$ учеников образуют какую-то пятёрку $i$ и числа $i$ ни у кого из них нет. Оба условия выполнены.

Ответ

Наименьшее $N = C_{11}^5 = 462$ В общем виде, если любые $k$ учеников из $n$ имеют все числа, а любые $k - 1$ — нет, то наименьшее $N = C_n^{k - 1}$

Проверка

Тест для всех четырёх версий сравнивает $C_n^{k-1}$ с официальным ответом; на маленьких классах (от $4$ до $7$ учеников) проверяет, что пример выполняет оба условия, а без любого его числа второе условие ломается; полным перебором всех таблиц для классов до $5$ учеников подтверждает, что меньшим числом чисел не обойтись. Модель даёт заполнить такую таблицу для класса из $3$ – $6$ учеников и проверяет оба условия. Другие версии ( $C_n^{k-1}$ ): ID 3985 ( $12$ учеников, любые $7$ ): $C_{12}^6 = 924$ ID 3986 ( $13$ любые $6$ ): $C_{13}^5 = 1287$ ID 3987 ( $14$ любые $7$ ): $C_{14}^6 = 3003$

Ответ

$462$

Ответ

$462$

Главная идея

Каждой пятёрке соответствует число, которого у неё нет, и у разных пятёрок эти числа разные (иначе шестеро без числа), поэтому N ⩾ C(11, 5) = 462; пример — число для каждой пятёрки записывают все остальные шесть.

«Любые k вместе имеют всё, любые k − 1 — нет» — сопоставь каждой (k − 1)-группе свой недостающий предмет и докажи, что сопоставление различает группы; пример строится по тому же сопоставлению.

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

Доказать только оценку или только пример; считать пятёрки как 11·5 или 11!/5!; не объяснить, почему у разных пятёрок разные числа.

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

Олимпиада «Физтех» · математика · 11 класс · 2024/25 · отборочный этап, третий тур (3 попытка). Задача 10, версия с ID 3984 — первая в официальном файле; другие версии этого номера (ID 3985, 3986, 3987) можно выбрать в модели.

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

Условие — из официального файла организатора. Подсказки, решение и модель — Popov Academy. Авторское решение записано до знакомства с решениями организатора; затем ответ совпадает с ответом организатора («Решения Ф11 3 попытка», стр. 10 ↗: ID 3984: 462; ID 3985: 924; ID 3986: 1287; ID 3987: 3003.). Сверены все четыре официальные версии этого номера.

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

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

Подсчёт вариантов · Начальный вход

Число сочетаний
Оценка плюс пример

Приёмы решения: Последовательный подсчёт без повторов · Оценка и достижимость

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