Цифровой 2018 — часть 3.

Всем привет,

Как я уже понял, для активного решения интересных задачек требуется некоторая небольшая мотивация — так мне не жалко! Но об этом чуть ниже. Для начала, по просьбам трудящихся, возжелавших задачек для решения в мозгу, то есть совсем без программирования и даже без карандаша с бумагой — их есть у нас. Задачки, которые не требуют компьютера. Более того, карандашом и бумагой они решаются быстрее, чем клавиатурой и компилятором. Вот одна такая, которую я решил чисто в голове.

Задачка1 ->
Есть некое очень красивое 10-значное число. Первый (самый левый) знак в этом числе — общее количество нулей в этом же числе. Второй знак — количество единиц. Третий — двоек. И так далее. Последняя цифра в этом числе — количество девяток в его записи. Что же это за число такое?

Ещё раз — для решения требуется всего-то голова и немного мозга в ней. Дерзайте :)

Вторая задачка немного сложнее. Не в каждой голове найдётся её решение. Хотя известны арифметические гении, которые умели перемножать в уме многозначные числа. Итак,

Задачка2 ->
Существует ли такое натуральное (целое ненулевое положительное) число, дающее при перемножении с 2018 результат, который всё в той же десятичной записи состоит только из единиц и нулей? (вы же здесь все программисты — нули-единички любите :). Так вот, можно ли помножить 2018 на что-то целое и положительное, да так, что результат перемножения записывается только нулями и единицами? Если да — покажите. Если таких много — найдите минимальное и докажите его минимальность. Если таких чисел нет — докажите невозможность.

Ну, вперёд! За самые смешные решения будут ещё подарки.

А пока назначаю победителей прошлых задачек. Это:

1) Максим Юрчук (двукратный чемпион!)
2) Дмитрий Питецкий
3) Ivankravtsov (спецприз за оригинальное продолжение условия задачки).

Победители, «с вами свяжутся» :) для вручения призов.

А теперь немного про решения этих задачек.

Задачка-2018-1:
Как соорудить 2018 из последовательности 10-9-8-7-6-5-4-3-2-1 и её усечений 9-…-1, 8-…-1 и так далее.

Лирическое отступление:
Самое правильное время для поиска решений — ожидание посадки/взлёта в аэропорту и самолёте. Немного всё нервно происходит, обстоятельства как раз способствуют включению режима спокойствия и решения чего-нибудь математически не слишком занудного. И получается вот так, например:

10 — 9 + (8*7*6*(5+4+3))/2 + 1 = 2018

Решение, конечно, не единственное. Их должно быть очень много — например, вот что ещё подсказали:

(10*9*(8+7-6)*5 — 4*3)/2 — 1

Пробуйте самостоятельно, у вас тоже должно что-то новое найтись.

Так, летим дальше…

9*8*7*(6+5-4-3) + 2*1 = 2018
8*7*6*(5+4-3) + 2*1 = 2018

Дальше без факториала уже никак не получилось:

((7 * 6! / 5) + (4 — 3) ) * 2 * 1 = 2018
6! / 5 * (4+3)!!!!! + 2*1 = 2018

где «!!!!!» — кратный факториал.
Хммм… Вообще-то через кратные факториалы можно чёрта лысого из чего угодно слепить…

3 2 1 -> 3!=6 -> 6!! = 48 -> 48!!!…!!! (41-кратный факториал) = 48*7 -> и так далее до 32*9*7 + 2*1 = 2018.

Так, давайте дальше попробуем без этих извращений.

Альтернативно мне подсказали вот что:

(9*8 — 7 ) * (6*5 + 4 — 3 ) + 2 + 1
8*7*6 *(5 + 4 — 3) + 2*1
-7 + ((6 + 5 + 4)*3 ) ^ (2/1) или немного лёгкого читерства: 7*6*(5 + 43) + 2/1
-6*5 + 4^3! / 2*1 или -6*5 + (4 << (3*(2+1)))

А что, (4 << (3*(2+1))) — неплохая задумка :)

Итак, продолжение развлечений:

5 4 3 2 1 = 2018
4 3 2 1 = 2018
3 2 1 = 2018
2 1 = 2018

и наше любимое:

1 = 2018

Мне тут же подсказали:

(5! — 4!) * F(F(3!)) + 2*1 = 96 * 21 + 2 = 2018
где F() = числа Фибоначчи.

От четвёрки я уже сам: 4 3 2 1 = 2018 ->

C(4) * F( (3!)!!!! ) + 2*1 = 14*144 + 2 = 2018
где:
C() = числа Каталана.
F() = числа Фибоначчи.

Тройка: 3 2 1 = 2018 ->

L(L(3)!!) + !L(M(2)) + 1 = L(15) + !L(3) + 1 = 1973 + 44 + 1 = 2018
где:
L() = числа Леонардо,
M() = числа Мерсена,
!n = субфакториал.

Двойка с единицей: 2 1 = 2018 ->

Двойку развррачиваем в…
M(2) = 3 // числа Мерсена.
M(3) = 7
!7 = 1854 // субфакториал.

Единицу в…
!1 = 0
Fm(0) = 3 // числа Ферма.
M(3) = 7
L(7) = 41 // числа Леонардо.
41!!!…!!! = 41*4 = 164 // 37-кратный факториал.

=> 1854 + 164 = 2018

Итого,

!M(M(2)) + L(M(Fm(!1)))!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! = 2018

Осталось самое смешное. Как из единицы получить 2018. А вот как:

!1 = 0
Fm(0)=3
W(3)=23 // число Вудала
23!!!!!!!!!!!!!!!!!!!!! = 46 // 21-кратный факториал
As(46) = 1009 // антисигма, как правильно обозначается мне неизвестно, «As» я сам придумал :)
1009!!!…!!! = 1009*2 = 2018 // 1007-кратный факториал. Как уже было ранее замечено, кратными факториалами можно чёрта лысого слепить.

(As(W(Fm(!1))!!!!!!!!!!!!!!!!!!!!!))!!!!!…..!!!!! = 2018

Всё.

Упражнение закончено. Кто опоздал — ждём нового 2019-го.

Дальше — решение Задачки-2018-2 про закрашивание 2018 лепестков. Решается очень просто.

1. Круг с чётным количеством лепестков N=2a.

На шаге 0 закрашивается самый первый лепесток, на шаге 1 – с номером 1, на шаге 2 – номер 3 и так далее. Получается арифметическая прогрессия на кольце из N элементов. На шаге N закрашивается лепесток номер:

N(N+1)/2 = 2a*(N+1)/2 = a*(N+1) = a (mod N)

То есть, за ‘a’ шагов на чётном круге алгоритм останавливается в противоположной точке круга и поскольку по модулю N можно не нарезать лишние круги – алгоритм повторяется зеркально из точки N/2=a. Это значит, что если круг разрезать пополам, развернуть в две параллельные ленты и начать одновременное закрашивание из точек 0 и N/2=a, то закрашивание пойдёт абсолютно симметрично. То есть, чётные круги можно смело резать пополам. В виде формулы количество закрашенных лепестков на чётном круге звучит так:

F(N) = F(2a) = 2*F(a)

2. Круг с нечётным количеством лепестков N=2a+1.

Аналогичными несложными вычислениями можно убедиться, что вся нечётная ромашка проходится за один цикл. При этом алгоритм половину цикла «топает» в одну сторону, а потом возвращается обратно по тем же самым точкам. Но иногда алгоритм красит одни и те же точки несколько раз – в этом несложно убедиться покрасив, например, ромашку-9. То есть, надо найти случаи, когда дублирующих перекрашиваний нет.

3. Нечётный круг с простым количеством лепестков N=P.

Рассматриваются только закрашивания «по дороге туда», поскольку на нечётных кругах цикл красит «туда-обратно». Что значит «закрасили лепесток повторно»? А это означает, что на некотором шаге ‘y’ мы оказались ровно в той же точке, что и на каком-то предыдущем шаге ‘x’. То есть, на шагах {0,1, …, a} возвращаемся в уже закрашенное место ‘n’. Что значит:

(x+1)*x / 2 = n + N*?? // сколько кругов N открутили до попадания в ‘n’ — неважно.
(y+1)*y / 2 = n + N*??

x^2 + x — y^2 — y = 2*N*k // k — количество кругов между попаданиями в ‘n’.

Т.е. разлагаем в множители, а поскольку N — простое, то только так:

(x-y)*(x+y+1) = 1*2*N*k // ‘1’ выделил специально — она тоже множитель, а вдруг есть решение, где «x-y=1» ?

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

Слева — два множителя, справа — разложение на множители. Кто-то слева делится на N, которое по условию простое число. (x-y) меньше N, поскольку они оба меньше (a+1). Но (x+y+1) тоже меньше N, по той же причине и они разные, то есть максимальная сумма (x+y+1) = a + a-1 + 1 = 2a < N.

То есть, решений уравнения нет, все кружки красятся только один раз! То есть – доказано, что для простых 'p' справедливо утверждение:

F(p) = (p+1)/2

4. Что по поводу закрашивания 2018 ?

F(2018) = F(2*1009) = 2*F(1009) = 2*( (1009+1)/2 ) = 1010 // поскольку 1009 простое.

Всё.

5. Что по поводу закрашивания чего-то, что даёт 2018 ?

1009 закрашиваний даёт ромашка-2017, поскольку 2017 тоже простое число. То есть,

2018 = 2*F(2017) = F(4034)

Решение это не единственное, поскольку F(3) = 2 и поверьте мне на слово, вот так тоже можно:

2018 = F(3)*F(2017) = F(6051)

поскольку 3 и 2017 взаимопростые. Как это и почему, где доказательство – см. Замечание2 чуть ниже.

Ну, на этом – совсем всё на сегодня.

Замечание1. Наверняка всё это можно изложить ещё проще, но у меня пока вот так получилось. Пробуйте, буду рад увидеть более элегантные доказательства.

Замечание2. Через год будет проблема 2019 = 3*673, то есть перемножение двух простых и не двойки. А это будет требовать немного более сложной математики, но знаний Википедии для решения вполне достаточно :)