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

В футбольном чемпионате участвуют 18 команд. На сегодняшний день проведено 8 туров (в каждом туре все команды разбиваются на пары и в каждой паре команды играют друг с другом, причём пары не повторяются). Верно ли, что найдутся три команды, которые не сыграли ни одного матча между собой?

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

В команде сторожей у каждого есть разряд (натуральное число). Сторож <i>N</i>-го разряда <i>N</i> суток дежурит, потом <i>N</i> суток спит, снова <i>N</i> суток дежурит, <i>N</i> – спит, и так далее. Известно, что разряды любых двух сторожей различаются хотя бы в три раза. Может ли такая команда осуществлять ежедневное дежурство? (Приступить к дежурству сторожа могут не одновременно, в один день могут дежурить несколько сторожей.)

Клетки доски размером 5×5 раскрашены в шахматном порядке (угловые клетки – чёрные). По чёрным клеткам этой доски двигается фигура – мини-слон, оставляя след на каждой клетке, где он побывал, и больше в эту клетку не возвращаясь. Мини-слон может ходить либо в свободные от следов соседние (по диагонали) клетки, либо прыгать (также по диагонали) через одну клетку, в которой оставлен след, на свободную клетку за ней. Какое наибольшее количество клеток сможет посетить мини-слон?

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

Даны положительные числа <i>b</i> и <i>c</i>. Докажите неравенство  (<i>b</i> – <i>c</i>)²⁰¹¹(<i>b</i> + <i>c</i>)²⁰¹¹(<i>c</i> – <i>b</i>)²⁰¹¹ ≥ (<i>b</i>²⁰¹¹ – <i>c</i>²⁰¹¹)(<i>b</i>²⁰¹¹ + <i>c</i>²⁰¹¹)(<i>c</i>²⁰¹¹ – <i>b</i>²⁰¹¹).

2011 складов соединены дорогами так, что от каждого склада можно проехать к любому другому, возможно, проехав по нескольким дорогам. На складах находится по  <i>x</i>₁, ..., <i>x</i>₂₀₁₁  кг цемента соответственно. За один рейс можно провезти с произвольного склада на другой по соединяющей их дороге произвольное количество цемента. В итоге на складах по плану должно оказаться по  <i>y</i>₁, ..., <i>y</i>₂₀₁₁  кг цемента соответственно, причём

<i>x</i>₁ + <i>x</i>₂ + ... + <i>x</i>₂₀₁₁ = <i>y</i>₁ + <i>y<...

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

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

В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.

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

На новом сайте зарегистрировалось 2000 человек. Каждый пригласил к себе в друзья по 1000 человек. Два человека <i>объявляются</i> друзьями тогда и только тогда, когда каждый из них пригласил другого в друзья. Какое наименьшее количество пар друзей могло образоваться?

На доске выписано  (<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&...

В некой стране 100 городов (города считайте точками на плоскости). В справочнике для каждой пары городов имеется запись, каково расстояние между ними (всего 4950 записей).   а) Одна запись стёрлась. Всегда ли можно однозначно восстановить её по остальным?   б) Пусть стёрлись <i>k</i> записей, и известно, что в этой стране никакие три города не лежат на одной прямой. При каком наибольшем <i>k</i> всегда можно однозначно восстановить стёршиеся записи?

Игра в "супершахматы" ведётся на доске размером 100×100, и в ней участвует 20 различных фигур, каждая из которых ходит по своим правилам. Известно, что любая фигура с любого места бьет не более 20 полей (но больше о правилах ничего не сказано, например, если фигуру <i>А</i> передвинуть, то о том, как изменится множество битых полей мы ничего не знаем). Докажите, что можно расставить на доске все 20 фигур так, чтобы ни одна из них не била другую.

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

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

На дне рождения у Васи было 10 ребят (включая Васю). Оказалось, что у каждых двух из этих ребят есть общий дедушка.

Докажите, что у семи из них есть общий дедушка.

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

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

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

<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> на несколько прямоугольников, стороны которых идут по линиям сетки, а площади попарно различны?

Натуральное число<i>b</i>назовём<i>удачным</i>, если для любого натурального<i>a</i>, такого, что<i>a</i>⁵делится на<i>b</i>², число<i>a</i>² делится на<i>b</i>. Найдите количество удачных натуральных чисел, меньших 2010.

Докажите, что при любых натуральных  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>A</i> на плане) до своего отеля (точка <i>B</i>). Турист хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрестке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет. <div align="center"><img align="absmiddle" src="/storage/problem-media/111897/problem_111897_img_2.gif"></div>

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

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