На множестве S введено отношение $\rightarrow$ которое выполнено для пар элементов из множества S и обладает следующими свойствами: 1) для любых различных элементов $a, b \in S$ выполнено ровно одно из отношений $a \rightarrow b$ или $b \rightarrow a$; 2) для любых трех различных элементов $a, b, c \in S$ выполнение отношений $a \rightarrow b $ и $b \rightarrow c$ влечет за собой выполнение отношения $c \rightarrow a$. Каково наибольшее число элементов, которое может содержать множество S?
Подробнее
В обществе, состоящем из 1982 человек, среди любых четырех человек можно выбрать по крайней мере одного, знакомого с остальными тремя. Каково минимально возможное количество людей, которые знакомы со всеми?
Подробнее
В компании, состоящей из пяти человек, среди любых трех человек найдутся двое, которые знают друг друга, и двое, незнакомых друг с другом. Доказать, что компанию можно рассадить за круглым столом так, чтобы по обе стороны от каждого человека сидели его знакомые.
Подробнее
Девять математиков встретились на международной конференции и обнаружили, что среди любых трех из них по меньшей мере двое говорят на одном языке. Кроме того, каждый математик может говорить не более чем на трех языках. Доказать, что хотя бы три из них говорят на одном и том же языке.
Подробнее
a) В комнате находится 10 человек, причем среди любых трех из них есть двое знакомых между собой. Доказать, что найдутся четыре человека, любые два из которых знакомы друг с другом.
б) Останется ли верным утверждение п.а), если в нем число 10 заменить на 9?
Подробнее
В некоторой стране любые два города связаны друг с другом непосредственно одним из следующих средств сообщения: автобусом, поездом или самолетом. Известно, что не существует города, обеспеченного всеми тремя видами транспорта, и в то же время не существует таких трех городов, любые два из которых связаны одним и тем же средством сообщения. Найти наибольшее возможное количество городов в этой стране.
Подробнее
В некотором обществе любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Доказать, что в этом обществе все имеют одинаковое число знакомых.
Подробнее
В каждой из трех школ учится по $n$ человек. Любой ученик имеет в сумме $n + 1$ знакомых учеников из двух других школ. Доказать, что можно выбрать по одному ученику из каждой школы так, чтобы все трое выбранных учеников были знакомы друг с другом.
Подробнее
В пространстве даны $2n$ различных точек $A_{1}, A_{2}, \cdots, A_{2n} (n > 1)$. Никакие три из них не лежат на одной прямой. Пусть М - множество из $(n^{2} + 1)$ отрезков, концами которых являются данные точки. Доказать, что существует хотя бы один треугольник с вершинами в некоторых точках $A_{r}, A_{s}, A_{t}$, все стороны которого принадлежат множеству М. Доказать, что если число элементов множества М не превосходит $n^{2}$, то такого треугольника может и не существовать.
Подробнее
На вечере собралось несколько юношей и девушек. При этом оказалось, что если выбрать любую группу юношей, то число девушек, знакомых по крайней мере с одним из юношей этой группы, будет не меньше числа юношей в группе. Доказать, что все юноши одновременно смогут танцевать каждый в паре со знакомой девушкой.
Подробнее
Некоторые из городов $P_{1}, \cdots, P_{1983}$ соединены попарно некоторыми авиалиниями, принадлежащими компаниям $A_{1}, \cdots, A_{10}$. Известно только, что из любого города можно перелететь в любой другой без пересадок и что каждая авиалиния действует в обоих направлениях. Доказать, что (как бы ни были города соединены авиалиниями) существует хотя бы одна компания, которая может обеспечить путешествие с началом и концом в одном и том же городе и с нечетным числом используемых авиалиний.
Подробнее
В Простоквашинской начальной школе учится 20 детей. У любых двух из них есть общий дед. Докажите, что у одного из дедов в этой школе учится не менее 14 внуков. (Замечание: любой ребёнок не может иметь более двух дедушек.)
Подробнее
Коротышки, живущие в Цветочном городе, вдруг стали болеть гриппом. В один день несколько коротышек простудились и заболели, и хотя потом уже никто не простужался, здоровые коротышки заболевали, навещая своих больных друзей. Известно, что каждый коротышка болеет гриппом ровно день, причём после этого у него по крайней мере ещё один день есть иммунитет - т. е. он здоров и заболеть опять в этот день не может. Несмотря на эпидемию, каждый здоровый коротышка ежедневно навещает своих больных друзей. Когда началась эпидемия, коротышки забыли о прививках и не делают их. Докажите, что
а) если за день до эпидемии какие-нибудь коротышки сделали прививку и имели в первый день иммунитет, то эпидемия может продолжаться сколь угодно долго;
б) если же в первый день иммунитета ни у кого не было, то эпидемия рано или поздно кончится.
Подробнее
1997 фишек расположены на плоскости в вершинах выпуклого 1997-угольника. За один ход можно разбить их на две группы и фишки первой группы сдвинуть на какой-нибудь вектор, а остальные фишки оставить на месте. Может ли случиться, что после а) 9; б) 10 ходов все фишки окажутся на одной прямой?
Подробнее
Граф - это набор вершин, причем некоторые из них соединены ребрами (каждое ребро соединяет ровно две вершины графа). Раскраска вершин графа называется правильной, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в $k$ цветов, причем его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех $k$ цветов ровно по одному разу.
Подробнее