МАЛЫЙ МЕХМАТ МГУ

Кружок 5 класса

Разные задачи (16 февраля 2013 года)

1.

Пешеходная зебра состоит из 30 чередующихся чёрных и белых полос. Злостный нарушитель Василий каждую ночь тайно перекрашивает одну из полос в противоположный цвет (если после этого соседние полосы будут иметь один цвет, они объединяются в одну широкую полосу). Может ли зебра после двух недель хулиганских действий стать целиком одноцветной?

Решение

Решение. Нет.
Доказательство. Каждую из 14 ночей он может уменьшить количество полос каждого из цветов не более, чем на одну (одного цвета путём перекрашивания его в другой, а другого цвета — на одну путём объединения двух или трёх находящихся рядом полос, одна из которых новая), а полос каждого цвета по 15. Значит, после двух недель никакой из обоих цветов не исчезнет.

2.

Сторож Степаныч унёс со склада мешок с мукой, который весит 30 кг. В мешке имеется дырка, через которую мука высыпается со скоростью 100 г/мин. Изначально сторож бредёт со скоростью 2 км/ч, но с каждым просыпанным килограммом муки его скорость возрастает на 1 км/ч. Через 10 минут после Степаныча за ним со склада выбежала мышка, которая кушает просыпанную муку со скоростью 10 г/мин. Какова будет скорость мышки в тот момент, когда она доест муку?

Указание О размерностях физических величин. Решение

Указание. Заметьте, что важно только, что происходило в конце пути. Какова была скорость Степаныча с мешком, когда из него сыпался последний килограмм муки? Найдите плотность просыпанной муки пути в его конце. В каких физических единицах она должна измеряться?

О размерностях физических величин.. Плотность просыпанной муки показывает её количество (то есть в граммах или килограммах) на каком-либо участке пути (а длина участка меряется в метрах или километрах), значит, может измеряться в граммах на метр.
Размерности физических величин помогут получить и проверить ответ: при делении величин друг на друга их размерности тоже делятся, а скорость мышки должна измеряться в метрах в минуту или чём-либо аналогичном (в каких-либо единицах измерения расстояния за какую-либо единицу измерения времени). Попробуйте догадаться, как же можно вычислить скорость мышки? Проверьте, правильную ли размерность будет иметь в таком случае ваш ответ.

Решение.

Когда сыпался последний, 30-й килограмм муки, Степаныч шёл со скоростью \(2 + 29 = 31\) км/ч. Так как скорость высыпания муки измеряется в граммах в минуту, то нужно пересчитать скорость Степаныча в метры в минуту (1 км = 1000 м, 1 ч = 60 мин):
\(31 \frac{км}{ч} = \frac{31 \cdot 1000}{60} \frac{м}{мин} = \frac{31 \cdot 50}{3} \frac{м}{мин}\).

Плотность следа муки означает, как много её рассыпалось за каждый кусочек пути. Значит, она должна измеряться в граммах на метр пути, значит, её можно вычислить, разделив скорость просыпания муки на скорость сторожа (минуты, таким образом, сокращаются):
\(100 \frac{г}{мин}\) : \(\frac{31 \cdot 50}{3} \frac{м}{мин}\) = \(\frac{100 \cdot 3}{31 \cdot 50} \frac{г \cdot мин}{м \cdot мин}\) = \(\frac{2 \cdot 3}{31} \frac{г}{м}\) = \(\frac{6}{31}\) г/м.

Аналогично, чтобы получить скорость мышки вдоль следа (в метрах в минуту), понимаем, что нужно разделить скорость поедания муки мышкой (в граммах за каждую минуту) на плотность муки в следе (в граммах на каждый метр):
\(10 \frac{г}{мин} : \frac{6}{31} \frac{г}{м} = \frac{10 \cdot 31}{6} \frac{г \cdot м}{мин \cdot г} = \frac{310}{3} \frac{м}{мин} = 51\frac{2}{3} \frac{м}{мин}\).

3.

Очень умные Петя и Вася выписывают четырёхзначные числа. Петя выписывает такие числа, у которых первая цифра равна сумме трёх других, а Вася такие, у которых последняя цифра равна сумме трёх других. Кто выпишет больше чисел?

О соответствиях между множествами. Указание 2 Решение

О соответствиях между множествами..

Чтобы узнать, какое из множеств содержит больше чисел — множество чисел, придуманных Петей, или множество чисел, придуманных Васей, установите соответствие между ними, то есть придумайте правило, позволяющее по числу, выписанному одним из ребят, однозначно написать число, выписанное другим.

Если они выписали одинаковое количество чисел, то есть правило, позволяющее по каждому числу, написанному Петей, написать число для Васи, и наоборот. Таким образом, числа объединятся в пары: придуманное Петей и придуманное Васей, а значит, их количество одинаково.

Если же кто-то из них выписал больше чисел, например, Вася больше, чем Петя, то обратного правила придумать не удастся. Для любого числа, написанного Петей, можно будет по правилу написать число для Васи, но будут "лишние" числа, написанные Васей, не соответствующие никаким Петиным и потому не получающиеся с помощью этого правила. Обратное правило, позволяющее по Васиному числу получить Петино, будет можно применить не ко всем Васиным числам.

Указание 2. Заметьте симметрию в условиях на числа, которые выписывают ребята: одна из цифр должна быть равна сумме трёх остальных цифр. Условия отличаются только местом, на котором стоит эта цифра. Придумайте правило для сопоставления друг другу чисел Пети и Васи и проверьте с его помощью, по любому ли числу одного из ребят можно получить число другого.

Решение.

Условия на числа Пети и Васи отличаются положением цифры, которая должна быть равна сумме остальных. Это даёт идею использовать такое правило сопоставления: число Васи получается из числа Пети перестановкой первой и последней цифр местами (можно использовать и другие правила, например, записывать цифры в обратном порядке). Действительно, если первая цифра была равна сумме трёх остальных (например, 9315), то в полученном числе (5319) последняя цифра будет равна сумме трёх остальных. Очень важно, что наше правило обладает такими свойствами: по заданному числу однозначно получается другое (то есть не может быть так, что одно и то же число соответствует нескольким разным), и, наоборот, одно число Васи получается только из одного числа Пети (не может быть, что из разных чисел Пети получится одно и то же число для Васи). Это позволяет разбивать числа Пети и Васи на пары соответствующих друг другу, чтобы сравнить, каких чисел больше.

Однако, если число Пети оканчивается на 0 (например, 2110), то четырёхзначного числа не получится, так что у Пети будут "лишние" числа, не соответствующие никаким Васиным. (Если бы не это, все числа разбились бы по парам, то есть у Пети и Васи их было бы одинаково.)

Но это ещё не означает, что Петя придумал больше чисел: вдруг у Васи тоже есть свои "лишние", не соответствующие никаким Петиным, и их окажется больше? Докажем, что у Васи нет "лишних" чисел, то есть что любое число Васи окажется сопоставлено какому-то Петину числу. Итак, есть Васино число
\(abcd,~ a \ne 0,~ d=a+b+c\).
Докажем, что оно могло быть получено из какого-то Петиного числа заменой первой и последней цифр местами. Очевидно, что Петино число тогда будет выглядеть так:
\(dbca,\) при этом, чтобы оно было Петиным, нужно, чтобы было выполнено \(d \ne 0, ~ d=b+c+a\). Итак, покажем, что эти условия следуют из условий для числа Васи. Выполнение \(d=b+c+a\) очевидно, так как это просто по-другому записанное условие Васи \(d=a+b+c\). Докажем, что из условий Васи следует \(d \ne 0\). Действительно, так как цифры всегда больше или равны 0, а цифра \(a \ne 0\), то сумма \(d=a+b+c\) всегда больше 0.

Итак, каждому Васиному числу соответствует Петино, но у Пети есть ещё "лишние" числа, не соответствующие никаким Васиным. Значит, у Пети чисел больше.

4.

Сеня выписал в ряд несколько натуральных чисел, каждое из которых отличается от предыдущего либо на 10, либо в 7 раз. Сумма всех выписанных чисел равна 163. Какое наименьшее количество чисел мог выписать Сеня?

Указание Указание 2 Решение

Указание. Каждое число может отличаться друг от друга на 10 или в 7 раз в любую сторону, как большую, так и меньшую, но все они должны быть натуральными.
Придумайте подходящую последовательность из трёх чисел и покажите, что никакие последовательности из двух чисел не дают 163. Для этого обозначьте первое число в последовательности буквой и рассмотрите все 4 возможных случая таких последовательностей.

Указание 2. Чтобы уравнение было выполнено, обе его части должны одновременно делиться или не делиться нацело на одно и то же число (два числа не могут быть равны друг другу, если одно делится на что-то, а другое на это не делится).

Решение.

Подходит, например, такая последовательность: 51, 51 + 10 = 61, 61 - 10 = 51:
51 + 61 + 51 = 163.

Покажем, что меньше, чем из трёх чисел, такая последовательность состоять не может. Действительно, если числа только два, то может быть только 4 варианта последовательностей:
I) \(x + (x + 10) = 163;\)
\(2 x = 153,\) но слева стоит чётное число, а справа — нечётное, так что такого быть не может.
II) \(x + (x - 10) = 163;\)
\(2 x = 173\) — аналогично, не подходит.
III) \(x + 7 x = 163;\)
\(8 x = 163\) — слева число делится на 8, а справа — нет.
IV) \(x + x : 7 = 163\) — так как \(x\) &mdash натуральное число, то, чтобы при прибавлении к нему получилось целое 163, нужно, чтобы прибавлялось тоже целое, то есть чтобы \(x : 7\) было целым. Тогда \(x\) делится на 7, то есть \(x = 7 y,\) где \(y\) — тоже натуральное. Тогда уравнение представляется в виде
\(7 y + y = 163,\) что по аналогии с III) невозможно.
Итак, ни один из четырёх случаев не подходит, так что меньше, чем из трёх чисел, составить подходящую последовательность нельзя.

Ответ: 3.

5.

В лаборатории содержится 50 мышей, часть из них чёрные, а часть — белые. Они рассажены по 25 двухместным клеткам так, что ровно у половины белых мышей соседи по клетке чёрные. Докажите, что мышей нельзя пересадить так, чтобы ровно у половины чёрных мышей соседи по клетке были белыми.

Указание Решение

Указание. Может быть 3 разных способа наполнения клетки: обе мыши белые, обе чёрные, одна белая, другая — чёрная. Обозначьте количества клеток разных типов буквами и напишите условия того, как рассажены мыши изначально. При пересаживаниях количества клеток этих типов изменится, поэтому нужно выразить количество белых и чёрных мышей через количества разных клеток. Какое соотношение между количествами мышей должно быть выполнено, чтобы их можно было рассадить требуемым образом, и почему оно не может быть выполнено? Аналогично предыдущей задаче, посмотрите на делимость.

Решение. Пусть в \(x\) клетках обе мыши белые, в \(y\) клетках — одна белая и одна чёрная (тогда клеток с обоими чёрными мышами \(25 - x - y\)). По условию, половина белых мышей сидит в клетках с чёрными, то есть белых мышей всего \(2 y,\) а вторая половина из \(y\) мышей рассажена парами по \(x\) клеткам, откуда \(y = 2 x.\) Значит, всего белых мышей будет \(4 x,\) то есть их число делится на 4 (проще это можно было получить так: половина белых мышей сидит парами друг с другом, значит, половина делится на 2, а общее число белых мышей — на 4). По аналогичному соображению, чтобы можно было посадить чёрных мышей требуемым образом, их число тоже должно делиться на 4. Но тогда общее число мышей тоже должно делиться на 4, а их 50. Противоречие.

6.

В один ряд растёт по 300 деревьев, по 2 дерева каждого из 150 видов. Известно, что один из видов дерева — это осина. Между любыми двумя деревьями одного вида, кроме осины, растёт ровно 149 других деревьев. Докажите, что и между двумя осинами растёт ровно 149 деревьев.

Указание Указание 2 Решение

Указание. Докажите, что осины должны иметь в ряду номера в форме \(n\) и \(n + 150\), ровно как и пары деревьев остальных видов. Предположите, что это не так, и получите противоречие.

Указание 2. Очевидно, что чтобы между деревьями одного вида было 149 других деревьев, они должны иметь номера вида \(n\) и \(n + 150\). Так как всего деревьев в ряду 300, то одно дерево из пары каждого вида, кроме, может быть, осины, должно быть в первой половине (от 1 до 150), а другое — во второй. Пусть между осинами не 149 деревьев, то есть осины имеют координаты \(n\) и \(m,\) где \(m \ne n + 150\) (для определённости считаем, что \(m\) больше, чем \(n\)). Нужно доказать, что тогда условие задачи будет нарушено.

Решение. Если осины стоят не через 149 деревьев, то через 149 деревьев от одной из осин стоит дерево другого вида, а его пара должна находиться на месте этой осины. Получаем противоречие с условием.
Изложим эту идею аккуратно. Пусть осины имеют координаты \(n\) и \(m,\) где \(m \ne n + 150\) (для определённости считаем, что \(m\) больше, чем \(n\)). Нельзя просто рассмотреть дерево с номером \(n + 150,\) так как, если обе осины находятся во второй половине ряда, такого номера в ряду не будет существовать. Поэтому нужно посмотреть на дерево номер \(n + 150\), если \(n\) не больше 150, и номер \(n - 150\), если \(n\) больше 150. По предположению, это не осина, значит, тогда на месте \(n\) должно стоять дерево этого же вида. Но на нём стоит осина.

7.

В 99-этажном доме началось массовое переселение, при котором каждый житель переехал на один или два этажа вверх или вниз. До и после переселения на каждом этаже жил ровно один человек. Докажите, что какие-то два человека, раньше жившие через один этаж, теперь живут на соседних этажах.

Указание Решение

Указание. Посмотрите на нижние этажи дома. Рассмотрите все возможные варианты того, кто куда там переселяется, и в каждом случае найдите подходящие пары жильцов либо покажите, что в пределах нескольких первых этажей жильцы переселяются независимо от остальных, и можно эти несколько этажей "отбросить" и рассмотреть аналогичным образом следующие за ними.

Решение. Будем рассматривать разные случаи. Сначала рассмотрим, куда переходит житель 1 этажа. Под номером этажа будем писать номер этажа, куда переходит его житель, или оставлять пустое место, если в данном случае допускаются разные варианты.
1)
\( \begin{pmatrix}1 & 2 & 3 & \ldots \\ 3\end{pmatrix}\) Рассмотрим подслучаи, кто переходит на место 1:
1.1)
\( \begin{pmatrix}1 & 2 & 3 & \ldots \\ 3 & 1 & \end{pmatrix}\) Эта пара не подходит под условие, значит, нужно более подробное рассмотрение. Поскольку 3 может переходить на три разных этажа (2, 4 или 5, поскольку на 1 уже переходит житель со 2-го) — 3 варианта, а на 2 этаж можно переходить в нашем случае только с 3-го или 4-го этажей (2 варианта), то проще рассмотреть 2 варианта, кто переходит на 2 этаж:
1.1.1)
\( \begin{pmatrix}1 & 2 & 3 & \ldots \\ 3 & 1 & 2\end{pmatrix}\) Жители 1 и 3 этажей, жившие через этаж, теперь живут на соседних 3 и 2 этажах.
1.1.2)
\( \begin{pmatrix}1 & 2 & 3 & 4 & \ldots\\ 3 & 1 & & 2\end{pmatrix}\) Жители 2 и 4 этажей, жившие через этаж, теперь живут на соседних 1 и 2 этажах.
1.2)
\( \begin{pmatrix}1 & 2 & 3 & \ldots \\ 3 & & 1\end{pmatrix}\) Аналогично случаю 1.1, рассмотрим разные подслучаи того, кто переходит на 2 этаж. Но здесь уже известно, что с 1 и 3 этажей жители переходят не на 2, значит, на 2 этаж может перейти только житель 4, то есть вариант только один:
\(\begin{pmatrix}1 & 2 & 3 & 4 & \ldots\\3 & & 1 & 2\end{pmatrix}\) Анализируем дальше. Пока не написано, куда переходит житель 2 этажа. Но, так как на каждом этаже может жить только один человек, то он не может переселяться на 1 и 3. Значит, он переселяется на 4:
\(\begin{pmatrix}1 & 2 & 3 & 4 & \ldots\\3 & 4 & 1 & 2\end{pmatrix}\) Нужная пара по-прежнему не найдена. Но впервые в перестановке нет пустых клеток, значит, жители первых четырёх этажей меняются местами между собой, никак не затрагивая остальные этажи: со следующих после четвёртого этажей никто не уходит на первые четыре и не приходит с первых четырёх. Тогда можно просто "отпилить" нижние четыре этажа и рассматривать следующие этажи, как будто они самые нижние: рассмотрим разные случаи, в некоторых из которых найдём нужную пару жителей, а в некоторых отпилим этажи дальше. Нужно будет доказать, почему подходящая пара жителей найдётся, и не получится так, что все 99 этажей будут отпилены.
2)
\( \begin{pmatrix}1 & 2 & 3 & \ldots\\2\end{pmatrix}\) Аналогично, рассмотрим, кто переходит на 1 этаж. Это житель либо со 2-го, либо с 3-го этажа.
2.1)
\( \begin{pmatrix}1 & 2 & 3 & \ldots\\2 & 1\end{pmatrix}\) Жители первых двух этажей меняются местами, не затрагивая остальные этажи, поэтому "отпилим" два нижних этажа и рассмотрим следующие за ними этажи, как будто они самые нижние.
2.2)
\( \begin{pmatrix}1 & 2 & 3 & \ldots\\2 & & 1\end{pmatrix}\) Жители 1 и 3 этажей, жившие через этаж, перешли на соседние 2 и 1 этажи.

Итак, в каждом из случаев либо была найдена подходящая пара, либо были отрезаны 2 или 4 нижних этажа и рассмотрены следующие за ними этажи. Почему не случится так, что все 99 этажей будут отрезаны? 99 — нечётное число, а отрезают только по 2 либо 4 этажа, значит, все этажи отрезаны не будут. 98 этажей тоже не могут быть отрезаны, так как иначе остался бы один 99-й этаж, который по условию должен куда-то перейти, но переходить ему некуда, потому что на отрезанных этажах все меняются только между собой. Значит, после всех отрезаний останется не меньше, чем 3 последних этажа, а раз они не будут отрезаны, то в них будет реализован вариант без отрезания, то есть будет найдена подходящая пара.

8.

По узкому длинному коридору идут через равные промежутки 33 джентльмена, а им навстречу тоже через равные промежутки — 61 джентльмен. Когда два джентльмена встречаются, они пожимают друг другу руки, разворачиваются и идут обратно. Когда джентльмен добирается до какого-нибудь из концов коридора, он уходит домой. Через некоторое время все джентльмены, наконец, разошлись. Сколько рукопожатий было сделано?

Указание Указание 2 Решение

Указание. Подумайте, как переформулировать эту задачу, чтобы движение джентльменов было более простым?

Указание 2. Можно считать, что джентльмены не разворачиваются после рукопожатия, а проходят друг сквозь друга: ведь неважно, кто именно куда пойдёт, общее количество рукопожатий от этого не изменится.

Решение. Если считать, что джентльмены вместо разворотов проходят друг сквозь друга, то каждый из 33 джентльменов пожмёт руку 61 другому, мимо кого он пройдёт, то есть всего будет 33 · 61 = 2013 рукопожатий.