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

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

Занятие 3. Ацнок с зилана

Бывает, что задом наперед ходить удобнее…

Рак

1.

Предложил черт лодырю: «Всякий раз, как перейдешь этот волшебный мост, твои деньги удвоятся. За это ты, перейдя мост, должен будешь отдать мне 40 рублей». Трижды перешел лодырь мост — и остался совсем без денег. Сколько денег было у лодыря первоначально?

Ответ Решение

Ответ. 35 рублей.

Решение.

После последнего перехода моста у лодыря стало 40 рублей, которые он в итоге и отдал черту. Значит, перед этим у него было 40:2=20 рублей, до уплаты «налога» во второй раз у него было 20+40=60 рублей. До второго перехода моста у лодыря было 30 рублей, до первой уплаты «налога» — 70 рублей, а перед первым переходом моста — 35 рублей.

Дополнительный вопрос: а сколько денег нужно иметь лодырю первоначально, чтобы такая сделка была для него выгодной? (Ответ: больше 40 рублей)

2.

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

Ответ Решение

Ответ. 127 гусей.

Решение.

На последнем озере село половина всех гусей и еще полгуся и оказалось, что это все летевшие гуси. Значит, полгуся — это половина всех гусей, подлетевших к последнему озеру, а всего их было 0,5·2=1 гусь. На предпоследнем озере село половина всех гусей, подлетевших к нему, и еще полгуся, а еще один гусь полетел на последнее озеро. Значит, к этому озеру подлетело (1 + 0,5)·2=3 гуся. Рассуждая таким образом дальше, получим, что к пятому озеру подлетело 7 гусей, к четвертому — 15 гусей, к третьему — 31 гусь, ко второму — 63 гуся и, наконец, к первому — 127 гусей.

Замечание 1. Хотя в условии задачи фигурируют «полгуся», на самом деле все время летает и садится целое число гусей, так что описанная в задаче ситуация вполне могла иметь место в реальной жизни.

Замечание 2. Заметим, что 1=2¹ − 1, 3=2² − 1, 7=2³ − 1, …, 127=2⁷ − 1. Подумайте, почему так получилось.

3.

Трем братьям дали 24 бублика так, что каждый получил на три бублика меньше, чем ему лет. Меньший брат был сообразительный и предложил поменять часть бубликов: «Я, — сказал он, — оставлю половину бубликов, а другую разделю между вами поровну; после этого средний брат также оставит половину бубликов, а другую разделит поровну между мной и старшим братом. В конце старший брат поделит так же». Так они и сделали. Оказалось, что все получили поровну. Сколько лет каждому брату?

Ответ Решение

Ответ. Старшему брату 16 лет, среднему 10, а младшему — 7.

Решение. Раз бубликов всего было 24, то в конце каждый из братьев получил по 24:3=8 бубликов. Перед тем, как старший брат разделил между своими братьями половину бубликов, у него было 8·2=16 бубликов, значит, каждому брату он отдал по 8:2=4 бублика. Значит, до этого у них было по 8-4=4 бублика. Проведя аналогичные рассуждения еще два раза, получим следующее. Перед тем, как бубликами поделился средний брат, у него было 8 бубликов, у младшего — 2 бублика, а у старшего — 14. Ну а в самом начале у старшего брата было 13 бубликов, у среднего — 7, а у младшего — 4. Теперь несложно посчитать, сколько каждому из братьев лет.

4.

За круглым столом сидят А, В, С, D. Каждый из них имеет по несколько яблок. Затем А дает каждому из остальных по столько яблок, сколько тот уже имел (тем самым удвоив число яблок у всех, кроме себя ). После этого В делает тоже самое, и так далее до D. Когда они закончили, у каждого оказалось по 32 яблока. Кто сколько яблок имел в начале?

Ответ Решение

Ответ. У A было 66 яблок, у B — 34, у C — 18, у D — 10.

Решение. Рассуждения очень похожи на те, которые мы проводили в предыдущей задаче. Если в конце концов у каждого оказалось по 32 яблока, значит, перед этим А, В и С получили половину своих яблок, то есть по 16 яблок, от D. То есть всего D раздал 16·3=48 яблок, а до этого у него было 32+48=80 яблок. Далее проводим аналогичные рассуждения еще несколько раз. Перед тем, как яблоки раздавал С, у сидящих за столом было, соответственно, 8, 8, 72 и 40 яблок; перед тем, как раздавал В, у них было 4, 68, 36 и 20 яблок соответственно, а в самом начале — 66, 34, 18 и 10 яблок.

5.

По кругу расставлены 9 нулей и единиц, причем не все они равны. За один ход между каждыми двумя соседними числами записывается 0 в случае, если они равны, и 1 в противном случае. Далее старые числа стираются. Могут ли в конце все числа оказаться равными?

Ответ Решение

Ответ. Нет.

Решение. Решим эту задачу методом «от противного», то есть исходя из утверждения, противоположного тому, что мы пытаемся доказать, придем к противоречию. Допустим, в конце концов все числа оказались равными 0. Тогда перед этим по кругу тоже было написано 9 одинаковых чисел. Случай, когда это тоже нули, рассматривать неинтересно: в этом случае ничего не меняется. Рассмотрим только случай, когда все числа, стоящие по кругу, равны 1. Это означает, что из чисел, написанных по кругу до этого, никакие два соседних не были равны. Попробуем их выписать. Для начала на любом месте напишем 0 (или 1, это неважно). Тогда дальше по часовой стрелке будут стоять числа 1, 0, 1, 0, 1, 0, 1, 0. Начинали мы с нуля, а девятое число тоже оказалось нулем (если бы мы начинали с единицы, в конце получилась бы единица). Значит, в этом круге два нуля (или две единицы) оказались рядом, а такого быть не могло. Полученное противоречие доказывает, что наше предположение было неверно, и все числа нельзя сделать равными.

6.

По кругу написаны числа: 1, 0, 0, 0, 0, 0. Разрешается одновременно увеличивать на 1 два любых соседних числа. Можно ли сделать все 6 чисел равными? А если разрешается одновременно увеличивать на 1 три соседних числа?

Примечание: в условиях задач, которые выдавались на занятии, формулировка этой задачи выглядела несколько иначе. Второй вопрос был сформулирован не совсем ясно: «А если три соседних?» Этот вопрос следует понимать именно так, как написано здесь. На занятии соответствующие пояснения были даны.

Ответ Решение

Ответ. Нет в обоих случаях.

Решение.

Рассмотрим сначала первый случай. Заметим, что при добавлении 1 к двум соседним числам четность суммы всех чисел сохраняется. Изначально эта сумма равна 1, а стало быть, нечетна. Если бы удалось все шесть чисел сделать равными, то их сумма делилась бы на 6, а значит, была бы четной. Этого мы с помощью наших действий добиться не сможем. Во втором случае вместо четности суммы будем рассматривать остаток от ее деления на 3. Он сохраняется при добавлении 3 к трем соседним числам. Изначально сумма 1 дает остаток 1 при делении на 3, а сумма шести одинаковых чисел делится на 6, а значит, и на 3 с остатком 0.

Замечание 1. Аналогичные рассуждения можно было бы провести в случае, когда разрешено прибавлять по 1 к двум (соответственно, трем) любым, а не только соседним числам. На то, как изменяется сумма всех чисел при наших действиях, это не влияет. Так что мы решили даже несколько более общую задачу.

Замечание 2. При решении этой задачи мы нашли свойство делимости на 2 (соответственно, 3), которое не изменяется при наших действиях. Такое свойство (или величина) называется инвариантом. Инварианты часто используются для доказательства невозможности добиться требуемого результата при помощи заданного набора действий. Для этого находится свойство или величина, не изменяющаяся при разрешенных действиях, но различающаяся у начальной и конечной (требуемой) конфигурации. Правда, если эта величина оказалась одинаковой у начальной и конечной конфигурации, это еще ничего не означает. В этом случае нужно либо искать другой инвариант для доказательства невозможности, либо пытаться при помощи некоторой последовательности разрешенных действий все же получить конечный результат.

7.

Расставьте различные натуральные числа в таблицу 2×3 (2 строки, 3 столбца) так, чтобы произведения в столбцах были равны, и суммы в строках тоже были равны (но суммы могут отличаться от произведений).

Ответ Решение

Ответ. Это можно сделать, например, так (могут быть и другие варианты):

20	2	15
3	30	4

Решение. Конечно, решение этой задачи включает в себя перебор. Однако его можно немного упростить. В качестве произведения элементов в столбце нужно выбрать такое число, которое можно разложить на два неравных множителя хотя бы тремя способами (в нашем примере это число 60=20·3=30·2=15·4=12·5=10·6=60·1). Дальше уже нужно выбирать, какие пары использовать, а какие нет, и как расставлять числа одной пары. Понятно, что бóльшие сомножители в каждой паре не все должны быть в одной строке. Еще можно использовать четность суммы. Скажем, если в каком-то столбце верхний сомножитель четный, а нижний нечетный, то хорошо бы в другом столбце сделать наоборот, а в третьем оба сомножителя взять четными (сделать оба нечетными не получится, а если четность будет разной, то суммы чисел в верхней и нижней строке тоже будут иметь разную четность).

8*.

Однажды царь наградил крестьянина яблоком из своего сада. Пошел крестьянин к саду и видит: весь сад огорожен тройным забором, в каждом заборе только одни ворота, и в каждых воротах стоит сторож. Подошел крестьянин к первому сторожу и показал ему царский указ, а сторож ему в ответ: «Иди возьми, но при выходе отдашь мне половину тех яблок, что несешь, и еще одно». То же ему сказали второй и третий сторож. Сколько яблок должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко?

Ответ Решение

Ответ. 22 яблока.

Решение. Эта задача очень похожа на задачу №1. До «расплаты» с первым сторожем у крестьянина должно остаться (1 + 1)·2=4 яблока, до «расплаты» со вторым сторожем — (4 + 1)·2=10 яблок, а до «расплаты» с третьим — (10 + 1)·2=22 яблока.

9*.

Три мальчика делили 120 фантиков. Cначала Петя дал Ване и Толе столько фантиков, сколько у них было. Затем Ваня дал Толе и Пете столько сколько у них стало. И наконец Толя дал Пете и Ване столько, сколько у них к этому моменту имелось. В результате всем досталось поровну. Сколько фантиков было у каждого в начале?

Ответ Решение

Ответ. 65 фантиков было у Пети, 35 у Вани и 20 — у Толи.

Решение. Решение аналогично решению задачи №4.