Какое наибольшее число ладей можно расставить на шахматной доске размером $3n \times 3n$ так, чтобы каждая из них находилась под ударом не более одной из остальных?
Подробнее
Клетки шахматной доски размером $n \times n$, где $n$ - четное число, большее 2, раскрашены $n^{2}/2$ красками так, что каждой краской окрашены ровно две клетки. Доказать, что на доске можно расставить $n$ ладей так, чтобы они стояли на клетках разного цвета и не били друг друга.
Подробнее
В пространстве с прямоугольной системой координат рассматривается множество Е точек с целочисленными координатами, принимающими значения от 0 до 1982. Каждая из этих точек окрашена либо в красный, либо в синий цвет. Сколько существует раскрасок, обладающих следующим свойством; число красных вершин у любого параллелепипеда (с вершинами из Е и ребрами, параллельными осям) делится на 4?
Подробнее
Каждый из 17 ученых переписывается с остальными. В их переписке речь идет лишь о трех темах. Каждая пара ученых переписывается друг с другом лишь по одной теме. Докажите, что не менее трех ученых переписываются друг с другом по одной и той же теме.
Подробнее
В группе переводчиков, каждый из которых знает один или несколько иностранных языков, 24 владеют японским, 24 — малайским, 24 — персидским. Докажите, что можно выделить подгруппу, в которой ровно 12 человек владели бы японским, ровно 12 — малайским и ровно 12 — персидским.
Подробнее
Король решил устроить проверку своим ста мудрецам и сообщил, что на следующий день он выстроит всех с завязанными глазами в очередь и наденет каждому чёрный или белый колпак.
После того, как глаза будут развязаны, каждый, начиная с последнего в очереди, назовёт предполагаемый цвет своего колпака. Если он при этом не угадает, то будет казнён. У мудрецов ещё есть время договориться, как они будут действовать завтра. Скольким мудрецам наверняка удастся спастись?
Подробнее
В игре «Десант» две армии захватывают страну. Они ходят по очереди, каждым ходом занимая один из свободных городов. Первый свой город армия захватывает с воздуха, а каждым следующим ходом она может захватить любой город, соединённый дорогой с каким-нибудь уже занятым этой армией городом. Если таких городов нет, армия прекращает свои боевые действия (при этом, возможно, другая армия свои действия продолжает). Найдётся ли такая схема городов и дорог, что армия, ходящая второй, сможет захватить более половины всех городов, как бы ни действовала первая армия? (Число городов конечно, каждая дорога соединяет ровно два города.)
Подробнее
Мартышка поднимается на один из 100 этажей небоскрёба и бросает вниз кокос. Она пытается выяснить, с какого наименьшего этажа нужно бросить кокос, чтобы тот разбился. Каково минимальное число попыток, достаточное для этого, если у мартышки всего два кокоса?
Подробнее
Существует ли конечное слово из букв русского алфавита, в котором нет двух соседних одинаковых подслов, но таковые появляются при приписывании (как справа, так и слева) любой буквы русского алфавита.
Комментарий. Словом мы называем любую последовательность букв русского алфавита, не обязательно осмысленную, подсловом называется любой фрагмент слова. Например, АБВШГАБ - слово, а АБВ, Ш, ШГАБ - его подслова.
Подробнее
В городе Цветочном $n$ площадей и $m$ улиц ($m \geq n + 1$). Каждая улица соединяет две площади и не проходит через другие площади. По существующей в городе традиции улица может называться либо синей, либо красной. Ежегодно в городе происходит переименование: выбирается площадь и переименовываются все выходящие из нее улицы. Докажите, что вначале можно назвать улицы так, что переименованиями нельзя добиться одинаковых названий у всех улиц города.
Подробнее
В один из дней года оказалось, что каждый житель города сделал не более одного звонка по телефону. Докажите, что население города можно разбить не более, чем на три группы так, чтобы жители, входящие в одну группу, не разговаривали в этот день между собой по телефону.
Подробнее
Куб покрасили снаружи белой краской и распилили на 64 маленьких кубика. Затем из маленьких кубиков произвольным образом составили куб. (Кубики могли не только поменяться местами, но и повернуться.) Какова вероятность того, что он будет белым снаружи? (Все способы составления большого куба считаются равновероятными.)
Подробнее
В зрительном зале кресла расставлены в $p$ рядов и $q$ «колонн» (условимся называть так кресла, выстроенные «в затылок» одно другому). Таким образом, всего зал вмещает $pq$ зрителей ($p > 1, q > 1$).
В каждом кресле сидит один школьник, причем все ребята, находящиеся в этом зале, отличаются между собой по росту. Учитель выбирает в каждом ряду самого маленького школьника. Рост самого высокого из них оказывается равным $a$. Затем учитель выбирает самого высокого школьника в каждой «колонне». Рост самого маленького из них оказывается равным $b$.
Выяснить, каким из трех соотношений
$a < b, a = b, a >b$
могут быть связаны числа $a$ и $b$, установить, можно ли изменить это соотношение, пересаживая ребят в зрительном зале.
Подробнее
На выпускном балу каждый юноша танцевал по крайней мере с одной девушкой, но никто из юношей не танцевал со всеми девушками, а каждая девушка танцевала по крайней мере с одним юношей, но никто из девушек не танцевал со всеми юношами.
Доказать, что среди присутствовавших на балу можно найти двух юношей и двух девушек так, что каждый из двух юношей танцевал лишь с одной из двух девушек, а каждая из этих двух девушек танцевала лишь с одним из этих двух юношей.
Подробнее
Расположим в ряд произвольным способом $n$ черных и $n$ белых шариков. Подсчитаем число перемен цвета в каждом таком расположении, то есть определим, сколько раз черные и белые шарики оказываются рядом.
Доказать, что расположений, в которых шарики различных цветов $n - k$ раз оказываются рядом, столько же, сколько расположений с $n + k$ парами разноцветных «соседей» ($0 < k < n$).
Подробнее