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

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

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

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

Задачка 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

6118792_original

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

Задачка 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. На сетке 2018x2019 отрезали по 1 клеточке в левом верхнем и правом нижнем углах. Можно ли замостить полученный лист доминошками 2x1? Теперь тот же вопрос про сетку 2019x2019 и также про 2018x2018.

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

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

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

Задачка 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. Поощрительные призы: термосы.

Метки:
Previous Entry Поделиться Next Entry

Записи из этого журнала по тегу «chtogdekogda»

  • Интересная история про 21 стопку монет и точные весы.

    Всем привет! Как уже успели заметить постоянные читатели этого блога, здесь периодически попадаются разные умственно-математические задачки,…

  • Adventures и «адвенчуристы» 20-го века.

    Мальчики и девочки, те из вас, кто прочитал мой предыдущий пост до самого конца, знают - я уже несколько дней на совершенно замечательной…

  • Ответы о мячах.

    Всем привет! То ли моя недавняя задачка о мячах была слишком сложной, то ли слишком простой, а может быть просто не было достойной мотивации типа…


Пойду лучше шить толстовку и программировать защиту KIS...
Пока это выглядит легче!

То ли я чего-то не понимаю, то ли первая совсем примитивная.
10^2019 + 1 на девять не делится - сумма цифр 2.
10^19 - 1 - это 19 девяток, т.е. на девять делится.
То есть первое на второе делиться не может.
Или там где-то знак перепутан?

Так я же предупреждал - в самом начале совсем простые. Потом посложнее.

Хм, ну если вначале действительно простые, то тогда со второй понятно:
Да, можно. После отрезания доску можно рассматривать как комбинацию двух полос 1*2018 и полотна 2016*2019. Каждая полоса, очевидно, покрывается 1009 костяшками, полотно покрывается 1008*2019 костяшками.

Неудивительно, что доказать невозможность у меня не получилось:)

Отлично!
Теперь тот же вопрос про доску 2019x2019.

А это еще проще: нечетное число клеток будет после отрезания, и можно на полотна не резать: сразу нет

Спасибо за задачки! Унесла в нору, буду ученикам показывать. Со ссылкой, конечно :)

Ну и противоположный вариант 2018x2018 - это тоже просто.

UPD:

> Со ссылкой, конечно

Задачки не мои! Это мне друзья накидывают...

Edited at 2019-02-01 10:33 (UTC)

недавно простую задачку на сообразительность предложил:
Требуется определить каковы запасы питьевой воды будут оставаться в бочке лежащей на боку строго горизонтально если известен её диаметр и высота, а измерить можем доступными предметами из коих есть только палка и линейка (таблицей,к примеру через 5 мм ) ;- )))

PS используя элементарные арифметические действия

получение приза

Elizaveta Yakovleva

2019-02-04 12:47 (UTC)

Добрый день! Благодарим Вас за участие и волю к победе! :) Напишите, пожалуйста, на почту elizaveta.yakovleva@kaspersky.com для обсуждения деталей получения приза!

Мне? За то, что я задачки унесла для учеников? Я же даже ответы писать не стала (потому что это было бы нечестно)...

Но от термоса не откажусь! Пошла писать на почту

2019*2019 решается или так же, как и с шахматной доской, через раскраску, или через четность:). Ее, очевидно, нельзя.
В общем виде x*(x+2n) нельзя, x*(x+2n-1) можно, n, как и x, натуральное.
Добавил: через раскраску - это общий метод для квадратных досок по аналогии с шахматной.
Еще добавил: нет, правильно так: x*(x+2n) нельзя, x*(x+2n+1) можно, n натуральное или ноль.

Третья - (+/-335,+/-338) и (+/-1009,+/-1010). Решение, естественно, не подбором, а следующим образом:
1. x<>0, ибо в этом случае y не может быть целым.
2. Если пара натуральных (x, y) удовлетворяет решению, то и все пары вида (+/-x, +/-y) тоже ему удовлетворяют, и наоборот. Таким образом, задача сводится к поискам натуральных x и y, y>x
3. (y-x)*(y+x) = 1*3*673, 673 - простое. Итого это 1*2019, 3*673
Отсюда либо y-x=1, y+x=2019, либо y-x=3, y+x=673.

Edited at 2019-02-01 10:49 (UTC)

Четвертая: Нет, остаток 6

Определение (поскольку есть ограничение по форматированию): если a=29, b=48, то ab=2948.

Лемма: если a+b делится на 9, то и ab делится на 9.
Доказательство леммы: ab=10^k*a+b=9*N*a+(a+b), где k - разрядность числа b, N - число из k единиц (11..11). Итого, остаток от деления a+b и ab на 9 совпадают.

Решение задачи: очевидно, что остаток от деления указанного числа на 9 совпадает с остатком от деления на 9 суммы всех чисел от 1 до 2019 включительно. А это, благодаря Гауссу, легко посчитать: 2019*2020/2 или 2019*1010 = 2039190. Данное число на 9 не делится, остаток 6.

Добавил - да, задача 3 решена в предположении что x2 означает x^2.


Edited at 2019-02-01 11:01 (UTC)

Пятая.
Пусть a, b - корни (возможно, a=b), a и b по условию целые.
По теореме Виета a*b=2^2019. Итого a и b должны быть степенями двойки с одинаковым знаком.
По той же теореме a+b = -2^2018. С учетом того, что a и b степени двойки с одинаковым знаком, такое возможно только при a=b=-2^2017. Но в этом случае их произведение будет 2^4034, а не 2^2019.

Шестая. Нет, не может.
Остаток от деления любого квадрата на 9 может быть 0, 1, 4 или 7. Это следует из того, что (9n+a)^2=81n^2+2*9*n*a+a^2=a^2 mod 9, а остатки от деления на 9 квадратов чисел с 0 до 8 - 0, 1, 4, 0, 7, 7, 0, 4, 1.
Остаток от деления на 9 числа 2019 - три, соответственно, ни один квадрат не может иметь такой суммы цифр, ибо остаток от деления квадрата на 9 равняется остатку от деления на 9 его суммы цифр (можно это не доказывать:)?)

Седьмую тоже решил, но пока выложу только ответ, наверное, чтобы и другие могли развлечься: 8. В следующем году ответ был бы 1.

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

Edited at 2019-02-01 12:40 (UTC)

ага, седьмая довольно известная в различных вариантах. Собственно, там будет чередование 1 или 8)

По восьмой:
1) 2^672 = 1(mod 673) - малая теорема,
2) 2^672 = 1(mod 3) - четная степень
3) из предыдущих 2х: 2^672 = 1(mod 2019)
4) (2^672)^3 = 1(mod 2019)
5) 2^3(2^2016) = 8(mod 2019)

То есть остаток 8.
Ага, для 2017 вообще здорово было бы)


Edited at 2019-02-02 18:08 (UTC)

По восьмой - ага, именно так я и решал. Та самая малая, а 2017 вообще простое (забавно получилось - простое число, дважды простое число, трижды простое число идут подряд. Правда, в следующем году уже так не получится).

Седьмая - ну да, несложно. Не rocket science. Правда, русский перевод данной фразы тут не подходит, ибо один из вариантов решения - как раз через бином Ньютона. Еще можно впрямую индукцией доказывать, что четные степени дают остаток 8, нечетные - 1.

Edited at 2019-02-03 11:26 (UTC)

победа в конкурсе

Elizaveta Yakovleva

2019-02-04 12:40 (UTC)

Добрый день! Поздравляем Вас с победой в конкурсе! :) Напишите, пожалуйста, на почту elizaveta.yakovleva@kaspersky.com для обсуждения деталей получения приза!

Задачка 2

Можно. Всё можно. Только в некоторых случаях последнюю доминошку надо будет разрезать на два кусочка.

Можно мне сразу два приза: и за волю к победе, и за остроумие?
Я очень волевая. А иногда ещё и остроумная. Правда, не в том смысле, который требуется для решения задач :(

получение приза

Elizaveta Yakovleva

2019-02-04 12:43 (UTC)

Добрый день! Благодарим Вас за участие и волю к победе! :) Напишите, пожалуйста, на почту elizaveta.yakovleva@kaspersky.com для обсуждения деталей получения приза!

Задача 4 (альтернатива без лемм и Гаусса).

Найдем сумму конкатенаций (если нигде не ошиблась):
1. от 1 до 9: 45
2. от 1 до 99: (45*10+10*(1+2+..+9)) = 2*45*10
3. от 1 до 999: 2*45*10*10 + 100(1+2+...+9) = 3*45*100
4. от 1 до 1999: 3*45*100*2 + 1*1000 = 9(3*5*100*2 +111)+1
5. от 1 до 2019: 9(3*5*100*2 +111)+1 + 20*2 +45 +55 = 9(3*5*100*2 +111)+1 + (9*4 +4) +9*5 + (9*6 +1) = 9*m +6

То есть полученное число не делится нацело на 9. Остаток от деления: 6.

получение приза

Elizaveta Yakovleva

2019-02-04 12:42 (UTC)

Добрый день! Поздравляем Вас с получением второго места в конкурсе! :) Напишите, пожалуйста, на почту elizaveta.yakovleva@kaspersky.com для обсуждения деталей получения приза!

(Удалённый комментарий)
Не работает: 1 2 3 4 5 6 7 8 9.
1+9=10 и не делится.

Re: Задача 4

ua6em

2019-02-21 16:01 (UTC)

;-)))

Да уж, старею да и это не с MBR разбираться по молодости ...
Надеюсь Вашу статью в журнале помните...а если порыться в загашнике пожалуй и найду её )))

PS А вот статистически, сказав не делится % попадания более 80 )))

Edited at 2019-02-21 16:15 (UTC)

?

Log in

No account? Create an account