Разрежьте фигуру, изображённую на рисунке, на три части так, чтобы линии разреза не проходили по сторонам клеток и чтобы из частей можно было сложить квадрат. Предложите как можно большее число способов такого разрезания.
Ответ:
Решение:
В каждую клетку доски $21\times 13$ клеток поставили либо чёрную, либо белую шашку. Оказалось, что в любых двух соседних по стороне клетках стоит хотя бы одна чёрная шашка. Какое наименьшее количество чёрных шашек может стоять на доске?
Ответ:
Решение:
Строки клетчатой доски $1001\times2012$ пронумерованы от $1$ до $1001$ снизу вверх, а столбцы пронумерованы от $1$ до $2012$ слева направо. Змейка начинает ползти из левой нижней клетки доски направо. Змейка не может выходить за пределы доски и посещать одну клетку более одного раза. Если змейка не может продолжить движение, она поворачивает налево и далее следует по прямой. Таким образом, змейка пройдёт доску по спирали, побывав в каждой клетке ровно по одному разу. Найдите сумму номеров строки и столбца клетки, в которой змейка закончит движение.
Ответ:
Решение:
Фокусник вместе со своим помощником собираются показать следующий фокус. Помощник надевает фокуснику повязку на глаза, приглашает на сцену случайного зрителя из зала и просит его написать последовательность из нулей и единиц длины $2^{2025}$. Затем помощник верно называет фокуснику номер и значение некоторого одного члена последовательности. Задача фокусника — отгадать 2025 других членов последовательности (т. е. назвать их номера и значения). Докажите, что они могут заранее договориться так, чтобы фокус удался.
Ответ:
Решение:
В ряд стоят 9 вертикальных столбиков. В некоторых местах между соседними столбиками вставлены горизонтальные палочки, никакие две из которых не находятся на одной высоте. Жук ползёт снизу вверх; когда он встречает палочку, он переползает по ней на соседний столбик и продолжает ползти вверх. Известно, что если жук начинает внизу первого столбика, то он закончит свой путь на девятом столбике. Всегда ли можно убрать одну из палочек так, чтобы жук, начав внизу первого столбика, в конце пути оказался наверху пятого столбика?
Например, если палочки расположены как на рисунке, то жук будет ползти по сплошной линии. Если убрать третью палочку на пути жука, то он поползёт по пунктирной линии.
Например, если палочки расположены как на рисунке, то жук будет ползти по сплошной линии. Если убрать третью палочку на пути жука, то он поползёт по пунктирной линии.
Ответ:
Решение:
Султан собрал 300 придворных мудрецов и предложил им испытание. Имеются колпаки 25 различных цветов, заранее известных мудрецам. Султан сообщил, что на каждого из мудрецов наденут один из этих колпаков, причём если для каждого цвета написать количество надетых колпаков, то все числа будут различны. Каждый мудрец будет видеть колпаки остальных мудрецов, а свой колпак нет. Затем все мудрецы одновременно огласят предполагаемый цвет своего колпака. Могут ли мудрецы заранее договориться действовать так, чтобы гарантированно хотя бы 150 из них назвали цвет верно?
Ответ:
Решение:
В лаборатории на полке стоят 120 внешне неразличимых пробирок, в 118 из которых находится нейтральное вещество, в одной — яд и в одной — противоядие. Пробирки случайно перемешались, и нужно найти пробирку с ядом и пробирку с противоядием. Для этого можно воспользоваться услугами внешней тестирующей лаборатории, в которую одновременно отправляют несколько смесей жидкостей из любого числа пробирок (по одной капле из пробирки), и для каждой смеси лаборатория сообщит результат: $+1$, если в смеси есть яд и нет противоядия; $-1$, если в смеси есть противоядие, но нет яда; $0$ в остальных случаях. Можно ли, подготовив 19 таких смесей и послав их в лабораторию единой посылкой, по сообщённым результатам гарантированно определить, в какой пробирке яд, а в какой противоядие?
Ответ:
Решение:
В доме из $2^n$ комнат сделали евроремонт. При этом выключатели света оказались перепутанными, так что при включении выключателя в одной комнате загорается лампочка, вообще говоря, в какой-то другой комнате. Чтобы узнать, какой выключатель к какой комнате подсоединён, прораб посылает несколько людей в какие-то комнаты, чтобы те, одновременно включив там выключатели, вернулись и сообщили ему, горела лампочка в их комнате или нет.
а) Докажите, что за $2n$ таких посылок прораб может установить соответствие между выключателями и комнатами.
б) А может ли он обойтись $2n-1$ такими посылками?
а) Докажите, что за $2n$ таких посылок прораб может установить соответствие между выключателями и комнатами.
б) А может ли он обойтись $2n-1$ такими посылками?
Ответ:
Решение:
С левого берега реки на правый с помощью одной лодки переправились $N$ туземцев, каждый раз плавая направо вдвоем, а обратно — в одиночку. Изначально каждый знал по одному анекдоту, каждый — свой. На берегах они анекдотов не рассказывали, но в лодке каждый рассказывал попутчику все известные ему на данный момент анекдоты. Для каждого натурального $k$ найдите наименьшее возможное значение $N$, при котором могло случиться так, что в конце каждый туземец знал, кроме своего, ещё не менее чем $k$ анекдотов.
Ответ:
Решение:
Сто мудрецов хотят проехать на электричке из 12 вагонов от первой до 76-й станции. Они знают, что на первой станции в два вагона электрички сядут два контролёра. После четвертой станции на каждом перегоне один из контролёров будет переходить в соседний вагон, причем они ходят по очереди. Мудрец видит контролёра, только если он в соседнем вагоне или через вагон. На каждой станции каждый мудрец может перебежать по платформе не далее чем на три вагона (например, из 7-го вагона мудрец может добежать до любого вагона с номером от 4 до 10 и сесть в него). Какое максимальное число мудрецов сможет ни разу не оказаться в одном вагоне с контролёром, как бы контролёры ни перемещались? (Никакой информации о контролёрах, кроме указанной в задаче, мудрец не получает. Мудрецы договариваются о стратегии заранее.)
Ответ:
Решение:
Саша написал по кругу в произвольном порядке не более ста различных натуральных чисел, а Дима пытается угадать их количество. Для этого Дима сообщает Саше в некотором порядке несколько номеров, а затем Саша сообщает Диме в том же порядке, какие числа стоят под указанными Димой номерами, если считать числа по часовой стрелке, начиная с одного и того же числа. Сможет ли Дима заведомо угадать количество написанных Сашей чисел, сообщив
а) $17$ номеров;
б) менее $16$ номеров?
а) $17$ номеров;
б) менее $16$ номеров?
Ответ:
Решение:
Команда из $n$ школьников участвует в игре: на каждого из них надевают шапку одного из $k$ заранее известных цветов, а затем по свистку все школьники одновременно выбирают себе по одному шарфу. Команда получает столько очков, у скольких её участников цвет шапки совпал с цветом шарфа (шарфов и шапок любого цвета имеется достаточное количество; во время игры каждый участник не видит своей шапки, зато видит шапки всех остальных, но не имеет права выдавать до свистка никакую информацию). Какое наибольшее число очков команда, заранее наметив план действий каждого её члена, может гарантированно получить:
а) при $n=k=2$;
б) при произвольных фиксированных $n$ и $k$?
а) при $n=k=2$;
б) при произвольных фиксированных $n$ и $k$?
Ответ:
Решение:
Имеется двести шариков ста цветов, по два шарика каждого цвета. Фокусник разложил их произвольным образом в сто коробочек, по два шарика в коробочку, где что лежит — игрок не знает. За ход игрок указывает на любые две коробочки, после чего фокусник незаметно для игрока выбирает по шарику из этих коробочек и меняет их местами. Если в какой-то момент в каждой коробочке будут лежать разноцветные шарики, ведущий выдаёт игроку приз. Может ли игрок действовать так, чтобы гарантированно получить приз, как бы фокусник ни менял шарики?
Ответ:
Решение:
У хозяйки есть кусок мяса, которым она хочет накормить трёх котиков. Раз в несколько секунд хозяйка отрезает кусочек мяса и скармливает его одному из котиков на свой выбор, причём каждый кусочек должен составлять одну и ту же долю куска, от которого его отрезают. Через некоторое время хозяйка убирает остаток мяса в холодильник. Может ли она скормить котикам поровну мяса?
Ответ:
Решение:
Кусок сыра массой 1 кг разрезали на $n\geqslant 4$ кусков массами меньше 600 г. Оказалось, что их нельзя разбить на две кучки так, чтобы масса каждой кучки была не меньше 400 г, но не больше 600 г (кучка может состоять из одного или нескольких кусков). Докажите, что найдутся три таких куска, что суммарная масса любых двух из них больше 600 г.
Ответ:
Решение:
Даны две последовательности из букв А и Б, в каждой из которых по 100 букв. За одну операцию разрешается вставить в какое-то место последовательности (возможно, в начало или в конец) одну или несколько одинаковых букв или убрать из последовательности одну или несколько подряд идущих одинаковых букв. Докажите, что из первой последовательности можно получить вторую не более чем за 100 операций.
Ответ:
Решение:
В равнобедренной трапеции проведена диагональ. По контуру каждого из получившихся двух треугольников ползёт свой жук. Скорости движения жуков постоянны и одинаковы. Жуки не меняют направления обхода своих контуров, и по диагонали трапеции они ползут в разных направлениях. Докажите, что при любых начальных положениях жуков они когда-нибудь встретятся.
Ответ:
Решение:
В узлах сетки клетчатого прямоугольника $4\times 5$ расположены 30 лампочек, изначально все они погашены. За ход разрешается провести любую прямую, не задевающую лампочек (размерами лампочек следует пренебречь, считая их точками), такую, что с какой-то одной стороны от неё ни одна лампочка не горит, и зажечь все лампочки по эту сторону от прямой. Каждым ходом нужно зажигать хотя бы одну лампочку. Можно ли зажечь все лампочки ровно за четыре хода?
Ответ:
Решение:
Есть бесконечная в одну сторону клетчатая полоска, клетки которой пронумерованы натуральными числами, и мешок с десятью камнями. В клетках полоски камней изначально нет. Можно делать следующее:
- перемещать камень из мешка в первую клетку полоски или обратно;
- если в клетке с номером $i$ лежит камень, то можно переложить камень из мешка в клетку с номером $i+1$ или обратно.
Ответ:
Решение:
На прямой сидят $2019$ точечных кузнечиков. За ход какой-нибудь из кузнечиков прыгает через какого-нибудь другого так, чтобы оказаться на прежнем расстоянии от него. Прыгая только вправо, кузнечики могут добиться того, чтобы какие-то двое из них оказались на расстоянии ровно $1$ мм друг от друга. Докажите, что кузнечики могут добиться того же, прыгая из начального положения только влево.
Ответ:
Решение: