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

Previous Entry Поделиться Next Entry
13 декабря, 2017
e_kaspersky
Всем привет,

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

Задачка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, то есть перемножение двух простых и не двойки. А это будет требовать немного более сложной математики, но знаний Википедии для решения вполне достаточно :)



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

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


Не для натурального все же. Число из одних единиц не может делиться на четное число.
Видимо, кроме чисел, кратных двум и пяти (потому что мы делим на степень десятки).
Но если вернуться к исходным условиям - что допускается наличие нулей, - то делить не нужно, и доказательство "Для любого натурального N найдется x такой, что Nx в десятичной системе записывается с помощью нулей и единиц" будет верным

Я про тоже самое!
Делим N напополом до нечётного, потом 111....111.
Потом просто сдвигаем налево сколько надо.

?

Log in

No account? Create an account