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

Условие

Найдите наименьшее $k$ при котором из любых $k$ различных чисел множества $\{1, 2, \ldots, 605\}$ обязательно найдутся два, разность которых равна $7$

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

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

Попробуй сначала набрать как можно больше чисел так, чтобы разности $7$ не было. Как связаны размер такого набора и искомое $k$ В модели выбирай числа на нитках. Ниже можно сверить ответ.

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

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

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

Самостоятельное исследованиеБусины на нитках

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

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

Бусины на нитках

Сколько чисел можно выбрать без разности 7 — и какое k это даёт?

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

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

Если модель не открылась, попробуй так. Выпиши числа от 1 до 30 в 7 строк по остаткам при делении на 7 (1, 8, 15, 22, 29; 2, 9, 16, …). Отметь как можно больше чисел так, чтобы в одной строке не было двух соседних.

Подсказка 1

Ищи наибольшее множество без двух чисел с разностью $7$ — искомое $k$ на единицу больше. У каких пар чисел разность равна $7$

Подсказка 2

По остаткам от деления на $7$ числа разбиваются на $7$ цепочек $r, r + 7, r + 14, \ldots$ Разность $7$ — только у соседей одной цепочки. Из цепочки длины $L$ без соседей можно взять не больше $\left\lceil \frac{L}{2} \right\rceil$ чисел.

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

Переформулировка

Пусть $m$ — наибольшее число элементов подмножества $\{1, \ldots, 605\}$ в котором нет двух чисел с разностью $7$ Тогда при $k = m$ разность не обязана найтись (возьмём это подмножество), а при $k = m + 1$ найдётся обязательно — иначе нашлось бы множество больше $m$ без разности $7$ Значит, ответ

k = m + 1,

и задача — найти $m$ доказать оценку «больше нельзя» и привести пример.

Цепочки по остаткам

Если $b - a = 7$ то $a$ и $b$ дают одинаковый остаток при делении на $7$ и стоят рядом в цепочке

r,\ r + 7,\ r + 14,\ \ldots \qquad (r = 1, 2, \ldots, 7).

Все числа от $1$ до $605$ разбиваются на эти $7$ цепочек, и разность $7$ бывает только у соседей одной цепочки. Поэтому каждую цепочку можно рассматривать отдельно: нужно взять из неё как можно больше чисел, не беря двух соседних.

Сколько чисел можно взять из одной цепочки

Пусть в цепочке $L$ чисел. Разобьём её на пары соседей: 1-е и 2-е, 3-е и 4-е, … (при нечётном $L$ последнее число останется без пары). Из каждой пары можно взять не больше одного числа, поэтому из цепочки — не больше

\left\lceil \frac{L}{2} \right\rceil.

Столько и получается, если брать числа через одного: 1-е, 3-е, 5-е, … — соседних среди них нет. На рисунке — цепочка остатка $1$

нитка остатка 1: 1, 8, 15, …, 603; из каждой пары соседей — не больше одного: из 87 чисел не больше 43 + 1 = 44

Длины цепочек и ответ

$605 = 7 \cdot 86 + 3$ Цепочки остатков $1, 2, 3$ содержат по $87$ чисел (последние — $603, 604, 605$ ), цепочки остатков $4, 5, 6, 0$ — по $86$ Значит,

m = 3 \cdot \left\lceil \frac{87}{2} \right\rceil + 4 \cdot \left\lceil \frac{86}{2} \right\rceil = 3 \cdot 44 + 4 \cdot 43 = 132 + 172 = 304.

Пример из $304$ чисел без разности $7$ — «через одного» во всех цепочках, и больше нельзя по оценке шага 3. Ответ: $k = 304 + 1 = 305$

Проверка

Тест строит набор «через одного» во всех цепочках: в нём $304$ числа и нет двух с разностью $7$ точный максимум, найденный перебором по цепочкам (и полным перебором подмножеств для малых $N$ ), совпадает с суммой $\sum \left\lceil \dfrac{L}{2} \right\rceil$ . Другие официальные версии: ID 6402 ( $N = 407$ $d = 5$ ): $407 = 5 \cdot 81 + 2$ $2 \cdot 41 + 3 \cdot 41 = 205$ , ответ $206$ ID 6403 ( $503$ $8$ ): $503 = 8 \cdot 62 + 7$ $7 \cdot 32 + 31 = 255$ ответ $256$ ID 6404 ( $713$ $9$ ): $713 = 9 \cdot 79 + 2$ $2 \cdot 40 + 7 \cdot 40 = 360$ , ответ $361$

Ответ

$305$

Ответ

$305$

Главная идея

Разность 7 — только у соседей в цепочках остатков по модулю 7; из цепочки длины $L$ без соседей берётся не больше $\left\lceil \dfrac{L}{2} \right\rceil$ чисел, итого 3 · 44 + 4 · 43 = 304, ответ 305.

«Из любых k чисел обязательно найдутся…» — найди наибольшее множество без нужной пары и прибавь 1; запрет на разность d разбивает числа на цепочки с шагом d.

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

Ответить 304 (забыть +1); считать все цепочки одной длины $\dfrac{605}{7}$ брать из цепочки нечётной длины $L$ только $\dfrac{L}{2}$ с округлением вниз.

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

Олимпиада «Физтех» · математика · 11 класс · 2026/27 · отборочный этап, второй тур (2 попытка, 01.11.2026). Задача 2, версия с ID 6401 — первая в официальном файле; другие версии этого номера (ID 6402, 6403, 6404) можно выбрать в модели.

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

Условие — из официального файла организатора. Подсказки, решение и модель — Popov Academy. Авторское решение записано до сверки с указаниями организатора; затем ответ совпадает с ответом организатора («Указания к решению: математика, 11 класс, 2 попытка 2026/27», стр. 1 ↗: ID 6401: 305; ID 6402: 206; ID 6403: 256; ID 6404: 361.). Сверены все четыре официальные версии этого номера. Таблица официальных ответов была прочитана при разборе входных данных до собственного решения; указания к решению не открывались.

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

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

Гарантии и принцип Дирихле · Нужна школьная база

Остатки от деления
Принцип Дирихле (идея оценки и примера)

Приёмы решения: Сравнение остатков · Оценка и достижимость

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