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

Чётность

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

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

Задача 1#34898

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

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

Пусть в турнире участвовали 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  нечётно. Ещё из условия следует, что у выбывших осталось не сыграно по одинаковому числу партий. Сумма этих чисел чётна, значит, не равна общему числу несостоявшихся партий. Такое возможно в единственном случае: когда партия между выбывшими учитывается в сумме дважды. Значит, выбывшие не играли между собой.

Ответ:

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

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

Задача 2#78883

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

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

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

Ответ:

Не может

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

Задача 3#90084

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

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

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

Ответ:

нельзя

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

Задача 4#90093

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

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

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

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

Задача 5#100497

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

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

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

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

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

Задача 6#100772

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

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

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

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

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

Задача 7#33374

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

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

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

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

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

Задача 8#33375

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

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

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

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

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

Задача 9#33376

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

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

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

Ответ: Нет

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

Задача 10#35512

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

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

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

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

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

Задача 11#72375

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

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

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

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

Задача 12#72747

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

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

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

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

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

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

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

Задача 13#91902

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

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

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

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

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

Ответ: нет

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

Задача 14#72169

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

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

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

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

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

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

Задача 15#95539

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

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

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

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

Ответ:

Одно

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

Задача 16#96058

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

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

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

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

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

Задача 17#96832

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

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

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

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

Ответ:

Нет, нельзя

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

Задача 18#92723

Из чисел от 1  до 7  Саша выбрал пять и сообщил Ане их произведение. Исходя из этих данных Аня не может выяснить чётность суммы выбранных Сашей чисел. Какое число Саша сообщил Ане?

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

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

Посмотрим на два оставшихся числа. Так как сумму всех чисел от 1  до 7  Аня знает, то два оставшихся числа таковы, что по их произведению также нельзя определить четность их суммы. Поэтому их произведение можно представить как ab=xy,  причем a  и b  разной четности, а x  и y  одной. Тогда x  и y  — четные, поэтому четное из чисел a  и b  равно 4.  Далее все восстанавливается однозначно, и получаются числа 6  и 2  или 3  и 4.  Тогда произведение пяти чисел будет равно -7!
12 =420.

Ответ:

 420

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

Задача 19#82713

В 1a  классе каждого ребёнка попросили написать два числа: количество его одноклассников и количество его одноклассниц (именно в таком порядке; сам себя ребёнок не считает). Каждый ребёнок одно число написал правильно, а в другом ошибся ровно на 2  . Среди ответов были получены такие: (13,11),(17,11),(14,14)  . Сколько мальчиков и сколько девочек в классе?

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

Первое решение.

Обозначим детей, давших ответы (13,11),(17,11),(14,14)  через А, Б, В соответственно. Заметим, что если в классе m  мальчиков, то первое число в ответах девочек имеет ту же чётность, что и m  , а в ответах мальчиков - противоположную. Следовательно, дети А и Б одного пола, а В - другого.

Первые числа в ответах А и Б отличаются на 4, значит, они оба неправильные. Таким образом, количество одноклассников у А и Б равно 15 , а количество одноклассниц - 11 .

Если А и Б - мальчики, то в классе 16 мальчиков и 11 девочек. При этом у девочки В тогда 16 одноклассников и 10 одноклассниц, и ее ответ (14,14)  противоречит условию. Значит, А и Б девочки, и в классе 15 мальчиков и 12 девочек. ______________________

Второе решение.

Пусть какой-то ребёнок написал числа (m,d)  . Если бы оба числа он написал правильно, то он бы написал один из четырёх вариантов: (m − 2,d),(m + 2,d),(m,d− 2),(m,d +2)  .

Тогда, если этот ребёнок — мальчик, то существует четыре варианта количества мальчиков и девочек в классе: (m − 1,d),(m + 3,d),(m +1,d− 2)  и (m +1,d+2)  .

Аналогично, если этот ребёнок — девочка; возможные варианты в этом случае: (m − 2,d+ 1),(m + 2,d +1),(m,d− 1),(m,d +3)  .

Таким образом, каждый из ответов даёт нам восемь вариантов, сколько мальчиков и девочек могло быть в классе, один из которых должен быть верным:

для (13,11)  это (12,11),(16,11),(14,9),(14,13),(11,12),(15,12),(13,10),(13,14)  ;

для (17,11)  это (16,11),(20,11),(18,9),(18,13),(15,12),(19,12),(17,10),(17,14)  ;

для (14,14)  это (13,14),(17,14),(15,12),(15,16),(12,15),(16,15),(14,13),(14,17)  .

Осталось заметить, что только вариант (15,12)  встречается во всех трёх строчках.

Ответ: 15 мальчиков и 12 девочек

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

Задача 20#94455

Бухгалтеры, менеджеры и экономисты банка сидят за круглым столом. Когда директор попросил поднять руку бухгалтеров, рядом с которыми сидит экономист, руку подняли 20  человек. А когда директор попросил поднять руку менеджеров, рядом с которыми сидит экономист, руку подняли 25  человек. Докажите, что рядом с кем-то из поднимавших руку сидит сразу два экономиста.

Источники: Миссия выполнима 2016

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

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

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