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

  • Басконское побережье Бискайского залива.

    Совсем недалеко от Бильбао - ещё две точки, заслуживающие личного присутствия по краткому маршруту исследования Страны Басков. Это города Гечо и…

  • Камчатка книжная и панорамная.

    Всем привет! Это будет короткий воскресный пост, чтобы не отвлекать вас от важной задачи отдыхания физического и умственного, но закинуть на…

  • Воскресная угадайка.

    Снято из рукава перед посадкой в самолёт. Вопрос: куда я сейчас полечу? // номер самолёта (где его видно) я закрасил, не поможет :) ЗЫ:…


Первое подбором делается.
6210001000
Второе надо думать.

По второй задаче.
1. Если X*1009 дает число, удовлетворяющее условиям задачи (т.е. из 0 и 1), то 5X*2018 дает число, удовлетворяющее условиям задачи (Х*1009*10)
2. Существует число вида 111...111 (из одних единиц), которое делится нацело на 1009. Доказательство:
Рассмотрим последовательность вида 1, 11, 111, ... - S(i) есть число из i единиц. Рассмотрим члены последовательности от S(1) до S(1010). Если какой-то из них делится на 1009, то задача решена. Если ни один из них на 1009 не делится, то хотя бы 2 из них дают одинаковые остатки (ибо остатков всего 1009). Вычтем из большего числа меньшее и разность поделим на 10 в нужной степени (уберем нули справа). Оставшееся число принадлежит последовательности и делится на 1009.


Итак, мы доказали, что существует число, при умножении 2018 на которое в результате получается число вида 111...10, соответствующее условиям задачи.
Далее можно попробовать прямым перебором найти минимальное:)

Отлично!
Я с "длинной стороны" не заходил, даже не думал про это. Я делал с младших цифр в верхние... Но доказательство = зачёт. Между прочим, доказано для любого вообще натурального N.

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

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

поздравляю!
напишите мне на sp@kaspersky.com и мы вам вышлем подарок :)

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

Задача 1
Решал на уровне интуиции, было понятно что начать стоит с того, что от числа 9000000000 (оно неверное) начать двигаться в сторону верного. Попробовал 8000000010 (тоже неверное, ибо единичка оказалась неучтенной). Далее был вариант с семью нулями, который тоже не прошел. Ну а потом обнаружился верный вариант:
6210001000
Шесть нулей - учтено
Две единицы - есть
Одна двойка - есть
Одна шестерка - есть

Это по сути брутфорс и мне, как математику, стыдно за отсутствие аналитического решения. Но уж какое есть. Если найду аналитическое - обязательно его приведу :)

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

012233444 хммм... не влезает( чота я тупой

Да ладно..
у меня тоже бывают ситуации, что я давно знакомых цифр не помню.

Попробуйте еще раз.

2)
Пусть n -- натуральное число, которое не делится ни на 2 ни на 5. Попробуем найти что-то из нулей и единиц, что делится на n.

По теореме Эйлера (10 и n взаимно просты по определению n):
10^(phi(n)) = 1 (mod n)
А это значит, что 10 с phi(n) нулями дает нам остаток 1 при делении на n.

Пойдем дальше, возведем обе части в квадрат, получим
10^(2*phi(n)) = 1 (mod n)
Т.е. если удвоим кол-во нулей, все равно остаток будет равен 1. Это будет другое число, т.к. phi(n) != 0

Проделаем это n раз, просуммируем левые части, получим число, которое делится на n без остатка (потому что мы просуммировали n чисел, что дают остаток 1).

Т.е. число 10^(phi(n)) + 10^(2*phi(n)) + .. + 10^(n*phi(n)) будет делиться на n без остатка и будет состоять только из нулей и единиц по понятным причинам.

Если положить n = 1009, и умножить число по формуле выше на 10, то оно будет делится на 2018 и все цифры в нем будут либо 0 либо 1.

Edited at 2017-12-14 00:56 (UTC)

Но как я понимаю, здесь тоже не показана минимальность данного числа? Или это как-то следует из определения функции Эйлера?

Не-а, это не минимальное (в нем больше миллиона цифр, какая минимальность:) ).

Минимальное -- 100100011111110, но я очень не уверен, что его можно найти не перебором.

Ясно, спасибо:)
Ну что, ждем ответа автора блога. Из его слов можно понять, что данное решение можно найти с помощью ручки и бумаги - т.е. вряд ли перебором.

Там алгоритм довольно простой. Умножаем на такое, чтобы младшая цифра превратилась в 0 или 1. Потом к множителю дописываем цифру, чтобы и вторая цифра ушла в 0 или 1. Причём там так получается, что можно выбирать 0 или 1 по желанию. И так далее. На каждой итерации "левый остаток" исходного числа становится всё меньше и меньше. За конечное число шагов - всё.

Первая задача простая, за несколько минут на бумажке подобралось число: 6210001000, потом для интереса брутфорсом перебрал, больше нет таких десятизначных чисел. Доказать единственность по-другому не смог.

Вторая задача: вроде тоже понятно, что число такое есть, доказательство существования выше интересное. Я думать начал с остатков и окончания числа искать, снизу, но не довёл и забил, т.к. понял, что получить это число всё равно таким способом будет сложновато (дерево там строилось уже слишком ветвистое, а конца не видать было, и подозревал что это немного неправильно, ну и способ был типа: понятно что множитель заканчивается на 5, потом пишем недостаюшее итд, upd: увидел в ветке выше вы примерно то же самое написали, но у меня выходило куча вариантов почему-то, где-то я накосячил получается с бумажкой своей).
Потому как на бумажке или без брутфорса найти я не знаю до сих пор (но интересно, я на досуге подумаю ещё), накидал на коленке скрипт, нашлось пока три решения:
2018 * 49603573395 = 100100011111110
2018 * 49608573395 = 100110101111110
2018 * 49609073395 = 100111110111110

Edited at 2017-12-15 09:18 (UTC)

ладно скрипт оставлю для потомков, может кто-нибудь дождётся других решений)
(ну тут python3 если вдруг что)

YEAR = 2018
isbinarylike = lambda number: False if number % 10 > 1 else isbinarylike(number // 10) if number > 0 else True
_ = [print(YEAR,"*",n//YEAR,"=",n) for n in range(YEAR,sys.maxsize,YEAR) if isbinarylike(n)]


Edited at 2017-12-15 09:32 (UTC)

Переделал немного, накидались ещё варианты:
2018 * 495540683895 = 1000001100100110
2018 * 496035678895 = 1001000000010110
2018 * 496035678945 = 1001000000111010
2018 * 496035683895 = 1001000010100110
2018 * 496035728945 = 1001000101011010
2018 * 496035733895 = 1001000111000110
2018 * 496035733945 = 1001000111101010
2018 * 496035733950 = 1001000111111100
2018 * 496036228945 = 1001001110011010
2018 * 496040683895 = 1001010100100110
2018 * 496085728945 = 1001101001011010
2018 * 496085733895 = 1001101011000110
2018 * 496085733945 = 1001101011101010
2018 * 496085733950 = 1001101011111100
2018 * 496090683895 = 1001111000100110
2018 * 496090733895 = 1001111101000110
2018 * 496090733945 = 1001111101101010
2018 * 496090733950 = 1001111101111100
2018 * 501040683895 = 1011100100100110

Алгоритм для бумаги и ручки

tsaregorodtsev1

2017-12-15 20:46 (UTC)

Наконец то дошло как можно искать решение в блокноте, которое кратко описал Евгений. Итак, поехали.
1-я цифра справа:
2018
0 - хочу эту цифру на конце (правда для первого числа других вариантов нет)
5 - множитель
2-я цифра справа:
10090 - это 2018*5, если все цифры 0 или 1, то прекращаем, в данном случае пока нет
1 - хочу эту цифру на втором месте справа
2 - нужно добавить к 9, чтобы получить число с 1 на конце
9 - на это нужно умножить 2018, чтобы получить 2 на конце
95 - промежуточный результат, последние 2 цифры искомого числа
3-я цифра справа:
191710 - это 2018*95
1 - хочу эту цифру на третьем месте справа
4 - нужно добавить к 7, чтобы получить число с 1 на конце
3 - на это нужно умножить 2018, чтобы получить 4 на конце
395 - промежуточный результат, последние 3 цифры искомого числа
4-я цифра справа:
797110 - это 2018*395, есть не 0 или 1, идем дальше
1 - хочу эту цифру на 4-м месте справа
4 - нужно добавить к 7, чтобы получить число с 1 на конце
3 - на это нужно умножить 2018, чтобы получить 4 на конце
3395 - промежуточный результат, последние 4 цифры искомого числа
5-я цифра справа:
6851110- это 2018*3395, есть не 0 или 1, идем дальше
.....
.....
.....
49603573395 - промежуточный результат, последние 11 цифр
100100011111110 - это 2018*49603573395, остались только 0 и 1, задача решена.





Edited at 2017-12-15 21:10 (UTC)

Это всё круто, я почти так же делал, но как доказать, что найденное - минимально?)

?

Log in

No account? Create an account