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

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

Занятие 7. Делимость

1.

Ведьма Клара приобрела в лавке несколько лягушек по 35 центов, несколько бутылочек бесовского зелья по 1 доллару 40 центов за штуку и змею за 2 доллара 80 центов. Колдун сказал, что с него 20 долларов 50 центов. Ведьма Клара превратила колдуна в мышку. Докажите, что было за что.

Решение

Решение. $0.35, $1.40 и $2.80 кратны $0.35, а $20.50 не кратно $0.35.

2.

Водяной построил кикимор в колонну по 4, но при этом кикимора Дуся осталась лишней. Тогда водяной построил кикимор в колонну по 5. И снова Дуся осталась лишней. Когда же и в колонне по 6 кикимора Дуся в осталась лишней, водяной посулил ей болото вне очереди, после чего в колонне по 7 Дуся нашла себе место и никого лишнего не осталось. Какое наименьшее количество кикимор могло быть у водяного?

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

Ответ. 301.

Решение. Число кикимор на 1 больше некоторого числа, кратного 4, 5 и 6 (т.е. кратного 60). Из чисел, кратных 60, надо выбрать наименьшее из тех, у которых следующее делится на 7. Перебираем: числа 61, 121, 181 и 241 не делятся на 7, а вот 301 уже делится.

3.

Можно ли торт Клары со сторонами 2,3×3,5 см разрезать на прямоугольнички 0,08×0,07 см?

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

Ответ. Нет.

Решение. Площадь всего торта равна 23·7·5·0,01=23·7·5²·2·0,0001 см², а площадь каждого прямоугольничка равна 8·7·0,0001 см². Видно, что второе число кратно 8·0,0001 см², а первое нет (в произведении нет 8).

4.

Кикимора Дуся думает, что v³ + 2v делится на 3 для любого натурального v. В правильном ли направлении думает Дуся?

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

Ответ. Да.

Решение. v³ + 2v = v(v² + 2). Рассмотрим возможные остатки от деления числа v на 3.

1. v = 3k
2. v = 3k + 1 ⇒ v² + 2 = 9k² + 6k + 3
3. v = 3k + 2 ⇒ v² + 2 = 9k² + 12k + 6

Видно, что во всех трех случаях число v³ + 2v = v(v² + 2) будет делиться на 3.

5.

Ведьма Клара ищет два последовательных натуральных числа, сумма цифр каждого из которых делится на 11. Помогите ей.

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

Ответ. Например, 5599999 и 5600000 (могут быть и другие решения).

Решение. Если два последовательных числа отличаются только последней цифрой, то их суммы чисел отличаются на 1, а стало быть, не могут делиться на 11 одновременно. Еще один случай – когда при добавлении к числу 1 несколько девяток на конце превращаются в нули, а следующая за ними цифра увеличивается на 1 (например, 699 и 700). Сколько нам нужно таких девяток? Если девятка одна, то суммы цифр отличаются на 9 − 1=8, если две, то на 2·9 − 1=17, если три, то на 3·9 − 1=26, если четыре, то на 4·9 − 1=35, если пять, то на 5·9 − 1=44 и т.д. Необходимо, чтобы эта разность делилась на 11. Это выполняется, например, при пяти нулях на конце большего из чисел. Осталось придумать для него «начало», сумма цифр которого делилась бы на 11. Например, 56.

6.

Лешие выходят из леса парами. В каждой паре идет леший-мальчик и леший-девочка, причем у мальчика либо в два раза больше веток, либо в два раза меньше веток, чем у девочки. Может ли всего у леших быть 100 веток?

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

Ответ. Нет.

Решение. В каждой паре у одного из леших k веток, а у другого 2k веток, значит, у обоих вместе 3k веток. То есть общее число веток, собранных лешими, должно делиться на 3. А 100 не делится на 3.

7.

Имеется три компьютерных пня. Если одному из них на вход дать лист, где написаны числа (m, n), то он выдаст лист с числами (n, m), если другому – выдаст (n + m, n), третьему – выдаст (m − n, n). Можно ли таким образом из листа (42, 21) получить лист (19, 84)?

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

Ответ. Нет.

Решение. При операциях, выполняемых пнями, сохраняются общие делители чисел m и n. 42 и 21 делятся на 21, а 19 и 84 нет (они даже взаимно простые).

8.

Водяной задумался: «На сколько нулей заканчивается число 2000!?» Помогите ему.

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

Ответ. На 499 нулей.

Решение.

Пояснение: Для тех, кто не знает: 2000!=1·2·\3·…·1999·2000 (говорят: две тысячи факториал). Так что в условии задачи «!» – это знак факториала, а «?» – знак препинания.

Количество нулей на конце числа равно максимальной степени 10, на которую это число делится. Каждая десятка в произведении получается как произведение двойки и пятерки, присутствующие в разложении сомножителей на простые множители. Количество таких пар и надо посчитать. Для этого достаточно посчитать только пятерки, а двоек им заведомо хватит (ведь среди чисел от 1 до 2000 четных гораздо больше, чем кратных 5). Чисел, кратных 5, будет 2000:5=400, а среди них еще 2000:25=80 делятся на 25=5², а среди этих еще 2000:125=16 делятся на 125=5³, а среди них еще [2000:625]=3 делятся на 625=5⁴. (Здесь [x] - целая часть числа х, то есть наибольшее целое число, не превосходящее х. В частности, [2000:625] - это неполное частное от деления 2000 на 625. Кстати, по определению [5,45]=5, но [ − 5,45]= − 6.) Итого в разложение числа 2000! на простые множители 5 входит в степени 400+80+16+3=499. Столько нулей и будет на конце числа 2000!

9.

На поле Чудес растут деревья с золотыми монетами. Каждую ночь на каждом дереве вырастает по одной новой монете. 1 марта на деревьях было всего 1000 монет. В один из дней марта Буратино посадил еще одно дерево, и 31 марта на деревьях оказалось всего 2000 монет. В какой день Буратино посадил дерево?

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

Ответ. 21 марта.

Решение. Если «старых» деревьев было n, то на них за месяц выросло 30n монет. Если Буратино посадил свое дерево за k ночей до 31 марта, то на нем выросло еще k монет, причем k ≤ 30. Всего за месяц на всех деревьях выросло 30n + k=1000 монет. Отсюда, помня, что k ≤ 30, находим n=30, k=10. Стало быть, Буратино посадил свое дерево за 10 ночей до 31 марта, то есть 21 марта.

10.

Кикимора Дуся думает, что если натуральные числа a, b и c таковы, что числа a + b, b + c, a + c – простые, то среди них найдутся равные. Права ли Дуся?

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

Ответ. Да.

Решение. Допустим, a четно. Тогда b и c должны быть нечетными (ведь числа a + b и b + c должны быть простыми, а равны 2 они быть уже не могут). В этом случае b + c четно и может быть простым, только если оно равно 2. Поскольку b и c – натуральные, они могут равняться только 1, то есть они одинаковы. Если же а нечетно, то b и c должны быть четными (или 1, если a=1). Но тогда b + c – снова четное, и мы приходим к предыдущей ситуации.

11*

Найдите последнюю цифру числа:

а)

2001²⁰⁰¹;

б)

549⁴⁹;

в)

345673³⁷⁶⁵⁴³;

г)

77⁷⁷⁷⁷.

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

Ответ. а) 1; б) 9; в) 7; г) 7.

Решение. Идея во всех пунктах одинаковая. Вспомнив правило умножения в столбик, можно понять, что последняя цифра произведения двух чисел – это последняя цифра произведения двух последних цифр этих чисел. В пункте а) единица все время будет умножаться сама на себя, поэтому получится единица. В пункте б) 9·9=81, …1·9=…9 и т.д., то есть нечетные степени будут оканчиваться на 9, а четные – на 1. в) У числа 3 степени в зависимости от делимости на 4 могут заканчиваться на 3, 9, 7 и 1. Поскольку 376543 делится на 4 с остатком 3, последняя цифра этой степени будет 7. г) У степеней семерки тоже 4 возможных окончания: 7, 9, 3, 1, выбор вновь зависит от того, с каким остатком показатель степени делится на 4. Но 77 в любой степени дает остаток 1 при делении на 4 (можно проверить, что при перемножении двух чисел, делящихся на 4 с остатком 1, получится число с таким же свойством). Значит, последняя цифра 7.

12*

Найдите две последние цифры числа

а)

1999²⁰⁰⁰;

б)

16²⁰⁰⁰.

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

Ответ. а) 01; б) 56.

Решение. Вновь воспользуемся правилом умножения в столбик. Последние две цифры произведения двух чисел – это две последние цифры произведения чисел, составленных из их двух последних цифр (стоящих в том же порядке, что в исходном числе). Аналогично предыдущей задаче, переберем возможные варианты. В пункте а) это только 99 и 01, а в пункте б) 16, 56, 96, 36, 76, 16 (в зависимости от остатка от деления показателя степени на 6). 1998 делится на 6 нацело, значит, 2000 дает при делении на 6 остаток 2.

13*

Найдите последнюю ненулевую цифру числа 2000!

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

Ответ. 6.

Решение. Будем вновь использовать правило умножения в столбик, только вместо последней цифры числа будем каждый раз брать последнюю ненулевую, а вместо возведения в степень будем вычислять факториал. Если не полениться все это написать, получится вот что: (1 2 6 4 2 2 4 2 8 8)( 8 6 8 2 1 6 2 6 4 4 )(4 8 4 6 3 8 6 8 2 2 )(2 4 2 8 4 4 8 4 6 6)… и дальше снова то же самое. То есть через каждые 40 сомножителей последняя цифра повторяется. У числа 2000! это будет 6.

14*

Назовем автобусный билет с шестизначным номером счастливым, если сумма цифр его номера делится на 7. Могут ли два билета подряд быть счастливыми?

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

Ответ. Да, например, 609999 и 610000.

Решение. Полностью аналогично решению задачи 5.

15*

В последовательности цифр каждая цифра, начиная с пятой, равна последней цифре суммы четырех предыдущих. Последовательность начинается с цифр 1234096… Может ли в ней встретиться комбинация цифр 1999?

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

Ответ. Нет.

Решение. Заменим в нашей последовательности четные числа нулями, а нечетные единицами. При этом по-прежнему каждая цифра, начиная с пятой, равна последней цифре суммы четырех предыдущих (сложение осуществляется по правилу: 0+0=0, 0+1=1+0=1, 1+1=10, то есть как в двоичной системе счисления). Выпишем начало последовательности: (10100)(10100)… Видно, что одна и та же комбинация цифр будет повторяться в этой последовательности до бесконечности, и никаких других комбинаций появиться не может. 1999 превратилось бы в 1111, а такой комбинации, очевидно, в последовательности нет.