Тема Применение классических комбинаторных методов к разным задачам

Чётность

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

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

Задача 1#122420

На столе в ряд стоит 40  чашек, занумерованных слева направо числами от 1  до 40.  В каждой чашке лежит не более 10  вишен, а количество вишен в любых соседних чашках отличается ровно на один. В чашках с номерами 1,4,7,10,...,40  вместе 125  вишен. Какое наибольшее количество вишен может быть во всех чашках?

Источники: СПбГУ - 2025, 11.1(см. olympiada.spbu.ru)

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

Подсказка 1

Количество ягод в соседних чашках отличается на 1. Стало быть, чётность тоже отличается...

Подсказка 2

Какое наибольшее количество может быть в двух соседних чашках, учитывая чётность?

Подсказка 3

Мы знаем суммарное количество ягод в чашках 1, 4, 7, ..., 40. А можно ли оценить количество ягод в остальных чашках, используя предыдущие подсказки?

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

Заметим, что для каждой пары соседних чашек в одной четное число вишен, а в другой — нечетное. Тогда в них вместе нечетное, не превосходящее 20,  число вишен. Значит, в каждой паре соседних чашек не более 19  вишен. Тогда в каждой из пар 2− 3,5− 6,8− 9,...,38− 39  не более 19  вишен, а во всех этих парах вместе не более 19⋅13=247  вишен. Тогда всего в чашках не более 247+ 125 =372  вишен.

Приведем пример размещения 372  ягод. В чашки с нечетными номерами положим по 9  вишен, а в чашки с четными номерами по   10  вишен. Всего получится 380  вишен. Далее съедим по две вишни из чашек с номерами 4,10,16  и 22.  Останется 372  вишни.

Ответ:

 372

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

Задача 2#128245

У племени семпоальтеков было 24  слитка золота, 26  редких жемчужин и 25  стеклянных бус. У Кортеса они могут обменять слиток золота и жемчужину на одни бусы, у Монтесумы — один слиток и одни бусы на одну жемчужину, а у тотонаков — одну жемчужину и одни бусы на один золотой слиток. После долгих обменов у семпоальтеков осталось только одна вещь. Какая?

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

Пусть у племени было x  слитков золота, y  жемчужин и z  бус. Если семпоальтеки один раз обменяются с Кортесом, у них будет следующая тройка количеств предметов: x− 1,  y − 1,  z+ 1.  Если они обменяются с Монтесумой, будет тройка x − 1,  y+ 1,  z− 1.  Если они обменяются с тотонаками, будет тройка x+ 1,  y− 1,  z− 1.  Заметим, что при каждом обмене у всех количеств предметов меняется четность, а общее количество предметов уменьшается на 1. Всего предметов было 24+ 26+25 =75.

Обмены производились, пока у племени не осталась последняя вещь. Тогда всего обменов было произведено 74. Следовательно, четность всех количеств предметов осталась исходной. Два вида предметов должны отсутствовать у племени, то есть, их количества равны 0, это будут слитки золота и жемчужины, так как в самом начале их было 24 и 26 соответственно. Получается, что у племени останутся стеклянные бусы.

Ответ:

Стеклянные бусы

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

Задача 3#128448

Роза раскладывает по одной монете в каждую клетку таблицы 2023 ×2023  орлом вверх. Ход состоит в том, чтобы выбрать монету и перевернуть все монеты, находящиеся рядом с выбранной. Например, если выбрана центральная монета, тогда четыре монеты в ячейках сверху, снизу, слева и справа от него переворачивались бы. Возможно ли, что после серии ходов все монеты окажутся орлом вниз?

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

Подсказка 1:

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

Подсказка 2:

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

Подсказка 3:

Как насчет того, чтобы рассмотреть главную диагональ? Ведь на неё влияют только клетки соседних диагоналей.

Подсказка 4:

Тут стоит рассуждать в лоб. Пусть клетки диагонали, примыкающей к главной сверху, были выбраны для хода соотвественно x₁, x₂, ..., x₂₀₂₂ раз. Аналогичные обозначения введём для нижней диагонали, но с переменной y. Посчитайте количество переворотов монеты на каждой клетке главной диагонали и поработайте с их чётностью.

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

Предположим, что так могло произойти. Рассмотрим монеты на главной диагонали. Заметим, что на них могли повлиять только монеты с соседних диагоналей, будем называть их верней и нижней диагоналями. Тогда пусть мы выбирали первую монету на верхней диагонали    x1  раз, вторую — x2,  и так далее до x2022.  Аналогично для нижней диагонали введём y1,...,y2022.  Все клетки главной диагонали попали под действие ходов нечётное число раз. Тогда для первой клетки получаем x1+ y1  нечётно. Для второй клетки x1+ x2+ y1 +y2  также нечётно, что означает чётность x2+ y2.  Аналогично получаем x3 +y3  нечётно, и так далее. Значит, x2022+ y2022  чётно, откуда получаем противоречие для последней клетки главной диагонали. Значит, такой последовательности ходов быть не могло.

Ответ:

нет

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

Задача 4#34898

Несколько шахматистов должны были провести турнир в один круг. Два игрока, сыграв поровну партий, выбыли из турнира. В результате состоялось 23 партии. Играли ли выбывшие шахматисты друг с другом?

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

Подсказка 1

Пусть в турнире участвовали n игроков. Как оценить снизу и сверху количество партий?

Подсказка 2

Верно! Если два выбывших не сыграли ни одной партии, то должно было быть сыграно (n-2)(n-3)/2 игр, а если бы они не выбыли, то сыграны были бы все n(n-1)/2 партий. Какие тогда могут быть n?

Подсказка 3

Верно! n = 8 или n = 9. А что тогда можно сказать о числе несыгранных партий?

Подсказка 4

Точно! Оно нечетно, а когда это возможно?

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

Пусть в турнире участвовали n  игроков. Они должны были сыграть n(n−-1)
  2  партий, из них (n−2)(n−3)
    2  партий сыграли друг с другом невыбывшие игроки. По условию

(n− 2)(n− 3)     n(n− 1)
-----2-----≤23 ≤---2---,

откуда n =8  или 9.

В обоих случаях число несостоявшихся партий n(n−1)
--2-- − 23  нечётно. Ещё из условия следует, что у выбывших осталось не сыграно по одинаковому числу партий. Сумма этих чисел чётна, значит, не равна общему числу несостоявшихся партий. Такое возможно в единственном случае: когда партия между выбывшими учитывается в сумме дважды. Значит, выбывшие не играли между собой.

Ответ:

Нет, не играли

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

Задача 5#78883

На доске написано пять натуральных чисел с суммой 2020.  Может ли их произведение оканчиваться на 2019?

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

Подсказка 1

В условии спрашивают про последние цифры числа, что намекает нам на рассмотрение остатков по какому-то модулю.

Подсказка 2

Хорошо подойдёт модуль 2. Сумма пяти чисел чётная, а произведение — нет. Осталось получить противоречие.

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

Среди пяти чисел в сумме точно есть одно чётное, так как если все числа нечётные, то и их сумма нечётная, а 2020  чётное. Значит, есть одно чётное число, а 2019  нечётное. Такого быть не может.

Ответ:

Не может

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

Задача 6#90084

В квадрате 11× 11  все клетки покрашены в белый цвет или черный цвет. За один шаг можно перекрасить все клетки в любой строке или столбце в противоположный цвет. Можно ли из полностью белого квадрата получить квадрат, в котором одна угловая клетка черная, а остальные клетки белые?

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

Подсказка 1

Попробуйте найти какие-то свойства белых и чёрных клеток, которые не меняются в процессе операций.

Подсказка 2

Обратите внимание на свойства количеств этих клеток. Какие самые очевидные приходят вам на ум?

Подсказка 3

Попробуйте последить за чётностью количества белых и чёрных клеток. Как еë меняет операция из условия?

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

Рассмотрим любой квадратик 2× 2  в нашем квадрате. Изначально все клетки в нем белые. Заметим, что любая операция внутри нашего маленького квадрата не меняет четность количества белых клеток. Действительно, либо операция никак не изменяет наш квадрат, либо меняет цвета только 2  клеток. Если эти 2  клетки белого цвета, тогда количество белых клеток в квадратике уменьшилось на 2  (но четность не поменялась), если обе клетки чёрные, то количество белых клеток в квадратике увеличилось на 2  (но четность опять не поменялась), если же клетки были разных цветов, то количество белых клеток в квадратике просто не поменяется. Итого, в любом квадратике 2× 2  будет четное число белых клеток, если изначально их там так же было четно. Но в квадрате 11×11,  который мы хотим получить, угловой квадратик 2×2  имеет нечетное количество белых клеток. Противоречие.

Ответ:

нельзя

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

Задача 7#90093

В фирме 99  сотрудников. Каждый отдыхает 7  дней подряд в году, в остальные дни — работает. Докажите, что число дней, когда отдыхает нечетное число сотрудников, не меньше 7.

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

Подсказка 1

Попробуйте подумать про какие-то очевидные вещи, на которые намекает условие.

Подсказка 2

Рассмотрите дни недели. Что можно сказать, например, про понедельники? Найдется ли хотя бы один понедельник, подходящий к условию?

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

Рассмотрим все понедельники в году. Каждый из сотрудников отдыхал ровно в одном из них. Значит, суммарно в понедельники отдыхали 99  человек. Но ведь найдётся понедельник, в который отдыхало нечётное количество человек. Аналогично с остальными днями недели.

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

Задача 8#100497

Поляне, древляне и северяне встали в хоровод. Известно, что полян ровно 25,  древлян 30  и некоторое количество северян. Рядом с каждым человеком стоит хотя бы по 1  северянину. Докажите, что найдется человек, рядом с которым стоит 2  северянина.

Источники: Муницип - 2024

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

Предположим, что такого человека нет. Значит, рядом с каждым стоит ровно по одному северянину. Будем обозначать за Х не северянина. Тогда рядом с каждым Х стоит один Х и один С(северянин). Получается, Х разбиваются на изолированные пары: СХХС. Всего Х 30+ 25= 55,  что нечётно. Значит, такой ситуации быть не может.

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

Задача 9#100772

У Пети в двух карманах было по одинаковому количеству монет. Он высыпал все эти монеты на стол и подсчитал, что орлов выпало на    7  больше, чем решек. Докажите, что он ошибся.

Источники: Муницип - 2023, Ростов, 7.2 (см. tasks.olimpiada.ru)

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

Пусть в каждом кармане было по k  монет, а орлов выпало x  , тогда решек выпало 2k− x  . Их разность: x− (2k− x)= 2(x− k)  — чётное число и не может равняться 7.

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

Задача 10#33374

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

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

Если произведение 4 натуральных чисел нечетно, то все эти 4 числа обязательно нечетны. Но сумма 4 нечетных чисел четна, значит, Совунья не права.

Ответ: Нет, не могут

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

Задача 11#33375

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

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

Покрасим четные числа в красный цвет, а нечетные в синий. Так как по кругу стоят 11 чисел, то красные и синие числа не могут чередоваться, то есть идти в порядке …К-С-К-С…. Это значит, что найдутся два одноцветных рядом стоящих числа, то есть два соседних числа одной четности. Тогда их сумма четна, и Бараш сможет указать именно эти два числа.

Ответ: Да, всегда

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

Задача 12#33376

Совунья игралась со своей любимой шахматной доской 8× 8  . В процессе она случайно пролила на нее зеленую краску. Может ли оказаться так, что количество испачканных краской клеток на 9 больше, чем не испачканных?

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

Если бы так случилось, что количества испачканных краской клеток и неиспачканных отличаются на 9, то эти количества были бы разной четности. Тогда их сумма нечетна. Но их сумма равна общему числу клеток на шахматной доске, то есть равна 64 — четному числу, чего быть не может. (Как будто бы не может быть что 64 - четное число) Значит, такого быть не могло.

Ответ: Нет

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

Задача 13#35512

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

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

Будем решать задачу от противного. Рассмотрим разложение чисел на простые множители, представив каждое число в виде pα1pα2...pαk
 1  2    k  . Посмотрим, что происходит при переходе от одного числа к другому. У нас либо добавляется, либо пропадает один простой множитель, либо одна из α  изменяется на 1. В любом случае сумма α1+ α2+ ...+ αk  изменяется на 1, то есть меняет чётность. Значит, чётность этой суммы должна чередоваться — но это невозможно, если чисел всего 2021, то есть нечётное количество.

Ответ: Нет, нельзя

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

Задача 14#72375

На межпланетный фестиваль “Радуга” прибыли 107  зелёных и фиолетовых человечков. Зелёные человечки правильно воспринимают цвета, а фиолетовым, к сожалению, зелёный кажется фиолетовым, и наоборот. Посмотрев вокруг, каждый участник фестиваля подошёл к кому-то, сказал “Какой вы фиолетовый!” и подарил кактус. Докажите, что хотя бы один человек на фестивале не получил такого подарка.

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

Подсказка 1

Подумаем со стороны зеленого человечка, а какому он дарил подарок? Точно так же подумаем и про фиолетового.

Подсказка 2

Зеленый дарил фиолетовому, а фиолетовый - зеленому! Если бы у нас было бы одинаковое количество каждого цвета, то их можно было разбить на пары, которые дарят друг другу. Почему это не может быть так?

Подсказка 3

Обратите внимание на четность общего количество человечков

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

Из условия следует, что зелёные дарили кактусы фиолетовым, а фиолетовые — зелёным. Так как общее количество человечков нечетно, то какого-то вида больше, чем другого. Допустим, что зелёных больше, тогда какому-то зелёному человечку кактуса не досталось.

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

Задача 15#72747

Существуют ли целые числа x,y,z,  удовлетворяющие равенству:

(x+ y)(y+ z)(z+ x)=2023

Источники: Муницип - 2022, Брянская область, 8.1

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

Подсказка 1

Что можно сказать про число 2023? Четное ли оно?

Подсказка 2

Да, 2023 - нечетное! А что можно сказать про три множителя в левой части уравнения? Какую четность они имеют?

Подсказка 3

Верно, поскольку чисел 3(x, y, z). То среди них будут либо 2 четных, либо 2 нечетных! А что мы знаем про сумму чисел одной четности? Каким по четности будет произведение трёх этих множителей?

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

Если бы такие три числа x,y и z  существовали, по крайней мере два из них имели бы одинаковую четность. Предположим, что это пара чисел x  и y  . Тогда сумма x+ y  четная, а значит, четным должно быть и произведение (x+ y)(y+ z)(z+ x).  Число же 2023,  которому это произведение должно равняться, — нечетное. Полученное противоречие показывает, что целых чисел, удовлетворяющих условию, не существует.

Варианты правильных ответов:
  1. нет
  2. Нет

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

Задача 16#91902

Учитель физкультуры хочет выстроить в шеренгу (линию) 60 школьников — 29 мальчиков и 31 девочку так, чтобы ни один из школьников (девочка или мальчик) не стоял между двумя девочками. Удастся ли ему это сделать?

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

Предположим, что так удастся расставить школьников.

Рассмотрим школьников на чётных позициях. Заметим, что среди них нет двух подряд девочек, откуда получаем, что на чётных позициях не более половины девочек. Аналогично на нечётных позициях не более половины девочек, а значит девочек не более 30.

Противоречие.

Ответ: нет

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

Задача 17#72169

Можно ли по окружности расставить 2n  черных и несколько белых фишек так, чтобы каждой черной фишке соответствовала диаметрально противоположная белая фишка и никакие две белые не стояли рядом?

Источники: Муницип - 2021, Калужская область, 9.4

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

Подсказка 1

Давайте задавать себе правильные, наводящие вопросы. Для начала мы ничего не знаем про количество белых фишек. Попробуем это исправить. По условию никакие две белые фишки не стоят рядом, а диаметрально противоположные различных цветов. Учитывая, что фишек у нас всего двух цветов, какой вывод из этого можно сделать?

Подсказка 2

Верно, делаем вывод, что чёрные фишки тоже чередуются, а белых фишек столько же, как и чёрных, - 2n штук. Давайте предположим, что у нас получилось расставить фишки по окружности. Теперь попробуем воспользоваться ещё вторым условием задачи.

Подсказка 3

Посмотрим на две произвольные фишки на диаметре. Что тогда можно сказать о количестве фишек между ними, и не будет ли там противоречия?

Подсказка 4

Ага, фишек между ними будет (4n - 2)/2 = 2n - 1. Это нечётное число, а у нас фишки одинаковых цветов не стоят рядом.

Подсказка 5

Получаем противоречие, так как крайние фишки среди 2n-1 будут одноцветные., а должны чередоваться Победа!

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

Так как каждой черной фишке соответствует диаметрально противоположная белая фишка и никакие две белые не стоят рядом, то фишки должны чередоваться, и значит, белых фишек тоже 2n.  Получается, что всего фишек 4n,  а на полуокружности между черной и белой фишкой стоит 4n−2-
 2  =2n − 1  фишка, поэтому крайние из них одноцветны, следовательно, расстановка невозможна.

Варианты правильных ответов:
  1. нет
  2. Нет
  3. Нельзя
  4. нельзя

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

Задача 18#95539

Алиса расставила 10  натуральных чисел по кругу. Чеширский Кот посмотрел на эти числа и заметил, что как бы он ни разделил круг на две половинки по 5  чисел в каждой, ровно в одной половинке произведение находящихся там чисел будет делиться на 2.  Сколько чётных чисел могло быть среди написанных Алисой? Найдите все ответы.

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

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

Очевидно, хотя бы одно четное число Алиса расставила. Если на круге есть хотя бы два чётных числа, то можно разделить круг на два полукруга так, чтобы в каждом полукруге было хотя бы одно чётное число, и тогда произведение чисел в каждом окажется чётных, что противоречит условию.

Ответ:

Одно

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

Задача 19#96058

У двух малышей есть по одному набору карточек с буквами, букв в наборах поровну. У каждого ребенка буквы не повторяются. Ребята смешали все карточки и начали составлять слова. Сначала они составили слово KЛОК, затем перемешали карточки и составили слово ОКНО, а смешав карточки еще раз, составили слово РОТОР. Докажите, что какая-то карточка осталась неиспользованной.

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

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

Заметим, что у каждого ребенка в наборе есть буквы K, О и P, так как в данных словах эти буквы встречаются дважды, а у одного ребенка буквы не повторяются. Буквы, из которых составлялись слова, помимо K,O  и P,  -Л, Т и H , каждая использована по одному разу. Значит, всего было использовано 9  карточек, а у двух малышей карточек в сумме четное количество. Значит, хотя бы одна карточка не использована.

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

Задача 20#96832

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

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

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

Заметим, что всего пар соседних клеток из разных домино 27  штук. В каждой из них должно быть хотя бы одно нечетное число. Но нечетных чисел всего 24:  по 8  единиц, троек и пятерок.

Ответ:

Нет, нельзя

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