Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Комбинаторика на Межведе: способы, игры, клетки и плитки

Тема Межвед (на базе ведомственных образовательных организаций)

Комбинаторика на Межведе: способы, игры, клетки и плитки

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела межвед (на базе ведомственных образовательных организаций)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#68096

На листе клетчатой бумаги с размером клетки $1×1$ изображен прямоугольник. Прямоугольник разбит прямыми, параллельными его сторонам на некоторое количество маленьких прямоугольников. У каждого маленького прямоугольника длины сторон выражаются целыми числами, при этом длина хотя бы одной его стороны чётна. Докажите, что длина хотя бы одной стороны исходного прямоугольника также является чётным числом.

Источники: Межвед-2023, 11.4 (см. www.academy.fsb.ru)

Подсказки к задаче

Подсказка 1

Подумайте про площадь этого прямоугольника. Он ведь у нас разбит на маленькие прямоугольнички, у которого стороны целые, и одна из них четная....

Подсказка 2

Площадь маленьких прямоугольников - чётная, значит, и большого - чётная)

Показать доказательство

Заметим, что площадь прямоугольника равна сумме площадей прямоугольников разбиения. Так как у каждого маленького прямоугольника длины сторон выражаются целыми числами, при этом длина хотя бы одной его стороны чётна, то эта площадь четна. Тогда длина хотя бы одной стороны исходного прямоугольника также является чётным числом (иначе площадь была бы нечетной).

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#39874

Есть $101$ клетка. Двое поочередно слева направо вписывают в эти клеточки по одной из цифр от $0$ до $9$ . Если после заполнения всех клеток сумма всех записанных цифр будет делиться на $11$ , то выиграет игрок, ходивший первым, а если не будет делиться на $11$ — то вторым. Какой из игроков выиграет при правильной своей игре и любой игре соперника? Ответ обосновать.

Источники: Межвед-2022, 11.1 (см. www.academy.fsb.ru)

Подсказки к задаче

Подсказка 1!

1) Итак, у нас ребята заполняют клетки по очереди числами, значит было здорово использовать стратегию дополнения!

Подсказка 2!

2) Да, можно всегда дополнять сумму до 9, так как цифры от 0 до 9. Попробуем играть так за второго, что у нас выйдет?

Подсказка 3!

3) Что в конце первый всегда будет ставить любое число и выиграет! Тогда попробуем играть за первого, и "передать ход" второму. То есть первый ставит какой-то х, а дальше дополняет сумму до 9. Как ему надо ходить, чтобы выиграть...?

Показать ответ и решение

Заметим, что первый игрок всегда может дописывать к предыдущему числу второго такое, что их сумма равна девяти. Тогда в парах $(2,3)...(100,101)$ сумма будет равна девяти, откуда вся сумма в клетках $2,3...101$ равна $50⋅9= 450 ≡11− 1$ . Выберем цифру в первой клетке, равной $1$ и вся сумма будет кратна $11$ при любой игре второго.

Ответ:

Первый

Ошибка.
Попробуйте повторить позже

Задача 3#95206

У Олега есть $1000$ рублей, и он хочет подарить маме на $8$ Марта тюльпаны, причем непременно их должно быть нечётное число, и ни один оттенок цвета не должен повторяться. В магазине, куда пришел Олег, один тюльпан стоит $49$ рублей, и есть в наличии цветы двадцати оттенков. Сколько существует способов у Олега подарить маме цветы?

Источники: Межвед - 2021, 11.1 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

Какое максимальное число цветков можно купить? Если бы нам не пришлось следить за чётностью количества, сколько букетиков мы смогли бы собрать?

Подсказка 2

Каждый оттенок мы могли бы или взять, или не взять, сколько тогда букетиков собралось бы (без учета чётности)?

Подсказка 3

Верно, 2^20. Но что делать с букетиками, в которых чётное количество оттенков? Было бы хорошо, если бы мы смогли добавлять цветки туда, где нужно подправить чётность количества. Но ведь у нас тогда будут повторы, нам бы еще один оттенок... или можно изначально собирать букеты иначе? ;)

Показать ответ и решение

Из условия очевидно, что максимальное количество цветов в букете — $20.$ Рассмотрим $19$ цветов $19$ различных оттенков. Собрать букет из этих цветов без учёта чётности можно $19 2$ способами. Если в букете нечётное количество цветов, то мы его оставляем, если же чётное — добавляем неиспользованный двадцатый цветок. Таким образом, общее количество способов собрать букет равно $19 2$ .