Комбинаторика и комбигео на ФЕ —Каталог задач по Олимпиадной математике

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

Тема Формула Единства

Комбинаторика и комбигео на ФЕ

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

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

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

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

Подтемы раздела формула единства

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

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

Задача 1#85913

Вредный учитель даёт ученикам тест из 12 вопросов, на каждый из которых надо ответить «да» или «нет». Учитель не только вредный, но и нечестный, поэтому «правильные» ответы он определяет только после того, как ученики сдадут работы. При этом учитель стремится выбрать «правильные» ответы так, чтобы ни один из учеников не угадал больше половины ответов. При каком наибольшем количестве учеников учитель гарантированно сумеет это сделать?

Источники: ФЕ - 2024, 11.5 (см. www.formulo.org)

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

Если учеников три (или меньше), то учитель справится. Действительно, на первые два вопроса возможны 4 варианта ответа: ++, +-, –, -+. Поскольку учеников не больше трёх, то какую-то из этих комбинаций никто не выбрал, её-то учитель и объявляет «правильной». Так же он поступает с каждой следующей парой ответов. В результате у каждого ребёнка не больше половины верных ответов.

Четыре ученика смогут «обыграть» учителя. Для этого им надо разделить вопросы на две группы нечётного размера (например, первые 5 и последние 7 вопросов) и дать такие ответы: ++++++++++++,————, +++++——-,—–+++++++. Тогда найдётся ребёнок, угадавший больше половины ответов как в первой группе, так и во второй.

Ответ: 4

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

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

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

Задача 2#85912

У Вити есть 9 альбомов с марками, причём в любых двух альбомах количество марок различается. Витя хочет отдать сестре один или два пустых альбома на её выбор. При этом Витя обнаружил, что, какой бы один или какие бы два альбома ни попросила сестра, марки из них можно распределить по остальным альбомам так, что во всех оставшихся семи или восьми альбомах станет поровну марок. Изначально у Вити меньше всего марок в красном альбоме. А какое минимальное количество марок может быть в синем альбоме?

Источники: ФЕ - 2024, 11.4 (см. www.formulo.org)

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

Посмотрим, какое минимальное количество марок может изначально быть у Вити в красном альбоме.

_________________________________________________________________________________________________________________________________________________________________________________

Оценка: Упорядочим альбомы по количеству марок, начиная с наименьшего. Если во втором по количеству альбоме $x$ марок, то в следующих не менее чем $x+ 1,x+$ $2,...,x+ 7$ . После расформирования первого альбома в каждом из остальных будет не менее $x+7$ марок, то есть в них надо добавить не менее чем $7+ 6+ ...+ 2+1 +0 =28$ марок.

Пример: 28, 35, 36, ..., 42. Суммарное количество марок тут делится на 7 и на 8 ( $336=$ $42⋅8= 48⋅7$ ), поэтому можно сделать как 8 альбомов по 42 марки, так и 7 по 48 марок.

_________________________________________________________________________________________________________________________________________________________________________________

Итак, тогда общее число марок не меньше $28 +29+ ...+ 36$ , к тому же кратно 7 и 8 , а потому не меньше $336= 28+35+ 36+ ...+ 42$ . Если в этой сумме заменить $28+35$ на $31+32$ , то получим пример к ответу 32.

Предположим теперь, что в синем альбоме 31 марка или меньше. Тогда в красном не более 30 марок. В то же время общее количество марок равно $8a$ , где $a≥42$ . После расформирования красного альбома в остальных нужно сделать ровно по $a$ марок. Значит, изначально в каждом альбоме не более $a$ марок. В синий альбом придётся добавить не менее $42− 31= 11$ марок, а в остальные суммарно не менее чем $6+ 5+ 4+3 +2+ 1+ 0= 21$ марку. Однако в сумме это не менее 32 марок, а в красном альбоме лишь 30.

Ответ: 32

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

Задача 3#85910

Лес представляет собой координатную плоскость, в некоторых узлах которой растут ёлки. Всего ёлок больше миллиона. Докажите, что можно срубить более 100000 ёлок так, чтобы расстояние между любыми двумя срубленными ёлками было больше 3. (Узлом называется точка, обе координаты которой целые; ёлки считаем точками.)

Источники: ФЕ - 2024, 11.2 (см. www.formulo.org)

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

Раскрасим узлы в 10 цветов так, чтобы узлы одного цвета образовывали сетку из квадратов со стороной $√10$ . Например, пусть цвет узла с координатами ( $x,y$ ) определяется остатком от деления числа $x+ 3y$ на 10 (считаем, что деревья растут в центрах квадратов):


0	1	2	3	4	5	6	7	8	9	0

7	8	9	0	1	2	3	4	5	6	7

4	5	6	7	8	9	0	1	2	3	4

1	2	3	4	5	6	7	8	9	0	1

8	9	0	1	2	3	4	5	6	7	8

5	6	7	8	9	0	1	2	3	4	5

2	3	4	5	6	7	8	9	0	1	2

9	0	1	2	3	4	5	6	7	8	9

6	7	8	9	0	1	2	3	4	5	6
3	4	5	6	7	8	9	0	1	2	3

0	1	2	3	4	5	6	7	8	9	0

По принципу Дирихле, в какой-то из десяти цветов окрасились более 100 тысяч ёлок. Тогда все эти ёлки можно срубить, поскольку расстояние между любыми двумя из них не меньше $√10$ .

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

Задача 4#74787

Маша нарисовала на клетчатой бумаге по линиям сетки квадрат $n ×n$ клеток, где $n−$ чётное число. В некоторых клетках она провела диагонали, соблюдая два правила: - нельзя проводить две диагонали в одной клетке; - нельзя проводить две диагонали с общим концом.

Какое наименьшее число пустых клеток могло остаться на Машином рисунке?

Источники: ФЕ-2022, 11.4 (см. www.formulo.org)

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

Подсказка 1

Очень часто в задачах на оценку и пример бывает полезно разбить доску на фигуры, в которых удобнее делать оценку. Заметим, что в каждом узле не может «встретиться» более одной диагонали.

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

Оценка. Разобьём квадрат $n× n$ на $n∕2$ горизонтальных прямоугольников $2×n$ . Докажем, что в каждом из них Маша может провести не более $n+ 1$ отрезка, соблюдая условие задачи. Для каждого такого прямоугольника отметим все узлы сетки, лежащие на средней линии (см. рисунок снизу для $n= 8$ ).

$PIC$

В каждом прямоугольнике таких точек $n+ 1$ . Очевидно, любой Машин отрезок задействует не менее одной отмеченной точки. Значит, Маша в каждом таком прямоугольнике сможет провести не более $n+ 1$ отрезков. Таким образом, во всём квадрате $n ×n$ она проведёт не более $(n +1)⋅n∕2$ отрезков. Тогда количество пустых клеток не меньше $n2− n(n+21)= n(n2−1)$ .