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

Условие

Есть $300$ карточек с числами от $1$ до $300$ (на каждой карточке написано ровно одно число, числа на карточках попарно различны). Сколькими способами можно выбрать три карточки, чтобы сумма чисел на них была кратна $3$

Есть $270$ карточек с числами от $1$ до $270$ (на каждой карточке написано ровно одно число, числа на карточках попарно различны). Сколькими способами можно выбрать три карточки, чтобы сумма чисел на них была кратна $3$

Есть $240$ карточек с числами от $1$ до $240$ (на каждой карточке написано ровно одно число, числа на карточках попарно различны). Сколькими способами можно выбрать три карточки, чтобы сумма чисел на них была кратна $3$

Есть $210$ карточек с числами от $1$ до $210$ (на каждой карточке написано ровно одно число, числа на карточках попарно различны). Сколькими способами можно выбрать три карточки, чтобы сумма чисел на них была кратна $3$

На доске написаны подряд идущие натуральные числа от $1$ до $301$ (каждое из них ровно один раз). Сколькими способами можно стереть три из написанных чисел так, чтобы остаток от деления суммы всех чисел на доске на $3$ после этого не изменился?

На доске написаны подряд идущие натуральные числа от $1$ до $271$ (каждое из них ровно один раз). Сколькими способами можно стереть три из написанных чисел так, чтобы остаток от деления суммы всех чисел на доске на $3$ после этого не изменился?

На доске написаны подряд идущие натуральные числа от $1$ до $241$ (каждое из них ровно один раз). Сколькими способами можно стереть три из написанных чисел так, чтобы остаток от деления суммы всех чисел на доске на $3$ после этого не изменился?

На доске написаны подряд идущие натуральные числа от $1$ до $211$ (каждое из них ровно один раз). Сколькими способами можно стереть три из написанных чисел так, чтобы остаток от деления суммы всех чисел на доске на $3$ после этого не изменился?

Сколько существует способов выбрать из натуральных чисел от $1$ до $302$ три различных числа так, чтобы их сумма делилась на $3$

Сколько существует способов выбрать из натуральных чисел от $1$ до $272$ три различных числа так, чтобы их сумма делилась на $3$

Сколько существует способов выбрать из натуральных чисел от $1$ до $242$ три различных числа так, чтобы их сумма делилась на $3$

Сколько существует способов выбрать из натуральных чисел от $1$ до $212$ три различных числа так, чтобы их сумма делилась на $3$

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

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

От чего зависит, делится ли сумма на $3$ Попробуй разложить карточки на три кучки. В модели выбирай тройки карточек и включай раскраску по остаткам. Ниже можно сверить ответ — число способов.

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

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

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

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

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

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

Карточки и остатки

Когда сумма трёх чисел делится на 3?

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

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

Если модель не открылась, попробуй так. Выпиши числа от 1 до 9 в три столбика: 1, 4, 7 / 2, 5, 8 / 3, 6, 9. Выбирай тройки и складывай. Из каких столбиков берутся тройки с суммой, кратной 3?

Подсказка 1

Делимость суммы на $3$ зависит только от остатков слагаемых при делении на $3$ Разложи числа от $1$ до $300$ на три группы по остаткам $0$ $1$ $2$ — в каждой по $100$ чисел.

Подсказка 2

Сумма трёх остатков делится на $3$ ровно тогда, когда остатки все одинаковые ( $0+0+0$ $1+1+1$ $2+2+2$ ) или все разные ( $0+1+2$ ). Посчитай тройки каждого вида.

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

Важны только остатки

Остаток суммы при делении на $3$ равен остатку суммы остатков. Поэтому разложим числа от $1$ до $300$ на три группы: с остатком $0$ ( $3, 6, \ldots, 300$ ), с остатком $1$ ( $1, 4, \ldots, 298$ ) и с остатком $2$ ( $2, 5, \ldots, 299$ ). В каждой группе по $100$ чисел.

Какие наборы остатков подходят

Переберём наборы из трёх остатков (порядок не важен). Сумма делится на $3$ в четырёх случаях:

0 + 0 + 0,\quad 1 + 1 + 1 = 3,\quad 2 + 2 + 2 = 6,\quad 0 + 1 + 2 = 3.

Остальные наборы не подходят: например, $0 + 0 + 1 = 1$ $0 + 1 + 1 = 2$ $1 + 1 + 2 = 4$ $0 + 2 + 2 = 4$ $1 + 2 + 2 = 5$ $0 + 0 + 2 = 2$

Считаем тройки

Три карточки из одной группы по $100$ можно выбрать $C_{100}^3 = \dfrac{100 \cdot 99 \cdot 98}{6} = 161\,700$ способами, групп три. По одной карточке из каждой группы — $100 \cdot 100 \cdot 100 = 1\,000\,000$ способов. Всего

3 \cdot 161\,700 + 1\,000\,000 = 1\,485\,100.

Те же тройки в 10 и 11 классе

В 11 классе спрашивают о трёх различных числах от $1$ до $N$ — это в точности те же тройки. В 10 классе с доски стирают три числа так, чтобы остаток суммы оставшихся чисел при делении на $3$ не изменился: новая сумма равна старой минус сумма стёртых, поэтому остаток не меняется ровно тогда, когда сумма стёртых делится на $3$

Меняется только $N$ и группы становятся разными. Например, при $N = 301$ в группе с остатком $1$ на одно число больше: $101$ а в двух других по $100$ Тогда

C_{100}^3 + C_{101}^3 + C_{100}^3 + 100 \cdot 101 \cdot 100 = 161\,700 + 166\,650 + 161\,700 + 1\,010\,000 = 1\,500\,050.

При $N = 302$ по $101$ числу в группах с остатками $1$ и $2$ $C_{100}^3 + 2C_{101}^3 + 100 \cdot 101^2 = 1\,515\,100$ .

Проверка

Формула $C_a^3 + C_b^3 + C_c^3 + abc$ (где $a$ $b$ $c$ — размеры групп остатков) совпадает с полным перебором всех троек для $N$ от $3$ до $40$ — это проверяет тест модели. Ответы всех двенадцати официальных версий: $N = 300, 270, 240, 210$ (9 класс) — $1\,485\,100$ $1\,081\,440$ $758\,480$ $507\,220$ $N = 301, 271, 241, 211$ (10 класс) — $1\,500\,050$ $1\,093\,545$ $768\,040$ $514\,535$ $N = 302, 272, 242, 212$ (11 класс) — $1\,515\,100$ $1\,105\,740$ $777\,680$ $521\,920$

Ответ

$1\,485\,100$ (для $N = 300$ ответы других версий — в проверке).

Ответ

$1\,485\,100$ (для $N = 300$ ответы других версий — в проверке).

Главная идея

Сумма делится на 3 ровно тогда, когда остатки трёх чисел все одинаковые или все разные; дальше — сочетания внутри групп остатков и произведение их размеров.

«Сумма кратна 3» при выборе из подряд идущих чисел — раскладываем числа по остаткам и перебираем наборы остатков.

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

Считать упорядоченные тройки (в 6 раз больше); забыть случай «все остатки разные»; при N, не кратном 3, взять одинаковые размеры групп.

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

Олимпиада «Физтех» · математика · 9 класс · 2024/25 · отборочный этап, первый тур (1 попытка). Задача 5, версия с ID 3552 — первая в официальном файле; другие версии этого номера (ID 3555, 3554, 3553) можно выбрать в модели. Та же задача с другими числами и формулировкой: 10 класс, первый тур, задача 5 (ID 3582, 3600, 3601, 3602); 11 класс, первый тур, задача 4 (ID 3627, 3640, 3641, 3642) — разобрана здесь же, все её версии тоже есть в модели.

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

Условие — из официального файла организатора. Подсказки, решение и модель — Popov Academy. Авторское решение записано до знакомства с решениями организатора; затем ответ совпадает с ответом организатора («Решения М9 1 попытка 2024», стр. 5 (9 класс); 10 класс и 11 класс — свои файлы ответов первого тура ↗: 9 класс: ID 3552 — 1 485 100; ID 3555 — 1 081 440; ID 3554 — 758 480; ID 3553 — 507 220. 10 класс (задача 5): ID 3582 — 1 500 050; ID 3600 — 1 093 545; ID 3601 — 768 040; ID 3602 — 514 535. 11 класс (задача 4): ID 3627 — 1 515 100; ID 3640 — 1 105 740; ID 3641 — 777 680; ID 3642 — 521 920.). Сверены все четыре официальные версии этого номера.

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

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

Подсчёт вариантов · Нужна школьная база

Остатки при делении на 3
Число сочетаний C(n, 3)
Правило произведения

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

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