Олимпиадные задачи по теме «Комбинаторика» для 10 класса - сложность 2 с решениями

Можно ли нарисовать на поверхности кубика Рубика такой замкнутый путь, который проходит через каждый квадратик ровно один раз (через вершины квадратиков путь не проходит)?

Тетрадный лист раскрасили в 23 цвета по клеткам. Пара цветов называется хорошей, если существует две соседние клетки, закрашенные этими цветами. Каково минимальное число хороших пар?

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

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

Берутся всевозможные непустые подмножества из множества чисел   1, 2, 3, ..., <i>n</i>.  Для каждого подмножества берётся величина, обратная к произведению всех его чисел. Найти сумму всех таких обратных величин.

20 футбольных команд проводят первенство. В первый день все команды сыграли по одной игре. Во второй также все команды сыграли по одной игре.

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

Каждые две из шести ЭВМ соединены своим проводом. Укажите, как раскрасить каждый из этих проводов в один из пяти цветов так, чтобы из каждой ЭВМ выходило пять проводов разного цвета.

Двадцать городов соединены 172 авиалиниями.

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

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

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

Из натуральных чисел составляются последовательности, в которых каждое последующее число больше квадрата предыдущего, а последнее число в последовательности равно 1969 (последовательности могут иметь разную длину). Доказать, что различных последовательностей такого вида меньше чем 1969.

В окружность вписан неправильный <i>n</i>-угольник, который при повороте окружности около центра на некоторый угол  α ≠ 2π   совмещается сам с собой. Доказать, что <i>n</i> – число составное.

<i>n</i> точек соединены отрезками так, что каждая точка с чем-нибудь соединена и нет таких двух точек, которые соединялись бы двумя разными путями.

Доказать, что общее число отрезков равно  <i>n</i> – 1.

Доказать, что не существует таких натуральных чисел <i>x, y, z, k</i>, что  <i>x^k + y^k = z^k</i>  при условии  <i>x < k,  y < k</i>.

Рассмотрим лист клетчатой бумаги со стороной клетки, равной 1. Пусть <i>P_k</i> – число всех непересекающихся ломаных длины <i>k</i>, начинающихся в точке <i>O</i> – некотором фиксированном узле сетки. Доказать, что  <i>P_k</i>·3^–<i>k</i> < 2  для любого <i>k</i>.

Имеется 1959 положительных чисел<i>a</i>₁,<i>a</i>₂...,<i>a</i>₁₉₅₉, сумма которых равна 1. Рассматриваются всевозможные комбинации из 1000 чисел, причём комбинации считаются совпадающими, если они отличаются только порядком чисел. Для каждой комбинации рассматривается произведение входящих в неё чисел. Доказать, что сумма всех этих произведений меньше 1.

Сколько существует четырёхзначных номеров (от 0001 до 9999), у которых сумма двух первых цифр равна сумме двух последних цифр?

Докажите, что  2^<i>n</i> > (1 – <i>x</i>)^<i>n</i> + (1 + <i>x</i>)^<i>n</i>  при целом  <i>n</i> ≥ 2  и  |<i>x</i>| < 1.

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

В числовом треугольнике <div align="center"><img src="/storage/problem-media/76551/problem_76551_img_2.gif"></div>каждое число равно сумме чисел, расположенных в предыдущей строке над этим числом и над его соседями справа и слева (отсутствующие числа считаются равными нулю). Докажите, что в каждой строке, начиная с третьей, найдутся чётные числа.

Сколько существует натуральных чисел, меньших тысячи, которые не делятся ни на 5, ни на 7?

Сколькими различными способами можно разложить натуральное число <i>n</i> на сумму трёх натуральных слагаемых? Два разложения, отличающиеся порядком слагаемых, считаются различными.

  а) Выбраны 6 различных цветов; требуется раскрасить 6 граней куба, каждую в особый цвет из числа избранных. Сколькими геометрически различными способами можно это сделать? Геометрически различными называются две такие расцветки, которые нельзя совместить одну с другой при помощи вращений куба вокруг его центра.

  б) Решить ту же задачу для случая раскраски граней додекаэдра в 12 различных цветов.

Последовательность натуральных чисел  <i>a</i>₁ < <i>a</i>₂ < <i>a</i>₃ < ... < <i>a</i>_<i>n</i> < ...  такова, что каждое натуральное число либо входит в последовательность, либо представимо в виде суммы двух членов последовательности, быть может, одинаковых. Докажите, что  <i>a</i>_<i>n</i> ≤ <i>n</i>²  для любого  <i>n</i> = 1, 2, 3, ...

Каждое неотрицательное целое число представимо, причём единственным образом, в виде   <img align="absmiddle" src="/storage/problem-media/73613/problem_73613_img_2.gif">   где <i>x</i> и <i>y</i> – целые неотрицательные числа. Докажите это.

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

  а) ровно 4 клетки?   б) ровно 5 клеток?   в) все 8 клеток?