Цифровой 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»

  • Жара в Женеве.

    В Женеве жарко. Безумно жарко. Солнце палит сверху вниз на раскалённый город, ветра почти нет, озеро не компенсирует. Народ выполз на местные пляжи,…

  • Необычная деталь.

    Давече жаловались, что здесь слишком простые задачки формата "on the road again" задаются. Буду усложнять задачки. Вопрос: какую необычную…

  • Сельско-баварская пастораль.

    Что-то укатали Сивку крутые горки с поворотами. Я вчера в ночи чуть лицом на клавиатуру не упал :) А в 7 утра следующий самолёт. Ага, как мне больше…


Аналитическое решение мне неизвестно. Да и не нужно. Поскольку по той же логике отсеваются варианты с 5,4,3,2,1 в начале. И делается это всё в уме. = задача решена.

?

Log in

No account? Create an account