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

Условие

Дано множество чисел $M = \{2024, 2025, \ldots, 2031\}$ . Для каждого непустого подмножества множества $M$ (включая само множество $M$ ) вычислили сумму чисел, входящих в это подмножество, а затем все эти суммы сложили, получив число $S$ На какое двузначное число заканчивается $S$

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

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

Выписать все $255$ подмножеств долго. Посчитай по-другому: сколько раз каждое число из $M$ попадает в $S$ В модели посмотри полную таблицу для двух, трёх, четырёх чисел. Ниже можно сверить ответ — две последние цифры $S$

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

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

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

Самостоятельное исследованиеПодмножества

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

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

Подмножества

Сколько раз каждое число попадает в сумму всех сумм?

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

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

Если модель не открылась, попробуй так. Выпиши все непустые подмножества множества {1, 2, 3}, их суммы и сложи. Сколько раз встретилось число 1? А в множестве {1, 2, 3, 4}?

Подсказка 1

Посчитай не суммы подмножеств, а вклад каждого числа: число $2024$ входит в $S$ столько раз, сколько есть подмножеств, его содержащих.

Подсказка 2

Подмножество, содержащее $2024$ определяется выбором остальных чисел: каждое из $7$ остальных либо берём, либо нет — $2^7 = 128$ вариантов. Значит, $S = 128 \cdot (2024 + 2025 + \ldots + 2031)$ .

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

Сколько раз считается каждое число

Сумма $S$ складывается из чисел множества, и каждое число $x \in M$ входит в неё столько раз, в скольких подмножествах оно лежит. Подмножество, содержащее $x$ задаётся выбором остальных семи чисел: каждое берём или не берём, $2^7 = 128$ вариантов. Пустое подмножество в $S$ не входит, но и вклад его был бы нулевым.

Значит, $S = 128 \cdot (2024 + 2025 + \ldots + 2031)$ .

Сумма множества

$2024 + 2025 + \ldots + 2031 = 8 \cdot 2024 + (0 + 1 + \ldots + 7) = 16\,192 + 28 = 16\,220.$

Последние две цифры

$S = 128 \cdot 16\,220 = 2\,076\,160$ . Последние две цифры произведения зависят только от последних двух цифр множителей: $28 \cdot 20 = 560$ то есть $S$ оканчивается на $60$

Проверка

Прямой перебор всех $255$ непустых подмножеств (тест модели) даёт $S = 2\,076\,160$ Проверка формулы на маленьком множестве $\{1, 2, 3\}$ подмножества $\{1\}$ $\{2\}$ $\{3\}$ $\{1,2\}$ $\{1,3\}$ $\{2,3\}$ $\{1,2,3\}$ суммы $1 + 2 + 3 + 3 + 4 + 5 + 6 = 24 = 2^2 \cdot 6$ . Другие версии: $128 \cdot (8 \cdot 3182 + 28) = 128 \cdot 25\,484 = 3\,261\,952$ — $52$ $128 \cdot 42\,244 = 5\,407\,232$ — $32$ $128 \cdot 58\,828 = 7\,529\,984$ — $84$

Ответ

$60$

Ответ

$60$

Главная идея

Каждое число множества лежит ровно в 2⁷ = 128 подмножествах, поэтому S = 128 · (сумма чисел множества).

Сумма по всем подмножествам — считать вклад каждого элемента: он лежит в половине всех подмножеств.

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

Считать, что каждое число входит в 2⁸ или 2⁸ − 1 подмножеств; пытаться выписывать подмножества; ошибиться в сумме 0 + 1 + … + 7.

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

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

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

Условие — из официального файла организатора. Подсказки, решение и модель — Popov Academy. Авторское решение записано до знакомства с решениями организатора; затем ответ совпадает с ответом организатора («Решения М9 2 попытка», стр. 9 ↗: ID 3898: 60; ID 3901: 52; ID 3900: 32; ID 3899: 84.). Сверены все четыре официальные версии этого номера.

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

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

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

Число подмножеств множества
Последние цифры произведения

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

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