Задача 091. Гриб называется плохим, если в нем не менее 10 червей. В лукошке 90 плохих и 10 хороших грибов. Могут ли все грибы стать хорошими после того, как некоторые черви переползают из плохих грибов в хорошие?
Решение:
Пусть в каждом плохом грибе ровно 10 червей, а в хорошем червей нет. Далее, пусть из каждого плохого гриба по одному червю переползут в хорошие, по 9 в каждый. В результате в каждом грибе окажется по 9 червей, и все грибы будут хорошими.
Ответ: могут.
Задача 092. Можно ли в центры 16 клеток шахматной доски 8×8 вбить гвозди так, чтобы никакие три гвоздя не лежали на одной прямой?
Решение:
Ответ: да, можно.
Задача 093. Даны три кучки камней, по n камней в каждой. За один ход можно выбрать две кучки, убрать из них по одному камню, при этом добавив один камень в третью кучку. При каких n можно через несколько ходов оставить только один камень?
Решение:
Давайте возьмем число n = 7 и посмотрим, что мы вообще можем получить.
7 7 7
6 6 8
7 5 7
8 4 6
7 5 5
8 4 4
7 3 5
Заметим, что три числа всегда одной четности. Докажем это.
Пусть у нас были числа Ч Ч Ч, так как все числа изменяются на 1, станет Н Н Н. Аналогично, если было Н Н Н, так как все числа изменяются на 1, станет Ч Ч Ч. Таким образом, 0 0 1 мы получить не сможем.
Задача 094. По кругу записано 100 чисел, каждое из которых равно среднему арифметическому своих соседей. Докажите, что все 100 чисел равны.
Решение:
Рассмотрим наибольшее из записанных чисел. Если таких чисел окажется несколько, то возьмем любое из них. Поскольку это число не меньше своих соседей и является средним арифметическим этих соседей, оба соседа равняются данному числу.
Проводя аналогичные рассуждения для соседей данного числа, для их соседей и т. д., получаем, что все числа равны между собой. Что и требовалось доказать. (В этой задаче крайним было наибольшее из всех чисел.)
Задача 095. Электронные часы показывают цифры часов и минут (например, 18:40). Какая наибольшая сумма цифр может быть на таких часах?
Решение:
Следует оценить сумму цифр в записи числа часов и в записи числа минут. Заметим, что максимальное число часов на часах — 23, максимальное число минут на часах — 59.
Наибольшее значение первой цифры — 2, второй — 9, значит, сумма первых двух цифр не может быть больше 11. Сумма равна 11 только при первой цифре 2 и второй цифре 9, но число часов не может быть равным 29. Следовательно, сумма первых двух цифр меньше 11. Сумма, равная 10, достигается на 19 часах.
Наибольшее значение третьей цифры — 5, четвертой — 9, значит, сумма первых двух цифр не может быть больше 14. Сумма, равная 14, достигается на 59 минутах. В итоге наибольшая сумма цифр — это 10+14=24.
Ответ: 24.
Задача 096. Несколько команд участвуют в однокруговом футбольном турнире. Докажите, что независимо от расписания игр в любой момент найдутся хотя бы две команды, сыгравшие к этому моменту одинаковое количество матчей.
Решение:
Обозначим количество команд через n. Рассмотрим произвольный момент турнира. К этому моменту каждая команда могла сыграть от 0 до n − 1 матчей: различных вариантов ровно n, то есть столько же, сколько команд.
Пусть все команды сыграли разное количество матчей. Тогда каждый из n вариантов реализован ровно одной командой. Следовательно, какая-то команда не сыграла ни одного матча, а другая команда сыграла n – 1 матчей, то есть играла со всеми остальными командами. Но тогда она играла и с той командой, которая не сыграла ни одного матча, — противоречие.
Задача 097. Плоскость окрашена в два цвета — белый и черный, причем имеются точки и белого, и черного цвета. Докажите, что всегда найдутся две точки одного цвета на расстоянии 1 друг от друга.
Решение:
Рассмотрим равносторонний треугольник со стороной 1, произвольно расположенный на этой плоскости. Поскольку вершин у треугольника три («кролики»), а цветов только два («клетки»), согласно принципу Дирихле, найдутся две вершины одного цвета (любые две вершины этого треугольника расположены на расстоянии 1 друг от друга).
Задача 098. Могут ли три рыцаря, каждый со своим оруженосцем, переправиться через реку на двухместной лодке, если оруженосцы отказываются оставаться с незнакомыми рыцарями без своих хозяев?
Решение:
Здесь следует перебирать последовательно все возможные варианты переправы, отсекая заведомо неподходящие. А для того чтобы оруженосцы не оставались с незнакомыми рыцарями, рыцари не должны оставаться в меньшинстве.
Для того чтобы проиллюстрировать задачу, обозначим рыцарей и их оруженосцев через Р1, Р2, Р3 и О1, О2, О3 соответственно, а реку обозначим знаком тире. Изначально все находились по одну сторону от реки, т. е.
Р1 Р2 Р3 О1 О2 О3 −,
в итоге мы хотим получить расположение
− Р1 Р2 Р3 О1 О2 О3.
1. Если в первую переправу поедет один из рыцарей со своим оруженосцем, то оруженосцы не останутся с незнакомыми рыцарями ни на первом берегу, ни на втором. Вернуть лодку на первый берег оруженосец не может, так как в этом случае на первом берегу оруженосец окажется без своего рыцаря, что нас не устраивает. Значит, после первой переправы лодку назад должен возвращать рыцарь. В результате первая переправа (туда-обратно) будет выглядеть так:
Р1 Р2 Р3 О1 О2 О3 − ⇒ Р1 Р2 О1 О2 − Р3 О3 ⇒ Р1 Р2 Р3 О1 О2 − О3.
2. После этого на первом берегу окажется 3 рыцаря и 2 оруженосца, а на втором берегу — 1 оруженосец. Определим того, кто на этот раз может переправиться на другой берег. Двух рыцарей отправлять нельзя, так как в этом случае на первом берегу рыцари останутся в меньшинстве. Рыцаря и оруженосца нельзя, так как в этом случае на втором берегу рыцари будут в меньшинстве. Следовательно, отправить придется двух оруженосцев. Пригнать лодку обратно придется оруженосцу, поскольку на втором берегу будут только оруженосцы. В результате вторая переправа (туда-обратно) будет выглядеть так:
Р1 Р2 Р3 О1 О2 − О3 ⇒ Р1 Р2 Р3 − О1 О2 О3 ⇒ Р1 Р2 Р3 О1 − О2 О3.
3. Теперь на первом берегу будут 3 рыцаря и 1 оруженосец, а на втором — 2 оруженосца. Переправить на другой берег рыцаря с оруженосцем мы не можем, так как тогда там рыцари будут в меньшинстве, значит, отправляем двух рыцарей. В этом случае на первом берегу останутся рыцарь с оруженосцем, а на втором будет 2 рыцаря и 2 оруженосца. Теперь отправить возвращать лодку кого-то одного уже на получится, так как либо на первом, либо на втором берегу рыцари окажутся в меньшинстве. Получается, что отправить обратно можно только рыцаря с оруженосцем. В результате третья переправа (туда-обратно) будет выглядеть так:
Р1 Р2 Р3 О1 − О2 О3 ⇒ Р1 О1 − Р2 Р3 О2 О3 ⇒ Р1 Р2 О1 О2 − Р3 О3.
Заметим, что теперь ситуация стала совершенно симметричной. Если до последнего маневра на первом берегу были рыцарь с оруженосцем, а на втором — 2 рыцаря и 2 оруженосца, то после маневра наоборот: на первом берегу 2 рыцаря и 2 оруженосца, а на втором 1 рыцарь и 1 оруженосец. Так как наша исходная задача также была симметричной (все были на первом берегу, а должны оказаться на втором берегу), то нужно выполнить все предыдущие действия в обратном порядке.
4. Сейчас на первом берегу 2 рыцаря и 2 оруженосца, а на втором 1 рыцарь и 1 оруженосец. Отправим на второй берег двух рыцарей, а лодку возвращать поручим оруженосцу:
Р1 Р2 О1 О2 − Р3 О3 ⇒ О1 О2 − Р1 Р2 Р3 О3 ⇒ О1 О2 О3 − Р1 Р2 Р3.
5. Двух оруженосцев отправим на второй берег, а лодку возвращать поручим рыцарю:
О1 О2 О3 − Р1 Р2 Р3 ⇒ О3 − Р1 Р2 Р3 О1 О2 ⇒ О3 Р3 − Р1 Р2 О1 О2.
6. Последней поездкой отправим оставшихся рыцаря с оруженосцем:
О3 Р3 − Р1 Р2 О1 О2 ⇒ − Р1 Р2 Р3 О1 О2 О3.
В результате наших действий все оказались на другом берегу реки.
Ответ: Да.
Задача 099. Докажите, что среди любых шести человек всегда найдутся либо трое попарно знакомых, либо трое попарно незнакомых.
Решение:
У данного человека среди остальных пяти есть либо не менее трех знакомых, либо не менее трех незнакомых ему. Разберем, например, первый случай. Среди этих трех людей есть либо двое знакомых — тогда они вместе с выбранным нами исходно человеком образуют нужную тройку, либо они все трое попарно незнакомы.
Задача 100. Суммарное расстояние между съездами 1 и 20 на новой автомагистрали составляет 140 км. Между любыми двумя съездами должно быть не менее 7 км. Чему равно максимальное расстояние между любыми двумя соседними съездами?
Решение:
Прежде всего отметим, что между съездами 1 и 20 всего 19 «расстояний». Поскольку минимальное расстояние между любыми двумя съездами равно 7 км, рассмотрим крайний случай, в котором все расстояния, кроме одного, равны 7 км. Тогда минимальная сумма 18 «расстояний» составит 18 × 7 = 126 км. Таким образом, максимальное расстояние между любыми двумя съездами равно 140 – 126 = 14 км, иначе не хватит километров, чтобы выдержать 7-километровую дистанцию между остальными съездами.