Город имеет в плане вид прямоугольника, разбитого на клетки: $n$ улиц параллельны друг другу, $m$ других пересекают их под прямым углом. На улицах города - но не на перекрестках - стоят милиционеры. Каждый милиционер сообщает номер проходящего мимо него автомобиля, направление его движения и время, когда он проехал. Какое наименьшее число милиционеров нужно расставить на улицах, чтобы по их показаниям можно было однозначно восстановить путь любого автомобиля, едущего по замкнутому маршруту (маршрут не проходит по одному и тому же участку улицы дважды)?
Подробнее
В центре поля, имеющего форму квадрата, находится волк, а в вершинах квадрата - четыре собаки. Волк может бегать по всему полю, а собаки - только по сторонам квадрата. Известно, что волк задирает собаку, а две собаки задирают волка. Максимальная скорость каждой собаки в 1,5 раза больше максимальной скорости волка. Докажите, что собаки имеют возможность не выпустить волка из квадрата.
Подробнее
Дана конечная последовательность нулей и единиц, обладающая двумя свойствами:
а) если в некотором произвольном месте последовательности выделить 5 цифр подряд и в любом другом месте тоже выделить 5 цифр подряд, то эти пятерки будут различны (эти пятерки могут перекрываться, например $\underbrace {\underbrace {01101}01}$);
б) если к последовательности добавить справа любую цифру 0 или 1, то свойство а) перестает выполняться.
Докажите, что первая четверка цифр нашей последовательности совпадает с последней четверкой.
Подробнее
В некотором государстве система авиалиний устроена таким образом, что любой город соединен авиалиниями не более чем с тремя другими и из любого города в любой другой можно проехать, сделав не более одной пересадки.
Какое максимальное число городов может быть в этом государстве?
Подробнее
На доске написано уравнение
$x^3 + \cdots + x^2 + \cdots + x + \cdots = 0$.
Двое играют в такую игру. Первый ставит на любое из пустых мест целое число, отличное от нуля (положительное или отрицательное). Затем второй ставит целое число на одно из оставшихся мест. Наконец, первый ставит целое число на последнее свободное место, Докажите, что первый может играть так, чтобы независимо от хода второго все три корня получившегося уравнения оказались целыми числами.
Подробнее
В розыгрыше первенства страны по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?
Подробнее
а) Замок имеет форму (в плане) равностороннего треугольника со стороной 100 метров. Он разделен на 100 треугольных залов. Все стены залов имеют одинаковую длину - 10 метров. В середине каждой стены между залами сделана дверь. Докажите, что если человек захочет пройти по замку, побывав в каждом зале не более одного раза, то он сможет осмотреть не более 91 зала.
б) Каждая сторона правильного треугольника разбита на к равных частей. Через точки деления проведены прямые, параллельные сторонам. В результате треугольник разбился на $k^2$ маленьких треугольничков. Назовем «цепочкой» последовательность треугольничков, в которой ни один треугольник не появляется дважды, а каждый последующий имеет общую сторону с предыдущим. Каково наибольшее возможное число треугольничков в «цепочке»?
Подробнее
Вершины правильного $n$-угольника покрашены несколькими красками (каждая одной краской) так, что точки одного и того же цвета служат вершинами правильного многоугольника. Докажите, что среди этих многоугольников найдутся два равных.
Подробнее
а) Двое играют в такую игру. Первый записывает один под другим два ряда по 10 чисел так, чтобы выполнялось следующее правило: если число $b$ записано под числом $a$, а число $d$ - под числом $c$, то $a + d = b + c$. Второй игрок, зная это правило, хочет определить все написанные числа. Ему разрешается задавать первому игроку вопросы типа «Какое число стоит в первой строке на третьем месте?» или «Какое число стоит во второй строке на девятом месте?» и т. п. За какое наименьшее число таких вопросов второй игрок сможет узнать все числа?
б) В таблице $m \times n$ записаны числа так, что для любых двух строк и любых двух столбцов сумма чисел в двух противоположных вершинах образуемого ими прямоугольника равна сумме чисел в двух других его вершинах. Часть чисел стерли, но по оставшимся можно восстановить стертые. Докажите, что осталось не меньше чем $m + n - 1$ чисел.
Подробнее
В три сосуда налито по целому числу литров воды. В любой сосуд разрешается перелить столько воды, сколько в нем уже содержится, из любого другого сосуда. Докажите, что несколькими такими переливаниями можно освободить один из сосудов. (Сосуды достаточно велики: каждый может вместить всю имеющуюся воду.)
Подробнее
а) В вершине $A_1$ правильного 12-угольника $A_1A_2 \cdots A_{12}$ стоит знак минус, а в остальных - плюсы. Разрешается одновременно менять знак на противоположный в любых шести последовательных вершинах многоугольника. Докажите, что за несколько таких операций нельзя добиться того, чтобы в вершине $A_2$ оказался знак минус, а в остальных вершинах - плюсы.
б) Докажите то же утверждение, если разрешается менять знаки не в шести, а в четырех последовательных вершинах многоугольника.
в) Докажите то же утверждение, если разрешается одновременно менять знак в трех последовательных вершинах многоугольника.
Подробнее
На бесконечном листе клетчатой бумаги $N$ клеток выкрашено в черный цвет. Докажите, что из листа можно вырезать конечное число квадратов так, что будут выполнены два условия:
1) все черные клетки будут лежать в вырезанных квадратах,
2) в любом вырезанном квадрате площадь черных клеток составит не менее 1/5 и не более 4/5 площади этого квадрата.
Подробнее
Переключатель (рис. а) с двумя входами и двумя выходами может находиться в двух различных состояниях.
На рис. б изображена схема телефонной связи с тремя входами и тремя выходами, которая обладает таким свойством «универсальности»: меняя состояния переключателей, можно осуществить любое
из шести соединений трех входов с тремя различными выходами, т. е.
(Проверьте это. Заметьте, что общее число различных состояний этой схемы равно $2^3 = 8$, поскольку каждый из переключателей может находиться в двух состояниях.)
а) Постройте схему с четырьмя входами и четырьмя выходами, которая была бы «универсальной», т. е. осуществляла бы любое из 24 возможных соединений выходов и входов.
б) Какое минимальное число переключателей нужно для такой схемы?
в) Назовем схему с $n$ входами и $n$ выходами $n$-универсальной, если она осуществляет любое из $n! = 1 \cdot 2 \cdot \cdots \cdot n$ возможных соединений $n$ входов с $n$ различными выходами.
На рис., в изображена схема с восемью входами и восемью выходами, где $A$ и $B$ - 4 - универсальные схемы. Докажите, что она является 8 - универсальной.
Оцените сверху и снизу число переключателей в минимальной $n$-универсальной схеме.
Подробнее
На прямой дано 50 отрезков. Докажите, что верно хотя бы одно из следующих утверждений:
а) некоторые восемь отрезков имеют общую точку; б) найдется восемь отрезков, никакие два из которых не имеют общей точки.
Подробнее
Треугольная таблица строится по следующему правилу: в верхней строке написано натуральное число $a$, а далее под каждым числом $k$ слева пишется $k^2$, а справа - число $k + l$. Например, при $a = 2$ получается таблица, изображенная на рис. Докажите, что в каждой строчке такой таблицы все числа различны.
Подробнее
