Тема КОМБИНАТОРИКА

Логика .01 Строим пример

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела комбинаторика
Решаем задачи

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

Задача 21#134306Максимум баллов за задание: 7

Петя написал на доске десять натуральных чисел, среди которых нет двух равных. Известно, что из этих десяти чисел можно выбрать три числа, делящихся на 5. Также известно, что из написанных десяти чисел можно выбрать четыре числа, делящихся на 4. Может ли сумма всех написанных на доске чисел быть меньше 75?

Источники: ВСОШ, РЭ, 2022, 9.1, 10.1 и 11.1 (см. olympiads.mccme.ru)

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

Подсказка 1:

Попробуйте придумать пример таких чисел.

Подсказка 2:

Добавьте в набор число 20. Оно одновременно делится на 4 и на 5. Осталось взять два маленьких числа, кратных 5, и три числа, кратных 4.

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

Пример: 1,  2,  3,  4,  5,  6,  8,  10,  12,  20.  В этом наборе три числа (5,10,20)  делятся на 5, четыре числа (4,8,12,20)  делятся на 4, а общая сумма равна 71.

Ответ:

может

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

Задача 22#137302Максимум баллов за задание: 7

На доске написаны 11 целых чисел (не обязательно различных). Может ли оказаться, что произведение любых пяти из них больше, чем произведение остальных шести?

Источники: ВСОШ, ЗЭ, 2022, 10.5 и 11.5 (см. olympiads.mccme.ru)

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

Подсказка 1:

Попробуйте придумать пример.

Подсказка 2:

Для упрощения можно сделать большую часть чисел одинаковыми.

Подсказка 3:

Не забывайте про знак, разные знаки у чисел в примере могут помочь добиться требуемого.

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

Пусть одно из чисел равно 10,  а каждое из остальных равно − 1.  Тогда произведение любых пяти из них больше, чем произведение остальных шести. Действительно, если число 10 входит в произведение пяти чисел, то это произведение равно 10, а произведение оставшихся шести чисел равно 1,  и 10> 1.  Если же число 10 не входит в произведение пяти чисел, то это произведение равно − 1,  а произведение оставшихся шести чисел равно − 10,  и − 1> −10.

Ответ:

может

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

Задача 23#38622Максимум баллов за задание: 7

Можно ли так раскрасить все натуральные числа в красный и синий цвета, чтобы любые два числа, отличающиеся на 5, были разных цветов, и любые два числа, отличающиеся в два раза, были разных цветов? В ответ укажите “да” или “нет”.

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

Подсказка 1

Ну просто беее, а не задача. Раскрасить, да еще и все(!) натуральные числа. Да уж… Это ведь какой-то общий алгоритм надо придумывать, а потом еще и доказывать, что все числа будут использованы при таком алгоритме раскраски. Мда, ну и задача. Но это если думать, что ответ - «ДА», а вот если он противоположный, то можно, основываясь на условии задачи, найти контрпример и «дело в шляпе». Попробуйте это сделать!

Подсказка 2

Видимо нам нужно получить контрпример с тем, что число n будет и красным и синим одновременно, в условии того, что что - то известно про числа, которые связаны с данным(а именно отличаются от него на 5 или в два раза). Ну пусть числа n/2 и n-5. А вот если бы эти числа отличались на 5, то мы бы пришли к противоречию. А такое может быть?

Подсказка 3

Ну конечно, может. К примеру, если n=20. Тогда, с одной стороны, 20 имеет не совпадающий с 10 цвет, а с другой - не совпадающий с 15. Но при этом - 15 и 10 сами разных цветов, потому цвет 20 не совпадает с обоими цветами, которые у нас есть. Пришли к противоречию!

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

Рассмотрим числа 10  и 15  . Они должны быть разных цветов. Посмотрим теперь на число 20  . С одной стороны оно должно быть цвета, отличного от цвета 10  , а с другой — не такого же цвета как и 15  . Но такого быть не может так как цветов всего два — противоречие.

Ответ: нет

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

Задача 24#47039Максимум баллов за задание: 7

На каком из пяти интервалов, на которые разбивают числовую ось четыре точки

 5  8   3   6
x < y <y < x ,

лежит число 0?

Источники: Ломоносов-2018, 11.1 (см. olymp.msu.ru)

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

Подсказка 1

Хочется для начала разобраться со знаком (и даже интервалом значений) какой-то из переменных. Какое неравенство для этого лучше всего взять из условия?

Подсказка 2

Верно, это y⁸<y³, откуда несложно понять, что y∈(0;1). Вы можете попробовать взять неравенство для пятой и шестой степени x, но там конкретики не получится. Что же делать с x?

Подсказка 3

Просто разберите 2 случая: x<0 и x>0. Тогда, посмотрев на знаки неравенств, можно сделать выводы и решить задачу!

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

Из неравенства для y  получаем, что

 3   8      3    5
y > y ⇐ ⇒  y(1− y )>0 ⇒ y ∈ (0, 1)

Далее всё зависит от знака x.

Если x> 0,  тогда т.к. x6 > y3 > x5,  x> 1  и y > 1.  Но при таком условии y8 > y3,  так что этот случай невозможен.

Если x< 0,  то ответом может быть только (x5, y8).  Осталось привести пример, вполне подойдёт x= −1, y = 1.
         2

Ответ:

 (x5, y8)

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

Задача 25#95759Максимум баллов за задание: 7

Автобусы привезли на турнир 72  участника. В автобусах они сидели парами, и ровно в половине пар участники были знакомы. Докажите, что в столовой их можно рассадить за столы так, чтобы не менее чем за 18  столами нашелся участник, у которого за столом знакомых и незнакомых поровну. Количества участников за разными столами могут отличаться, одному за стол садиться нельзя.

Источники: Лига открытий - 2018

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

Разобьем всех сначала на четвёрки: пара знакомых (скажем, Петя с Васей) и пара незнакомых (скажем, Оля с Полей). Если Оля с Петей знакомы, посадим за стол тройку Петя, Оля и Поля: у Оли будет знакомых и незнакомых поровну. Если Оля с Петей незнакомы, посадим за стол тройку Петя, Вася и Оля: у Пети будет знакомых и не знакомых поровну. Так мы всех детей разобьем на 18  четверок; из каждой четверки выделим троих и посадим за один стол. Эти 18  столов будут удовлетворять условию, а оставшихся 18  детей мы всех усадим за один стол.

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

Задача 26#95762Максимум баллов за задание: 7

Буратино написал 25  чисел. Оказалось, что какие бы три из них ни выбрать, среди оставшихся найдется такое четвертое число, что сумма этих четырех чисел будет положительна. Обязательно ли сумма всех 25  чисел, написанных Буратино, положительна?

Источники: Лига открытий - 2018

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

Предположим, что Буратино написал такие числа: − 1,− 2  , ...,−24  и число 100.  Тогда сумма 100  и любых трех других чисел положительна, так что условие задачи выполнено, в то время, как сумма всех 25  чисел отрицательна.

Ответ:

Нет

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

Задача 27#95905Максимум баллов за задание: 7

Расставьте цифры 1,2,3,...,9  по кругу так, чтобы любое трехзначное число, образованное тремя подряд идущими цифрами по часовой стрелке, делилось на свою последнюю цифру. Каждую цифру нужно использовать ровно один раз.

Источники: Лига открытий - 2018

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

Подходит, к примеру, расстановка 1,9,2,4,3,5,7,6,8.

______________________________________________________________________________________________________________________________________________________

Замечание. В любом примере цифры 3,6  и 9  должны стоять через две.

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

Задача 28#95909Максимум баллов за задание: 7

Палиндромом называется число, которое одинаково читается слева направо и справа налево (например, 313  или 22).  Может ли сумма двух трехзначных палиндромов равняться четырехзначному палиндрому?

Источники: Лига открытий - 2018

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

Например, 999+ 222= 1221.

Ответ:

Да, может

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

Задача 29#96048Максимум баллов за задание: 7

Существуют ли два различных натуральных числа таких, что если каждое из них умножить на свою сумму цифр, то получатся равные числа?

Источники: Лига открытий - 2018

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

Например, подходят числа 105  и 210.

Ответ:

Да, существует

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

Задача 30#96051Максимум баллов за задание: 7

На столе стоит башенка из трех абсолютно одинаковых кубиков, на гранях которых расставлены цифры от 1  до 6.  Кубики повернуты так, что если прочитать сверху вниз число спереди, то видно 131,  сзади — 464,  а слева — 253.  Какое число видно справа?

Источники: Лига открытий - 2018

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

Так как спереди видно 131,  а сзади — 464,  то на противоположных гранях кубика находятся 1  и 4,  а также 3  и 6.  Оставшиеся два числа, 2  и 5,  тогда также находятся на противоположных гранях. И поэтому раз слева написано 253,  то справа — 526.

Ответ:

 526

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

Задача 31#96285Максимум баллов за задание: 7

Можно ли отметить некоторые клетки квадрата 11× 11  так, чтобы квадратиков 2× 2,  содержащих по 0,1,2,3  или 4  отмеченные клетки, было поровну?

Источники: Лига открытий - 2018

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

Пример приведён на рисунке.

PIC

Ответ:

Да, можно

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

Задача 32#98454Максимум баллов за задание: 7

На доске написаны через пробел числа 1,2,3,...,10  в указанном порядке. Можно ли расставить между числами знаки сложения, умножения и скобки так, чтобы результат делился на  5
5 ?

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

Подходит пример 1⋅(2+3 +4⋅5⋅6)⋅(7 +8)⋅9⋅10.

Ответ:

Да, можно

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

Задача 33#99837Максимум баллов за задание: 7

У учительницы есть 50  палочек с длинами от 1  см до 50  см. Она раздает по две палочки 25  мальчикам. При этом мальчик становится счастливым, если длины его палочек отличаются более чем в два раза. Может ли учительница сделать всех мальчиков счастливыми?

Источники: Лига открытий - 2018

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

Палочки с длинами от 25  см до 50  см должны быть более длинными, чтобы выполнялось условие. Но 26  палочек не могут быть более длинными в своей паре.

Ответ:

Нет, не сможет

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

Задача 34#99955Максимум баллов за задание: 7

На доску выписаны через пробел числа 0,1,2,...,99.  Вначале учительница подчеркивает одно число. После этого Вовочка подчеркивает еще 18  чисел. Если в итоге получится, что подчеркнутые числа идут в порядке возрастания суммы цифр, то учительница ставит Вовочке пятерку, иначе — двойку. Может ли учительница помешать Вовочке получить пятерку?

Источники: Лига открытий - 2018

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

Пусть учительница подчеркнула число ab.  Тогда подойдет последовательность 0,10,...,a0,a1,...,a9,(a-+1)9,...,99.

Ответ:

Нет, не сможет

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

Задача 35#92485Максимум баллов за задание: 7

Назовем словом любую последовательность букв русского алфавита, не обязательно осмысленную. Придумайте два слова разной длины таких, что существует ровно 210  способов переставить в них буквы. Первоначальное слово также считается перестановкой.

Источники: Лига открытий - 2017

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

В качестве первого слова подходит слово из одной буквы “a” и 209  букв “б”.

В качестве второго слова возьмем “аааббвв”. Количество перестановок его букв равно -7!--
3!⋅2!⋅2! = 210.

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

Задача 36#92662Максимум баллов за задание: 7

Можно ли разрезать квадрат тремя прямыми так, чтобы получилось ровно три треугольника и четыре четырёхугольника?

Источники: Лига открытий - 2017

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

В квадрате ABCD  проведем диагональ BD,  также проведем прямую, параллельную AD,  а через C  и точку P  на прямой AD   — прямую CP.  Получится требуемая картинка, если прямая, параллельная AD,  пройдет ниже точки пересечения диагонали BD  и CP.

Ответ:

Можно

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

Задача 37#92719Максимум баллов за задание: 7

Число n,  большее 4,  делится на 4.  Докажите, что найдутся хотя бы 4  правильные несократимые дроби со знаменателем n.

Источники: Лига открытий - 2017

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

Обозначим n= 4k.  Во-первых, дроби 1-
4k  и 4k−1-
 4k  подходят под условие, то есть надо найти еще две. Ими являются дроби 2k−1-
 4k  и 2k+1
 4k .  Действительно, эти дроби отличны от первых двух, так как k≥ 2,  и не сократимы, так как если бы какую-то дробь можно было сократить на p,  то и 4k,  и 4k± 2  делилось бы на p,  что возможно только при p= 2,  но число 2k± 1  нечетно.

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

Задача 38#92875Максимум баллов за задание: 7

Палиндромом называется натуральное число, которое читается одинаково слева направо и справа налево. Докажите, что для любой натуральной степени двойки найдётся натуральный палиндром, который на неё делится.

Источники: Лига открытий - 2017

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

Подойдет число x⋅10n +2n,  где x  — запись числа 2n  в обратном порядке.

Ответ:

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

Задача 39#93369Максимум баллов за задание: 7

У Пети есть 27  одинаковых кубиков. Он покрасил каждую грань каждого кубика в один из трех цветов. Может ли оказаться, что для каждого из трех цветов можно составить одноцветный куб 3× 3× 3  этого цвета?

Источники: Лига открытий - 2017

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

Обозначим раскраску кубика (x,y,z),  если x  граней окрашено в первый цвет, y  граней во второй цвет и z  граней в третий цвет. При этом если граней одного цвета две или три, то будем считать, что они все прилегают к одной вершине. Возьмем по одному кубику (3,3,0),(3,0,3)  и (0,3,3),  по шесть кубиков (3,2,1),(1,3,2)  и (2,1,3)  и шесть кубиков (2,2,2).  Тогда для каждого цвета есть 8  кубиков с тремя гранями, 12  кубиков с двумя гранями и 6  кубиков с одной гранью данного цвета, и из них легко сложить одноцветный кубик 3× 3× 3,  расположив кубики с тремя гранями в вершинах, 12  кубиков с двумя гранями — в серединах ребер, а оставшиеся  6  кубиков с одной гранью — в серединах граней.

Ответ:

Может

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

Задача 40#93716Максимум баллов за задание: 7

В клетчатом квадрате 3× 3  отметили все вершины клеток. Разрежьте его на девять треугольников с вершинами в отмеченных точках: три тупоугольных, три прямоугольных и три остроугольных.

Источники: Лига открытий - 2017

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

Пример приведен на рисунке.

PIC

Рулетка
Вы можете получить скидку в рулетке!