На выпускном балу каждый юноша танцевал по крайней мере с одной девушкой, но никто из юношей не танцевал со всеми девушками, а каждая девушка танцевала по крайней мере с одним юношей, но никто из девушек не танцевал со всеми юношами.
Доказать, что среди присутствовавших на балу можно найти двух юношей и двух девушек так, что каждый из двух юношей танцевал лишь с одной из двух девушек, а каждая из этих двух девушек танцевала лишь с одним из этих двух юношей.
Подробнее
Расположим в ряд произвольным способом $n$ черных и $n$ белых шариков. Подсчитаем число перемен цвета в каждом таком расположении, то есть определим, сколько раз черные и белые шарики оказываются рядом.
Доказать, что расположений, в которых шарики различных цветов $n - k$ раз оказываются рядом, столько же, сколько расположений с $n + k$ парами разноцветных «соседей» ($0 < k < n$).
Подробнее
На всех клетках шахматной доски расставлены кубики. Грани кубиков и клетки шахматной доски конгруэнтны. У всех кубиков одна из граней выкрашена в черный цвет. Требуется повернуть кубики так, чтобы все четыре грани оказались сверху.
Доказать, что это можно сделать, если поворачивать разрешается не каждый кубик в отдельности, а лишь все кубики, стоящие на одной горизонтали или вертикали, вместе.
Подробнее
Какова вероятность того, что среди пяти вытянутых номеров лото имеются по крайней мере два последовательных (то есть отличающихся друг от друга на единицу) числа?
Подробнее
Дано $n$ точек, из которых никакие 3 не лежат на одной прямой. Несколько прямолинейных отрезков с концами в заданных точках выкрашены в красный, а несколько других - в синий цвет так, что из любой точки в любую другую можно попасть, двигаясь лишь вдоль окрашенных отрезков, причем этот путь определен однозначно.
Доказать, что оставшиеся еще не окрашенными отрезки с концами в заданных $n$ точках можно выкрасить либо в красный, либо в синий цвет так, чтобы у любого треугольника с вершинами в заданных точках число красных сторон было нечетным.
Подробнее
Имеется 30 копилок. Каждую копилку можно открыть лишь одним ключом, который не подходит ко всем остальным копилкам. Перемешав ключи, их бросили в запертые копилки наугад по одному. Две копилки взломали.
Какова вероятность того, что после этого все остальные копилки удастся открыть, не взламывая замков? (Открыв или взломав какую-либо копилку, мы можем использовать брошенный в нее ключ для открывания копилки, к которой он подходит.)
Подробнее
В классе учится одинаковое число мальчиков и девочек (всего класс насчитывает не менее 4 человек). Их в различном порядке выстраивают в один ряд и смотрят, нельзя ли разделить ряд на две части так, чтобы в каждой части девочек и мальчиков было поровну.
Пусть $a$ - число случаев, когда такое разбиение ряда невозможно, a $b$ - число случаев, когда удается разбить ряд на две части с одинаковым числом девочек и мальчиков в каждой из них, но лишь одним способом.
Доказать, что $b = 2a$.
Подробнее
Вдоль параллельных границ некоторой территории, имеющей форму квадрата со стороной 10 км, проложены автострады. На территории размещены 4 наблюдательных поста. Требуется построить подъездные дороги из отрезков, параллельных сторонам квадрата, так, чтобы из каждого наблюдательного поста можно было добраться на велосипеде до каждой автострады (по автостраде ездить на велосипеде воспрещается).
Доказать, что независимо от того, где расположены наблюдательные посты, всегда можно построить подъездные пути общей протяженностью не более 25 км (при некоторых расположениях наблюдательных постов меньшая протяженность подъездных путей может оказаться недостаточной).
Подробнее
Для учета посещаемости при входе в библиотеку повесили две доски. Каждый посетитель библиотеки обязан записать на одной доске, сколько читателей он застал, войдя в читальный зал, а на другой доске - сколько читателей оставалось в зале, когда он уходил из библиотеки.
Доказать, что за день на обеих досках появятся одни и те же числа (быть может, в различном порядке).
Подробнее
Дана бесконечная последовательность квадратов со сторонами длиной $1, \frac{1}{2}, \frac{1}{3} , \cdots , \frac{1}{n} , \cdots , $. Доказать, что существует квадрат, в котором можно разместить все квадраты последовательности так, чтобы они не перекрывали друг друга, и определить, чему равна сторона наименьшего из квадратов, вмещающих все квадраты данной последовательности.
Подробнее
Группа граждан страны А эмигрировала в страну Б, а группа граждан Б - в страну В. В результате этого рейтинги каждой страны оказались выше первоначальных. После этого направление миграционных потоков изменилось на противоположное - часть жителей В переехала в Б, а часть жителей Б - в А. Оказалось, что в результате рейтинги всех трех стран опять выросли (по сравнению с теми, которые были после первого переезда, но до начала второго). (Так, во всяком случае, утверждают информационные агентства этих стран.) Может ли такое быть (если да, то как, если нет, то почему)? (Предполагается, что за рассматриваемое время $Q$ граждан не изменилось, никто не умер и не родился.)
Подробнее
Вдоль дороги стоит 10 фонарей. Если перегорел один из них, а соседние светят, то дорожная служба не беспокоится. Но если перегорают два фонаря, стоящих подряд, то дорожная служба сразу меняет все перегоревшие фонари. Каждый фонарь перегорает независимо от других.
Найдите вероятность того, что при очередной замене придется поменять ровно 5 фонарей.
Подробнее
В поисках внеземной жизни ученые обнаружили интересный живой организм - Камкохоб. Эксперименты в земных условиях показали, что Камкохоб размножается делением. То есть родительский организм исчезает, и образуются новые особи. При этом каждая особь либо делится ровно на 5 потомков, либо не размножается, а остается одной особью. Экспериментальный образец, привезенный на Землю, размножался, некоторые его потомки тоже размножались. Какое количество потомков могло получиться? Опишите всю серию возможных ответов общей формулой, используя переменную $x$ (где $x$ - натуральное число).
Подробнее
Некий тест состоит из 26 вопросов. За каждый неверный ответ у испытуемого вычитается пять очков, а за каждый правильный - ему начисляется восемь очков. Испытуемый ответил на все вопросы. На сколько вопросов он ответил правильно, если в итоге сумма полученных им очков равнялась нулю?
Подробнее
В соревнованиях по теннису участвуют $n$ игроков. Каждый теннисист выбывает из турнира после первого поражения. Сколько следует провести встреч, чтобы выявить победителя?
Подробнее
