Олимпиадные задачи по теме «Классическая комбинаторика» для 4-8 класса

Для игры в шляпу Надя хочет разрезать лист бумаги на 48 одинаковых прямоугольников. Какое наименьшее количество разрезов ей придется сделать, если любые куски бумаги можно перекладывать, но нельзя сгибать, а Надя способна резать одновременно сколько угодно слоёв бумаги? (Каждый разрез – прямая линия от края до края куска.)

На рисунке приведены три примера показаний исправных электронных часов. Сколько палочек могут перестать работать, чтобы время всегда можно было определить однозначно? <div align="center"><img src="/storage/problem-media/117005/problem_117005_img_2.gif"></div>

Вася выписал все слова (не обязательно осмысленные), которые получаются вычеркиванием ровно двух букв из слова <i>ИНТЕГРИРОВАНИЕ</i>, а Маша сделала то же самое со словом <i>СУПЕРКОМПЬЮТЕР</i>. У кого получилось больше слов?

Десять футбольных команд сыграли каждая с каждой по одному разу. В результате у каждой команды оказалось ровно по <i>х</i> очков.

Каково наибольшее возможное значение <i>х</i>? (Победа – 3 очка, ничья – 1 очко, поражение – 0.)

В круговом шахматном турнире участвует 9 мальчиков и 3 девочки (каждый играет с каждым один раз, победа – 1 очко; ничья – 0,5; поражение – 0). Может ли в итоге оказаться, что сумма очков, набранных всеми мальчиками, будет равна сумме очков, набранных всеми девочками?

В каждой клетке таблицы, состоящей из 10 столбцов и <i>n</i> строк, записана цифра. Известно, что для каждой строки <i>A</i> и любых двух столбцов найдётся строка, отличающаяся от <i>A</i> ровно в этих двух столбцах. Докажите, что  <i>n</i> ≥ 512.

Для некоторых 2011 натуральных чисел выписали на доску все их 2011·1005 попарных сумм.

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

В волейбольном турнире с участием 73 команд каждая команда сыграла с каждой по одному разу. В конце турнира все команды разделили на две непустые группы так, что каждая команда первой группы одержала ровно <i>n</i> побед, а каждая команда второй группы – ровно <i>m</i> побед. Могло ли оказаться, что  <i>m</i> ≠ <i>n</i>?

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

На доске выписано  (<i>n</i> – 1)<i>n</i>  выражений:   <i>x</i>₁ – <i>x</i>₂,  <i>x</i>₁ – <i>x</i>₃,  ...,  <i>x</i>₁ – <i>x_n</i>,  <i>x</i>₂ – <i>x</i>₁,  <i>x</i>₂ – <i>x</i>₃,  ...,  <i>x</i>₂ – <i>x_n</i>,  ...,  <i>x_n</i> – <i>x</i>_<i>n</i>–1,   где  <i>n</i&...

Какое наибольшее количество точек самопересечения может иметь замкнутая ломаная, в которой 7 звеньев?

Для прохождения теста тысячу мудрецов выстраивают в колонну. Из колпаков с номерами от 1 до 1001 один прячут, а остальные в случайном порядке надевают на мудрецов. Каждый видит только номера на колпаках всех впереди стоящих. Далее мудрецы по порядку от заднего к переднему называют вслух целые числа. Каждое число должно быть от 1 до 1001, причём нельзя называть то, что уже было сказано. Результат теста – число мудрецов, назвавших номер своего колпака. Мудрецы заранее знали условия теста и могли договориться, как действовать.

  а) Могут ли они гарантировать результат более 500?

  б) Могут ли они гарантировать результат не менее 999?

Боря и Миша едут в поезде и считают столбы за окном: "один, два, ...". Боря не выговаривает букву "Р", поэтому при счете он пропускает числа, в названии которых есть буква "Р", а называет сразу следующее число без буквы "Р". Миша не выговаривает букву "Ш", поэтому пропускает числа с буквой "Ш". У Бори последний столб получил номер "сто". Какой номер этот столб получил у Миши?

Дана незамкнутая несамопересекающаяся ломаная из 37 звеньев. Через каждое звено провели прямую.

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

Из ряда натуральных чисел вычеркнули все числа, которые являются квадратами или кубами целых чисел. Какое из оставшихся чисел стоит на сотом месте?

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

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

<img align="right" src="/storage/problem-media/115364/problem_115364_img_2.gif"> Назовём лестницей высоты <i>n</i> фигуру, состоящую из всех клеток квадрата <i>n</i>×<i>n</i>, лежащих не выше диагонали (на рисунке показана лестница высоты 4). Сколькими различными способами можно разбить лестницу высоты <i>n</i> на несколько прямоугольников, стороны которых идут по линиям сетки, а площади попарно различны?

Докажите, что при любых натуральных  0 <<i>k</i><<i>m < n</i>  числа  <img align="absmiddle" src="/storage/problem-media/111922/problem_111922_img_2.gif">  и  <img align="absmiddle" src="/storage/problem-media/111922/problem_111922_img_3.gif">  не взаимно просты.

Дана таблица <i>n×n</i>, столбцы которой пронумерованы числами от 1 до <i>n</i>. В клетки таблицы расставляются числа 1, ..., <i>n</i>  так, что в каждой строке и в каждом столбце все числа различны. Назовём клетку <i>хорошей</i>, если число в ней больше номера столбца, в котором она находится. При каких <i>n</i> существует расстановка, в которой во всех строках одинаковое количество хороших клеток?

300 бюрократов разбиты на три комиссии по 100 человек. Каждые два бюрократа либо знакомы друг с другом, либо незнакомы. Докажите, что найдутся два таких бюрократа из разных комиссий, что в третьей комиссии есть либо 17 человек, знакомых с обоими, либо 17 человек, незнакомых с обоими.

В очереди к стоматологу стоят 30 ребят: мальчиков и девочек. Часы на стене показывают 8:00. Как только начинается новая минута, каждый мальчик, за которым стоит девочка, пропускает её вперед. Докажите, что перестановки в очереди закончатся до 8:30, когда откроется дверь кабинета.

Имеются три комиссии бюрократов. Известно, что для каждой пары бюрократов из разных комиссий среди членов оставшейся комиссии есть ровно 10 бюрократов, которые знакомы с обоими, и ровно 10 бюрократов, которые незнакомы с обоими. Найдите общее число бюрократов в комиссиях.

Турнир, в котором участвовало 20 спортсменов, судили 10 арбитров. Каждый сыграл с каждым один раз, и каждую встречу судил ровно один арбитр. После окончания каждой игры оба участника фотографировались с арбитром. Через год после турнира была найдена стопка из всех этих фотографий. Оказалось, что не про каждого можно определить, кем он является – спортсменом или арбитром. Сколько могло быть таких людей?

Новогодняя гирлянда, висящая вдоль школьного коридора, состоит из красных и синих лампочек. Рядом с каждой красной лампочкой обязательно есть синяя. Какое наибольшее количество красных лампочек может быть в этой гирлянде, если всего лампочек 50?

Назовём раскраску доски 8×8 в три цвета <i>хорошей</i>, если в любом уголке из пяти клеток присутствуют клетки всех трёх цветов. (Уголок из пяти клеток – это фигура, получающаяся из квадрата 3×3 вырезанием квадрата 2×2.)  Докажите, что количество хороших раскрасок не меньше чем 6⁸.