Олимпиадные задачи по теме «Комбинаторика» для 10 класса - сложность 3-5 с решениями
В футбольном чемпионате участвуют 18 команд. На сегодняшний день проведено 8 туров (в каждом туре все команды разбиваются на пары и в каждой паре команды играют друг с другом, причём пары не повторяются). Верно ли, что найдутся три команды, которые не сыграли ни одного матча между собой?
Докажите, что при любых натуральных 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"> не взаимно просты.
Рассмотрим все возможные наборы чисел из множества {1, 2, 3, ..., <i>n</i>}, не содержащие двух соседних чисел.
Докажите, что сумма квадратов произведений чисел в этих наборах равна (<i>n</i> + 1)! – 1.
Числа 1, 2, 3, ..., <i>n</i> записываются в некотором порядке: <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, <i>a</i><sub>3</sub>, ..., <i>a<sub>n</sub></i>. Берётся сумма <i>S</i> = <sup><i>a</i><sub>1</sub></sup>/<sub>1</sub> + <sup><i>a</i><sub>2</sub></sup>/<sub>2</sub> + ... + <sup><i>a<sub>n</sub></i></sup>/<sub><i>n</i></sub>. Найдите такое <i>n</i>, чтобы среди таких сумм (при всевозможных перестановках <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>,...
30 учеников одного класса решили побывать друг у друга в гостях. Известно, что ученик за вечер может сделать несколько посещений, и что в тот вечер, когда к нему кто-нибудь должен прийти, он сам никуда не уходит. Покажите, что для того, чтобы все побывали в гостях у всех,
а) четырёх вечеров недостаточно,
б) пяти вечеров также недостаточно,
в) а десяти вечеров достаточно,
г) и даже семи вечеров тоже достаточно.
В стране больше 101 города. Столица соединена авиалиниями со 100 городами, а каждый город, кроме столицы, соединён авиалиниями ровно с десятью городами (если <i>A</i> соединён с <i>B</i>, то <i>B</i> соединён с <i>A</i>). Известно, что из каждого города можно попасть в любой другой (может быть, с пересадками). Доказать, что можно закрыть половину авиалиний, идущих из столицы, так, что возможность попасть из каждого города в любой другой сохранится.
<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a</i><sub>101</sub> – такая перестановка чисел 2, 3, ..., 102, что <i>a</i><sub><i>k</i></sub> делится на <i>k</i> при каждом <i>k</i>. Найти все такие перестановки.
В Чикаго живут 36 гангстеров, некоторые из которых враждуют между собой. Каждый гангстер состоит в нескольких бандах, причём нет двух банд с совпадающим составом. Оказалось, что гангстеры, состоящие в одной банде, не враждуют, но если гангстер не состоит в какой-то банде, то он враждует хотя бы с одним её участником. Какое наибольшее число банд могло быть в Чикаго?
В Чикаго орудует 36 преступных банд, некоторые из которых враждуют между собой. Каждый гангстер состоит в нескольких бандах, причём каждые два гангстера состоят в разных наборах банд. Известно, что ни один гангстер не состоит в двух бандах, враждующих между собой. Кроме того, оказалось, что каждая банда, в которой не состоит некоторый гангстер, враждует с какой-то бандой, в которой данный гангстер состоит. Какое наибольшее количество гангстеров может быть в Чикаго?
Найти количество нечётных чисел в <i>n</i>-й строке треугольника Паскаля.