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