В некотором поселке 1000 жителей. Ежедневно каждый из них делится узнанными вчера новостями со всеми своими знакомыми. Известно, что любая новость становится известной всем жителям поселка.
Докажите, что можно выбрать 90 жителей так, что если одновременно всем им сообщить какую-то новость, то через 10 дней она станет известной всем жителям поселка.
Подробнее
Можно ли все клетки какой-нибудь прямоугольной таблицы окрасить в белый и черный цвета так, чтобы белых и черных клеток было поровну, а в каждой строке и в каждом столбце было более 3/4 клеток одного цвета?
Подробнее
На окружности отмечено $3k$ точек, разделяющих ее на $3k$ дуг, из которых $k$ дуг имеют длину 1, еще $k$ дуг - длину 2 и остальные $k$ дуг - длину 3. Докажите, что среди отмеченных точек найдутся две диаметрально противоположные.
Подробнее
Квадратная таблица $n \times n$ клеток заполнена целыми числами. При этом в клетках, имеющих общую сторону, записаны числа, отличающиеся одно от другого не больше чем на 1. Докажите, что хотя бы одно число встречается в таблице:
а) не менее чем $[n/2]$ раз ($[а]$ - целая часть числа $а$);
б) не менее чем $n$ раз.
Подробнее
Множество $M$ состоит из $k$ попарно не пересекающихся отрезков, лежащих на одной прямой. Известно, что любой отрезок длины, не большей 1, можно расположить на прямой так, чтобы концы его принадлежали множеству $M$. Докажите, что сумма длин отрезков, составляющих $M$, не меньше $1/k$.
Подробнее
В строку в возрастающем порядке выписали $n$ различных действительных чисел. Под ними во вторую строку выписали те же числа, только, быть может, в другом порядке. Для каждой пары чисел, выписанных одно под другим, вычислили сумму. Эти суммы образовали третью строку. Оказалось, что числа в третьей строке также расположены в возрастающем порядке. Докажите, что первая строка совпадает со второй.
Подробнее
Имеется $n + 1$ гирь общим весом $2n$ и весы с двумя чашками, находящиеся в равновесии. Вес каждой из гирь выражается натуральным числом. Гири по очереди кладут на чашки весов: сначала самую тяжелую (или одну из самых тяжелых), затем самую тяжелую из оставшихся и т. д. При этом каждую следующую гирю кладут на ту чашку весов, которая в данный момент легче, а если весы находятся в равновесии, то на любую из чашек. Докажите, что после того, как на весах окажутся все гири, весы будут находиться в равновесии.
Подробнее
В белых клетках шахматной доски размером $1983 \times 1984$ записаны числа 1 или -1 так, что для любой черной клетки произведение чисел, стоящих в соседних с ней белых клетках, равно 1. Докажите, что это возможно только в том случае, если все записанные числа равны 1.
Подробнее
На плоскости проведено $n$ прямых ($n > 2$), делящих плоскость на несколько областей. Некоторые из этих областей окрашены, причем никакие две окрашенные области не могут соприкасаться по границе. Докажите, что число окрашенных областей не превосходит $\frac{1}{3} (n^2 + n)$.
Подробнее
Имеется куб, кубическая коробка с крышкой тех же размеров и шесть красок. Каждой краской окрашивается одна грань куба и одна из граней коробки. Докажите, что куб можно таким образом положить в коробку, чтобы каждая грань куба прилегла к грани коробки, окрашенной другим цветом.
Подробнее
Правильный шестиугольник разбит на 24 треугольника. Во всех 19 узлах фигуры, показанной на рис., записаны различные числа, Докажите, что среди 24 треугольников разбиения имеется по крайней мере 7 треугольников, в вершинах которых тройки чисел записаны в порядке возрастания, если
мы будем считать против часовой стрелки.
Подробнее
На бесконечном клетчатом листе со стороной клетки 1 разрешается делать разрезы только по линиям сетки. Докажите, что при любом целом $m > 12$ можно вырезать прямоугольник площади, большей $m$, из которого нельзя вырезать прямоугольник площади $m$.
Подробнее
В одном государстве король хочет построить $n$ городов и $n - 1$ дорог между ними так, чтобы из каждого города можно было проехать в любой другой. (Каждая дорога соединяет два города, дороги не пересекаются и не проходят через другие города.) Король хочет, чтобы кратчайшие расстояния по сети дорог между парами городов равнялись соответственно $1, 2, 3, \cdots, \frac {n(n-1)}{2}$ км. Возможно ли это, если а) $n = 6$; б) * $n = 1986$?
Подробнее
Докажите, что прямоугольную таблицу размером $m \times n$ клеток можно заполнить квадратами различных натуральных чисел так, чтобы суммы чисел в каждой строке и каждом столбце были также квадратами натуральных чисел.
Подробнее
На плоскости дан правильный шестиугольник. Каждая его сторона разделена на 1000 равных частей, и точки деления соединены отрезками, параллельными сторонам шестиугольника. Выберем какие-либо три узла получившейся сетки, являющиеся вершинами правильного треугольника (любого размера и расположения), и окрасим их. Будем продолжать окрашивать таким способом тройки узлов до тех пор, пока это возможно. Докажите, что если неокрашенным останется один узел, то он не может быть вершиной исходного шестиугольника.
Подробнее