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

Условие

Фокусник попросил $60$ зрителей загадать различные числа, каждого — одно число. За один вопрос фокусник может выбрать любых трёх зрителей и спросить, какие числа они загадали. В ответ ему скажут множество из трёх чисел. За какое наименьшее количество вопросов фокусник может указать, какие числа загадал каждый из зрителей?

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

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

Когда фокусник точно знает, чьё число какое? Что, если двоих зрителей спрашивали в одних и тех же вопросах? В модели задавай вопросы небольшой группе зрителей и добивайся, чтобы фокусник узнал все числа. Ниже можно сверить ответ.

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

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

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

Самостоятельное исследованиеВопросы фокусника

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

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

Вопросы фокусника

Как узнать числа всех зрителей за наименьшее число вопросов?

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

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

Если модель не открылась, попробуй так. Возьми шестерых зрителей A–F и задай вопросы ABC, CDE, EFA. Для каждого зрителя выпиши, в каких вопросах он был. Есть ли двое с одинаковыми списками?

Подсказка 1

Каждого зрителя нужно спросить хотя бы раз. Двое зрителей, которых спрашивали ровно по одному разу, не могут быть в одном вопросе: иначе они могли бы обменяться числами незаметно. Сколько таких зрителей может быть при $N$ вопросах?

Подсказка 2

В $N$ вопросах всего $3N$ мест. Посчитай места: «один раз» — не больше $N$ зрителей, остальные — хотя бы по два места. Получится $N \geqslant 30$ Для примера раздели зрителей на шестёрки и спроси в каждой три тройки.

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

Когда числа определяются

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

Наоборот, если всех спрашивали и наборы всех зрителей различны, фокусник знает всё: число $x$ встречается ровно в ответах на вопросы из набора его владельца, а такой набор у одного зрителя.

Оценка: не меньше 30 вопросов

Пусть задано $N$ вопросов и $M$ зрителей спрашивали ровно по одному разу. Двое таких в одном вопросе имели бы одинаковые наборы, поэтому в каждом вопросе не больше одного такого зрителя: $M \leqslant N$ Остальных $60 - M$ зрителей спрашивали хотя бы дважды. Всего мест в вопросах $3N$ поэтому

3N \geqslant M + 2(60 - M) = 120 - M \geqslant 120 - N \;\Rightarrow\; 4N \geqslant 120 \;\Rightarrow\; N \geqslant 30.

Пример на 30 вопросов

Разобьём зрителей на $10$ шестёрок. В шестёрке $A, B, C, D, E, F$ спросим тройки $ABC$ $CDE$ $EFA$ Наборы: $A$ — вопросы $1$ и $3$ $B$ — только $1$ $C$ — $1$ и $2$ $D$ — только $2$ $E$ — $2$ и $3$ $F$ — только $3$ Все шесть наборов разные, а у разных шестёрок вопросы разные. По шагу 1 фокусник узнаёт все числа за $10 \cdot 3 = 30$ вопросов.

Шестёрка зрителей: вопросы — стороны треугольника. Под каждым зрителем — номера его вопросов.

Проверка

Например, ответы на вопросы $ABC$ $CDE$ $EFA$ $\{12, 47, 85\}$ $\{30, 66, 85\}$ $\{9, 47, 66\}$ Число $85$ — в ответах $1$ и $2$ значит, это $C$ $47$ — в $1$ и $3$ — это $A$ $66$ — в $2$ и $3$ — это $E$ $12$ $30$ $9$ встречаются по одному разу — это $B$ $D$ $F$ Тест модели сравнивает признак «все наборы различны» с полным перебором расстановок чисел для малых групп, проверяет пример и расшифровку для $60$ $90$ $120$ $150$ зрителей и перебором подтверждает, что для $6$ зрителей двух вопросов мало. Другие официальные версии: $90$ зрителей — $45$ $120$ — $60$ $150$ — $75$

Ответ

$30$

Ответ

$30$

Главная идея

Числа определяются ⇔ у всех зрителей разные непустые наборы вопросов; спрошенных один раз не больше числа вопросов, отсюда 3N ⩾ 120 − N; пример — шестёрки с вопросами ABC, CDE, EFA.

«За какое наименьшее число вопросов можно узнать…» — оценка подсчётом мест плюс пример.

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

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

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

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

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

Условие — из официального файла организатора. Подсказки, решение и модель — Popov Academy. Авторское решение записано до знакомства с решениями организатора; затем ответ совпадает с ответом организатора («Решения М10 2 попытка», стр. 11 ↗: ID 3862: 30; ID 3863: 45; ID 3864: 60; ID 3865: 75.). Сверены все четыре официальные версии этого номера.

Продолжить тему: Гарантии и принцип Дирихле →

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

Гарантии и принцип Дирихле · Начальный вход

Оценка + пример
Подсчёт двумя способами

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

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