Определение задачи и её решение.

[E.K.]

Дамы и господа, мальчики и девочки -

 

Разрешите представить вам труд многомесячной работы творческого арифметического коллектива по теме "как сложить ровно 100 из того что было". Интереснейшее было цифровое путешествие, весьма сложная задачка - и не уверен, что в будущем получится придумать похожие по сложности и трудоёмкости прочие арифметические забавы. Что там было и как мы учились "карательной арифметики" - эти упражнения все достаточно тщательно расписаны уже ранее, достаточно потыкать по ссылкам на нашем фанклуб-форуме.

 

Здесь же и сразу хочу сформулировать эту архисложную арифметическую задачку:

 

Из каких десятичных наборов цифр при помощи простейших арифметических операций: плюс, минус, умножить, разделить, степень и корень (включая дробные и отрицательные степени и корни), да плюс факториал - из каких десятичных комбинаций невозможно получить ровно "100" ?  Переставлять цифры запрещено, склеивать вместе - можно.

 

Например-1:

 

0210 = 10^2  -- так нельзя! Двойку переставлять назад не позволяется.

 

0210:   (0!/2)√(10) = (1/2)√(10) = 10^2 = 100  -- а вот так можно. // кстати, там был корень 1/2-степени - это допускается.

 

Внимание! В дальнейшем знак корня '√' заменяю на символ 'V' ради уменьшения энтропии вычислений.

 

Например-2:  отличный пример как можно вычислять в рамках условия задачки:

 

17206:    1/7*(-20+6!) = 1/7*(-20+720) = 1/7*700 =100

 

Например-3:

 

Простые комбинации.. Ну, например, 12345 и обратно - пример с конкатенациями (слепкой) цифр и факториалами, а второй вообще какой-то очень простой..

 

12345:    12/3-4!+5! = 100

54321:    5*4*(3+2)*1 = 100

 

Например-4:  Да просто возьмите номерной знак своего автомобиля (или рядом стоящего транспортного средства) - и попробуйте из этих цифр в условиях этой задачки получить ровно 100. Склеивать цифры можно, переставлять нельзя!

[E.K.]

Как и откуда пришла идея этой задачки? - уже рассказывал. Просто в путешествиях в разные страны иногда приходится стоять в адских пробках (наши столичные пробки на этом фоне - просто незначительные проблемки). И там от нечего делать арифметически превращал номерные знаки соседних автомобилей в сотню - а что ещё делать, если всю почту прочитал, да все интересные интернеты осмотрел? Длинный и местами мож-быть интересный рассказ про это - вон там по ссылке.

 

Вот, например, никаких пробок - но по немецкому автобану A5 (из Франкфурта на север) едет ушастый Запорожец с номерным знаком "968 77" (буквы не важны). // фотка сделана мной в сентябре 2013.

 

Что можно сказать про его номерной знак 96877 ? А разное! - вот, например:

 

96877:    (9-6)!+87+7 = 100

96877:    V(9)+6!/8+V(7*7) = 100

96877:    -V(9)!-6+8*(7+7) = 100

 

Так вот, подумалось - а из каких комбинаций цифр невозможно сооружить ровно "100" ?

[E.K.]

Поскольку изначально задачка "сложить 100 арифметически из набора цифр" возникла из автомобильных номерных знаков, то оттуда и последовало направление решения. Ведь номерные знаки в России содержат 6 или 5 цифр (номер+регион), то я начал замечать, что практически вообще все 6-значные номера складываются с сотню (или же успевают уехать в даль до момента решения), а вот с пятизнаками иногда бывает сложнее...

 

То есть, первоначальнао задача была только про шестизнаки... А ещё ранее, в самом первом изложении - тогда было страшно браться за шестизнаки с нулём в начале. Например, "012345" - сейчас это легкота: 0*1+(2+3)*4*5 = 100, а вот тогда нули в начале комбинации страшили.. Посему, изначально задача звучала вот так:

 

Можно ли из любых шести последовательных цифр (за исключением первого нуля) при помощи операций плюс, минус, умножить, разделить, возведения в степень, корней, факториалов и скобок получить ровно 100? "Склеивать" цифры можно, переставлять местами - нет.

[E.K.]

Поскольку здесь в данной ветке приводится именно решение задачки, а не процесс её решения (это увлекательнейшее арифметическое путешествие - в параллельных ветках, начиная вот отсюда) - то сразу сообщаю, что задачка была целиком и полностью освоена. Наверняка, что-то могли пропустить, где-то ошибиться, что-то неправильно подсчитать - но результат есть. И он такой. От "однознаков" - до выхода на "всё решабельно".

 

1. Однознаки от "0" до "9" - число "100" получить из такого можно только по щучьему велению. Или же в бутылке джина найти джинна.

 

2. Двузнаки от "00" до "99" - аналогично. 100 = 5*4*5 или же "двузнак+цифра". Всё на этом, решений нет.

 

3. Трёхзнаки (решение здесь). Всего таких тысяча (что неудивительно). Решить получилось 140 (14%), не получилось 860.

 

4. Четырёхзнаки (подробности смотреть здесь). На момент написания этого текста не нашлось решений для 2736 нерешённых вариантов (27.4%).

 

5. Пятизнаки! - арифметически слабонервным сюда не заглядывать! Из 100-тысяч вариантов не удалось превратить в "100" только 1134 пятизнака =  1.134% от всех возможных комбинаций // окончательный результат "1134" ещё может поменяться...

 

6. Шестизнаки "123456", с чего всё начиналось. Не смогли найти решение только для 35 из миллиона возможных комбинаций! То есть, не решено 0,0035% из всего набора вариантов. Вот такая "карательная арифметика"...

 

7. Дальше - ... ну, совсем быстрее (если применять заранее наработанный арифметический арсенал). В "100" не складываются только две комбинации: 0000000 и 0000001.

 

8-и-далее-знаки:  все такие решаются в "100". И всё на этом.

 

Но кому интересно - далее в сжатом виде будет представлен результаты всего полугодового труда нашего арифметического коллектива. Само собой, мы работали "в факультативном режиме" (в свободное от работы, да), но всё же полгода цифровых упражнений и в результате достойный ответ на поставленную задачку - ай, какие молодцы!

[E.K.]

Теперь же настало время объяснить методы решения задачки превращения произвольных последовательностей цифр ровно с сотню "100". Изначально мы отталкивались от задачки про шестизнаки ("123456" - так "исторически сложилось"), то пытались найти оптимальные методы её решения.

 

 "abcdef" == 100.

 

Само собой, вручную подсчитывать (или программно код настраивать на) весь этот миллион вариантов от 000000 до 999999 = ухандокаться можно, то следует искать оптимизации. // Сразу отвечаю на вопрос: ИИ-шницы на вопрос о подобной задачке все жидко обгадились, поскольку это уникальное упражнение - и подглядеть ответ просто негде.

 

Итак, "в лоб решать" миллион вариантов - нужны тысячи "арифметических рабов". Код сооружать - не очень понятно как. ИИ-шница не в помощь. То есть, очень правильное место для применения своих личных человеческих хомо-сапиенских мозгов. Будем строить фильтры, которые помогут нам отсеять ненужное - а остальное будет решать "вручную".

 

Как строить эти фильтры? - некоторое время потратили на обсуждения и эксперименты. Затем пришли к выводу, что нужны разноуровневые фильтры, которые будут примерно как в горнорудном производстве "обогащать руду". И для шестизнаков первый фильтр (или "фильтр первого уровня") - это разбиение шести цифр на два трёхзнака.

 

 "abc"+"def" == 100.

 

Фильтр-1 работает так:

- разбиваем шестизнак на два трёхзнака.

- если из "abc" можно получить десятку "010", а "def" = "002" или "010", то:

 

 "010" * "010" = "010" ^ "002" = 100

- для таких комбинаций задачка решена, их можно отфильтровать сразу.

 

Более того, если "def" есть не просто "002", а степень двойки - то такие тоже можно отфильтровать сразу и навсегда:

 

 V(V("010"^"008")) = V(V(V("010"^"016"))) = V(V(V(V("010"^"032")))) = ... = 100

 

То есть, для любого натурального 'n' => V(...V("10"^2^n)...) = 100

 

 

Итого, чтобы из всего миллиона шестизнаков оставить для дальнейшей работы значительно поменьше миллиона нужно найти все "не-010-трёхзнаки" ("abc") - и все "не-002^n - и не-010" трёхзнаки ("def").

 

// зачем так подробно расписываю? - чтобы потом не вспоминать что, зачем и почему

[E.K.]

Теперь же нам следует найти все трёхзнаки "abc", которые не превращаются в "010" - чтобы потом отфильтровывать их в последующих вычислениях. А также найти все трёхзнаки "не-002", а потом из них получить "не-002^n" ...

 

// здесь и далее терминами "не-xx" называются двузнаки "ab", из которых нельзя получить число/цифру "xx". Аналогично "не-xxx" и "не-xxxx" - те "abc"/"abcd", из которых нельзя получить "xxx"/"xxxx". // Пятизнаки "не-ххххх" и далее "не-xxxxx..." не потребуются.

 

То есть,

 

// "не-02,05" = двузнаки, из которых не получаются ни 2, ни 5.

// "не-005,009" = трёхзнаки, не дающие ни 5, ни 9.

 

Итак, нужно выяснить какие "abc" невозможно арифметически превратить в "010". Например,

 

 123:  никак не превращается в десятку.

 321:  3^2+1 = 10   <-- а этот превращается!

 

Брать всю тысячу комбинаций и тупо её решать - можно, но долго и дорого... // В самом начале так и делал, но потом оптимизировал.

 

И далее будет про оптимизацию фильтрации. // о как!

[E.K.]

Для дальнейших арифметических упражнений нам потребуются следующие навыки:

 

1. Арифметическая угадайка. Умение видеть разные комбинации. И не просто "6+7+87 = 100", а более изощрённые. Например,

 

  2771:      2*(7*7+1) = 100
  17820:    V(17+8)*20 = 100

 

2. Арифметический арсенал. Потребуются библиотеки комбинаций "не-ab", "не-abc", "не-abcd" - и производные из них, вроде "не-01-02-05" и типа того.

 

Например, есть комбинация "8712xx". Какие "xx" можно отфильтровать?

 

8!/7!*1+2 = 10   --- то есть, можно сразу выбросить все "xx", которые дают "02^n" или "10" (примеры см. выше). А также:

87+(1+2)!+"07" = 100  --- то есть, можно выбросить все "xx", которые дают "07". То есть ==>

 

Для решения всех комбинаций "8712xx" потребуется фильтр:

 

  8712xx:    8!/7!*1+2 = 10, 87+(1+2)!+"07" = 100          "не-02^n,07,10" = 6 штук.

 

И вот эти "6 штук" для ручного перебора будем доставать из "арсенала".

 

3. Таблицы умножения степеней и факториалов. А как иначе угадать, что:

 

  (6!-5!)/6 = 100

  V(7!+7!-80) = 100

 

- ну, и так далее. А там такие арифметические лабиринты с минотаврами - аж закачаешься!

 

4. Арифметическая магия, на всём этом устроенная:

 

1065:       (1-0!/6)*5! = 100

4269:       4*(-2+V(6!+9)) = 100

5116:        5!*(1-1/6) = 100

26767:     -2-6/7+6!/7 = 100

72766:      (7!-(-2+7)!)/6-6! = 100

776777:    (7!-7!/6) / (7*7-7) = 100

 

- и так далее! Много и обширно.