Мат-задачки-2019, часть 3.

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

Задачка 1. Делится ли 10^2019 + 1 на 10^19 — 1 нацело, то есть без остатка?

Задачка 2. На сетке 2018×2019 отрезали по 1 клеточке в левом верхнем и правом нижнем углах. Можно ли замостить полученный лист доминошками 2×1?
Решили? Теперь тот же вопрос про сетку 2019×2019 и также про 2018×2018.

Задачка 3. Найти все целые решения уравнения: х2 + 2019 = y2

Задачка 4. Делится ли нацело на 9 вот такое число: 12345678910111213…201720182019

Задачка 5. Доказать, что уравнение x^2 + (2^2018)*x + 2^2019 = 0 не имеет целых решений.

Задачка 6. Может ли число, сумма всех цифр которого равна 2019, быть квадратом целого числа. Например, 11 в квадрате есть 121, сумма его цифр равна 4. То есть, для числа 4 решение есть. Существует ли оно для 2019?

Задачка 7. На большой доске мелким почерком написано число, равное 8^2019. У этого числа вычисляется сумма цифр, у полученного числа вычисляется опять сумма цифр и т.д. до тех пор пока не получится одна цифра. Что это за цифра?

Задачка 8. Найти без калькулятора (счёты можно) остаток от деления: 2^2019 / 2019

А вот и решения:

Задачка 1. Делится ли 10^2019 + 1 на 10^19 — 1 нацело, то есть без остатка?

10^19 – 1 есть 100…000 – 1 = 999…999 , оно состоит из 18-ти девяток и делится на девять.
10^2019 + 1 является вот таким числом: 100…0001 , сумма всех его цифр равна двум и на девять оно делиться не может (критерий делимости числа на 3 и 9: сумма всех цифр числа должно делиться на 3 или на 9).

То есть, деление нацело невозможно.

Задачка 2. На сетке 2018×2019 отрезали по 1 клеточке в левом верхнем и правом нижнем углах. Можно ли замостить полученный лист доминошками 2×1? Теперь тот же вопрос про сетку 2019×2019 и также про 2018×2018.

2018×2019 решается очевидно. Сначала кладём доминошки на две крайние 2019-полосы, где отрезано по одной клетке, то есть осталось 2018 клеток. Остаётся сетка размером 2018×2016, которую можно замостить в любом направлении параллельными доминошками. Ответ «можно».

2019×2019 ответ «нельзя», поскольку после отрезания остаётся нечётное количество клеток.

2018×2018 чуть сложнее и ответ тоже «нельзя». Доказательство простое. Нужно закрасить все клетки поочерёдно в чёрный и белый цвет, как на шахматной доске. Поскольку каждая доминошка закрывает один чёрный и одну белую клетку, то любое покрытие сетки доминошками закрывает одинаковое количество клеток. Но противоположные клетки на сетке имеют одинаковые цвета, то есть на сетке осталось неодинаковое число чёрных и белых клеток. Ответ: невозможно.

Задачка 3. Найти все целые решения уравнения: х^2 + 2019 = y^2

Решение уравнения сводится к следующему:

2019 = y^2 – x^2 = (y+x) * (y-x)

2019 раскладывается на следующие натуральные (целые положительные) множители:

2019 = 1 * 3 * 673

Отсюда две системы уравнений:

y + x = { 1, 3, 673, 2019 }
y – x = { 2019, 673, 3, 1 }

У которых 2 решения в натуральных числах: { x, y } = { 1009, 1010 }, { 335, 338 }. Поскольку отрицательные значения тоже подходят, то всего получается 8 пар решений.

Задачка 4. Делится ли нацело на 9 вот такое число: 12345678910111213…201720182019

Очень просто. Надо подсчитать сумму всех цифр в числе и проверить результат на критерий делимости на 9. Если сумма цифр делится на 9, то и исходное число тоже делится на девятку. У задачки есть несколько несложных решений. Например, поскольку мы проверяем делимость на 9, то цифры можно складывать группами: у ‘abcd’ результат проверки по ‘a+b+c+d’ будет совпадать с ‘ab+cd’.

abcd = 1000*a + 100*b + 10*c + d = (a+b+c+d) + 999*a + 99*b + 9*c

Девятки сокращаются при делении на 9 – и всё. Таким образом, надо проверить делимость на 9 арифметической прогрессии 1,2,…,2019. Она равна:

2019*(2019+1)/2 = 2019*1010 = 2039190 (или 3*673*2*5*101)

На 9 никак не делится.

Второй вариант решения: разбить исходное очень длинное число на группы по 9:

123456789
101112…18
192021…27

Первая группа делится на 9, поскольку сумма её цифр равна 45. Каждая последующая группа получается из предыдущей прибавлением к каждому элементу группы девятки, то есть, они все тоже делятся на 9. В числе 123…20182019 всего 224 группы. Остаётся группа из трёх последних элементов: 201720182019. Сумма цифр на 9 не делится. Всё.

Задачка 5. Доказать, что уравнение x^2 + (2^2018)*x + 2^2019 = 0 не имеет целых решений.

Исходное уравнение трансформируется следующим образом:

x^2 + (2^2018)*x + 2^2019 = 0 // исходное
x^2 + 2*(2^2017)*x + (2^2017)^2 — (2^2017)^2 + 2^2019 = 0 // преобразуется к форме ‘x^2 + 2*x*a + a^2 = b’
x^2 + 2*(2^2017)*x + (2^2017)^2 = 2^4034 — 2^2019
(x + 2^2017)^2 = 2^2019 * (2^2015 — 1) // что есть ‘(x + a)^2 = b’

Теперь даже невооружённым глазом видно, что никаких целых корней тут быть не может.

Есле же невооружённым не видно, то решение уравнения получается вот такое:

x = √ (2^2019 * (2^2015 — 1)) – 2^2017

Квадратный конень из ‘2^2019 * (2^2015 – 1)’ никак не может быть целым числом, поскольку под корнем двойка в нечётной степени.

Задачка 6. Может ли число, сумма всех цифр которого равна 2019, быть квадратом целого числа. Например, 11 в квадрате есть 121, сумма его цифр равна 4. То есть, для числа 4 решение есть. Существует ли оно для 2019?

Тоже очень просто. Предположим, что есть некое число ‘x^2’ сумма цифр которого равна 2019. Но по критерию делимости на 3 и на 9 получается, что ‘x^2’ делится на 3 и не делится на 9 (поскольку 2019 делится на 3, но не на 9). То есть, в разложении ‘x’ на множители есть тройка, но тогда в разложении ‘x^2’ должна быть девятка. Противоречие. То есть, такого числа не существует.

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

Задачка 7. На доске написано число, равное 8^2019. У этого числа вычисляется сумма цифр, у полученного числа вычисляется опять сумма цифр и т.д. до тех пор пока не получится одна цифра. Что это за цифра?

Эта цифра восемь. Вот почему: любое число записывается как сумма его десятичных разрядов, умноженных на степени десятки. Например, ‘123’ записывается вот так: 1*10^3 + 2*10^2 + 3. Сумма всех цифр числа получается «удалением лишних десяток», то есть:

123 = 1 + 2 + 3 + ( 1*999 + 2*99 )

Но это же просто деление с остатком на 9. То есть, 8^2019 надо разделить с остатком на девятку. Для этого посмотрим на последовательность 8^x по модулю 9:

8^1 = 8 (mod 9)
8^2 = 64 = 1 (mod 9)
8^3 = 8 * 8^2 (mod 9) = 8*1 (mod 9) = 8 (mod 9)
8^4 = 8 * 8^3 (mod 9) = 8*8 (mod 9) = 1 (mod 9)

То есть, 8^x поочерёдно принимает значения 1 и 8. Нечётные – восмёрки. 8^2019 даёт восьмёрку.

Задачка 8. Найти без калькулятора (счёты можно) остаток от деления: 2^2019 / 2019

Здесь сложнее и требуется некоторое количество несложных вычислений.

1) Последовательность 2^x (mod 2019) когда-то зациклится. То есть, найдутся ‘a’ и ‘b’ такие, что:

2^a = 2^b (mod 2019).

То есть,

2^b* (2^c — 1) = 0 (mod 2019)

// понятно, что ‘a>b’ и ‘c=a-b’. Они взаимопростые, посему существует

2^c = 1 (mod 2019).

Теперь надо его найти.

2) Чтобы найти эту самую ‘це’ надо достать счёты, поскольку придётся попотеть арифметически. Поехали, считаем остатки ‘2^x’ при делении на 2019:

1 2 4 8 16 32 64 128 256 512 1024 = 2^10 (mod 2019)
— первый десяток даже считать не надо, это нужно помнить наизусть.

29 58 116 232 464 928 1856 1693 1367 715 = 2^20 (mod 2019)
— второй десяток считается тоже не очень сложно, предыдущее надо просто умножить на 2 и вычесть 2019, если оно больше.

1430 841 1681 1345 671 1342 665 1330 641 1282 (2^30)
— тут уже менее приятные числа для вычислений, но тоже ничего этакого.

545 1090 161 322 644 1288 557 1114 209 418 (2^40)
836 1672 1325 631 1262 505 1010 1 (2^48)
— баммм! Вот оно! Длина цикла = 48.

248 = 1 (mod 2019)

Сколько там циклов в 2019 умещается?

2019 = 48*42 + 3

То есть,
22019 = 2(42*48 + 3) = (142) * (23) = 8 (mod 2019)

Всё. Ответ: тоже восемь.

3) Можно и меньшим количеством операций, если не боитесь умножать и делить многозначные числа. Поскольку мы знаем степени двойки наизусть, то можно искать цикл с шагом 10. То есть, считать не все остатки от деления степени двойки на 2019, а 2^20, 2^30, 2^40, 2^50 — каждый раз умножая предыдущий остаток на 1024 и вычисляя остаток от деления на 2019. За 4 умножения и 4 деления наткнёмся на остаток, равный степени двойки. Всё.
—8<—

По результатам математического марафона выходного дня отличились следующие участники: sir_derryk (первое место, молодца!) и Яна Барсукова (второе место). За прочие подвиги и попытки участия :) — mama_gremlina и olly_ru.

Победители награждаются корпоративно-зелёными призами из магазина Labshop, куда, кстати, недавно поступило много нового и прикольного, например вот такие «мидори-кумные» кигурумии домашние тапочки.

Первое(ые) место(а): толстовка + защита KIS. Поощрительные призы: термосы.