You are viewing fregimus

Previous Entry | Next Entry

Число из 9 разных цифр

Я набрел на эту задачу случайно — на одном вебсайте предлагалось решить ее на разных языках программирования. Когда я задумался, оказалось, что программировать вовсе не надо, и задачу можно решить на обороте конверта. fregima говорит, что она эту задачу видела уже давно, так что, может, я просто не находил ее раньше. Формулируется она так.

Составить число перестановкой цифр от 1 до 9 включительно так, чтобы:
* все число делилось без остатка на 9;
* число без последней цифры делилось на 8;
* без двух последних на 7;
* и так далее, пока цифры не кончатся.

Решение единственное, и, как оказалось, перебирать нужно не 9! вариантов, а много меньше. Можно сузить область поиска до 576 чисел, можно до 96, можно до 48, а можно и еще дальше. Больше подсказывать не буду.

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

Tags:

Comments

( 49 comments — Leave a comment )
lomeo
Dec. 22nd, 2013 11:24 pm (UTC)
Э, не знаю как сузить до 576/96/48. Сразу видно как сузить до 20, дальше проверяем и находим. Действительно, только одно число. Красивая задачка, спасибо!
fregimus
Dec. 23rd, 2013 12:07 am (UTC)
Вот это интересно. Пока не рассказывайте, а через пару дней я у Вас спрошу, как Вы решали, хорошо?
lomeo
Dec. 23rd, 2013 06:25 am (UTC)
Хорошо :-)
spamsink
Dec. 23rd, 2013 07:11 am (UTC)
А чего до 20-то, когда до 10?
lomeo
Dec. 23rd, 2013 08:01 am (UTC)
Не сообразил как.
pphantom
Dec. 22nd, 2013 11:27 pm (UTC)
576 получается легко: очевидно, что на всех четных позициях должны стоять только четные цифры, а на пятой позиции - пятерка. Соответственно, остается 4!*4! вариантов. А дальше?
pphantom
Dec. 22nd, 2013 11:32 pm (UTC)
Хотя да, уже видно: сумма цифр в каждой группе из трех соседей должна делиться на три. Следовательно, соседями пятерки могут быть только либо 2 и 8, либо 4 и 6. Дальше уже можно практически прямым перебором.
spamsink
Dec. 23rd, 2013 07:04 am (UTC)
Более того, группа должна начинаться только на 2 или 6, чтобы первые 4 цифры делились на 4. Итого для второй группы имеем 258 или 654. Последние 8 цифр должны делиться на 8, т.е. тройка из 6-й по 8-ю цифры должна делиться на 8. Но и 800 и 400 делятся на 8, т.е. пара из 7-й и 8-й цифр должна делиться на 8, а мы знаем, что 7-я цифра нечетная, т.е. варианты только 16, 32, 56, 72, 96. Вместе с второй группой это нам дает с 4-й по 8-ю цифры варианты 25816, 65432, 65472, 25896. Как мы знаем, каждая группа должна делиться на 3 путем приписывания нечетной цифры, т.е. к 25816 нужно приписывать 5, поэтому этот вариант вылетает. Рассуждая по образцу, получаем варианты 654321, 654327, 654723, 654729, 258963. В каждом из этих случаев имеется 2 варианта первой группы, итого 10:
987654321
789654321
981654327
189654327
981654723
189654723
381654729
183654729
147258963
741258963
Вот теперь можно прямым перебором.
Четвертый вариант с конца - ответ.
lomeo
Dec. 23rd, 2013 08:03 am (UTC)
> Более того, группа должна начинаться только на 2 или 6, чтобы первые 4 цифры делились на 4

Вот это не сообразил.
slobin
Dec. 23rd, 2013 08:54 am (UTC)
Вот пост-фактум, когда стал своё решение записывать, подчищая все ложные следы и тупики, получилось ровно то же самое. В смысле, те же десять вариантов, полученные теми же рассуждениями, а потом перебор. Но пока я до этого того же самого дошёл, я полтора часа блуждал.

... Уточнённое издевательство ...

utnapishti
Dec. 24th, 2013 09:43 pm (UTC)
Решил точно так же, но у меня правильный вариант оказался последним :)
slobin
Dec. 23rd, 2013 12:19 am (UTC)
уф, решил. полтора часа возился. ща придёт кто-нибудь, у кого полторы минуты.

... Условия победы: победить всех врагов ...

fregimus
Dec. 23rd, 2013 12:24 am (UTC)
Я вообще начал с групп и совсем не туда. Это нормально.
pustota
Dec. 24th, 2013 10:31 am (UTC)
а как вы начали с групп?
fregimus
Dec. 24th, 2013 10:56 am (UTC)
Ничего особо умного. Попытался понять, как устроена группа перестановок цифр, описываемая разными признаками делимости — получить известную группу каких-то симметрий и дальше исходить из ее (известных) свойств. По-моему, тупиковый путь.
pustota
Dec. 24th, 2013 11:17 am (UTC)
ну вроде как кроме чисел, делящихся на 3 и 9 ничто по перестановкам подгруппу не образует. вообще, может это и интересно
evil_gryphon
Dec. 23rd, 2013 12:52 am (UTC)
Решил. Компьютер перебирает все (987654321-123456789) чисел примерно за 7 секунд.
fregimus
Dec. 23rd, 2013 12:53 am (UTC)
С компьютером кто хошь решит. Без компьютера надо!
erofeich
Dec. 23rd, 2013 09:06 am (UTC)
ну так там ручной перебор не исключается вовсе
тут ведь какое дело
задача позиционируется как прикладная в цифровых вычислениях
решив задачу аналитически и подставляя результат мы решаем не саму поставленную задачу, а именно задачу максимальной оптимизации решения задачи
в то время как оптимизация штука тоже прикладная
и в зависимости от места ее "приложения" она может быть не очень нужна
скажем, при единственном вычислении такого числа в ходе выполнения ПО оптимизация производится совсем другими способами, например, решение выносится в некий модуль подготовки данных, или решение вовсе идет в таблицу констант как, например, замечательная таблица тригонометрических функций в игре "дум" (там прямо таблицы брадиса вбиты были)
и когда программист садится с бумажкой и тратит время на выполнение оптимизации о которой его не просили - это говорит о нем как о хорошем математике, но и одновременно как о человеке, который не очень понимает процесс разработки
хотя, если, например, он решает задачу в ходе собеседования и может аргументировать подход с этой точки зрения и примет во внимание другие варианты - у него будет большое преимущество перед теми кто не задумался как решить задачу аналитически
НО коммерческая разработка это сначала сроки, а только потом красота и оптимизация

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

Edited at 2013-12-23 09:19 am (UTC)
fregimus
Dec. 23rd, 2013 06:34 pm (UTC)
Ну понятно — экзаменатор должен выяснить, какую прибыль принесет родному заводу экзаменуемый. Мне кажется, это уже слишком… прикладное.
erofeich
Dec. 25th, 2013 09:34 am (UTC)
видимо вы по натуре ученый
инженер мыслит другими категориями
для меня задача без ее приложения - бессмысленна и беспощадна
а человек решающий сто раз решенную задачу, извините, онанирует
доставляет себе удовольствие, запуская некоторые химические процессы в организме и более ничего
в прикладном же смысле эта задача служит более установке взаимопонимания между двумя людьми, которым вместе решать много других задач, несет в себе десятки трактовок и вариантов решения вне математической области
это куда интереснее чем чистая математика и это - красиво
fregimus
Dec. 25th, 2013 10:00 am (UTC)
Да, наука — это исключительно доставление себе удовольствия, согласен. Никакой другой цели, кроме как вызвать в себе ублажительные химические реакции. Я, безусловно, очень плотно на них подсел — я аддикт, для меня не получать решений красивых задачек — прямая дорога к депрессии и тоске зеленой. Только свежая порция дофамина спасает.
erofeich
Dec. 25th, 2013 10:07 am (UTC)
ну а вот дофаминовый триггер инженера - встроить задачу в жизнь и посмотреть что выйдет
fregimus
Dec. 25th, 2013 10:21 am (UTC)
Очень любопытно. Я думал, триггер будет «…и чтоб заработало». А «…и посмотреть, что выйдет» — это для меня новость.
erofeich
Dec. 25th, 2013 10:40 am (UTC)
переформулирую:
триггер, впрыскивающий дофамин в мозг инженера - не решать задачу, а смотреть что выходит, когда она работает в жизни
самое решение впрочем тоже слегка впрыскивает, но существенно меньше чем ученым
слова они такие сложные
думаешь одно, пишешь другое, понимают третье

Edited at 2013-12-25 10:42 am (UTC)
schegloff
Dec. 23rd, 2013 01:53 am (UTC)
Спасибо на наводку, обнаружил, что в природе существует признак делимости на 7, причем совершенно неожиданный. А задачу решать некогда, даже на питоне.
spamsink
Dec. 23rd, 2013 04:16 am (UTC)
Я знаю только один, который сам вывел в детстве: удвоенную последнюю цифру вычитать из числа, образованного оставшимися цифрами, пока делимость или неделимость не станет очевидной.
l_i_d_y_a
Dec. 23rd, 2013 07:15 am (UTC)
381654729

Не больше получаса ушло, но многовато перебора, на мой вкус. Возможно, я какой-то важный признак делимости не помню.
fregimus
Dec. 23rd, 2013 06:35 pm (UTC)
Выше описывают решение с перебором 10 вариантов всего: http://fregimus.livejournal.com/233325.html?thread=6563949#t6563949

У меня, кажется, еще меньше получилось, но мне надо сформулировать понятно. Я их все не выписывал, а, скорее, как по дереву шел, отсекая сразу ветви.
l_i_d_y_a
Dec. 23rd, 2013 06:43 pm (UTC)
Ну я как-то так и решала, как выше написано. Сначала пятерку, потом возможные варианты расположения четных. Только я не считала сколько у меня было вариантов.
fregimus
Dec. 23rd, 2013 06:58 pm (UTC)
Ну, 5 вариантов перебора — это немного, на мой взгляд. Только признак делимости на 7 не используется, но они все сложные, смысла нет.
janatem
Dec. 23rd, 2013 07:55 am (UTC)
Я эту задачу уже решал и удивлялся, что она предлагается как задача по программированию (тупо берется брутфорсом либо решается математически), а не по математике (вполне осмысленная задача, не совсем простая и не убойно сложная). В том моем решении перебор сокращался до 6 вариантов, которые надо было проверить на делимость на 7, сейчас, пока ехал на работу, в уме прикинул, что варианта всего два.
fregimus
Dec. 23rd, 2013 08:58 am (UTC)
Да, на 7 можно проверять последним. Всего два.
janatem
Dec. 23rd, 2013 02:08 pm (UTC)
Странно, как может получиться два варианта. Я не учел подвариантов, на которые ветвятся основные варианты. Еще раз аккуратно проверил, получил тот же набор из 10 вариантов, что в комментариях выше. При этом учтены все условия, кроме делимости на 7 (что можно проверить в лоб). Другое дело, что проверку делимости на 7 можно оптимизировать, так что не нужно все десять 9-значных чисел делить, а достачно только вычислить остатки у двух 9-значных и нескольких маленьких (по сути 2-значных).
fregimus
Dec. 23rd, 2013 06:37 pm (UTC)
До проверки делимости на 7 при удовлетворении остальных условий остается два варианта: ответ и он же с переставленными первой и последней цифрами. Только ответ делится на 7.
janatem
Dec. 23rd, 2013 08:07 pm (UTC)
Так в том дело, что это вроде не верно. Например, 189654723 удовлетворяет всем условиям, кроме делимости на 7. И таких чисел десять.
fregimus
Dec. 23rd, 2013 08:12 pm (UTC)
Ага, и правда! Я и не заметил других вариантов — видимо, мне повезло в переборе попасть быстро на ответ. Фрегима вообще с первого раза подобрала, на удивление.
pustota
Dec. 24th, 2013 10:30 am (UTC)
дада, у меня тоже свелось к этим 10, но правильный ответ попался третьим. а 987654321 я на всякой случай проверил, когда оно как вариант стало еще в начале вырисовываться
alex_bykov
Dec. 23rd, 2013 07:57 am (UTC)
Забавная задача, сыну пятикласснику подкину, они как раз в олимпиадной школе в сентябре признаки делимости проходили. Если не забыл, решит.
beldmit
Dec. 23rd, 2013 10:02 am (UTC)
До 1024 я это свел. Дальше сходу слабо.
beldmit
Dec. 23rd, 2013 10:07 am (UTC)
Вру. 512.
v_pychick
Dec. 23rd, 2013 10:13 am (UTC)
решил :) Свел к 4-м вариантам, дальше тупо перебрал
_winnie
Dec. 23rd, 2013 05:06 pm (UTC)

Не особо ценное, но для полноты пусть будет.

from itertools import permutations 

for p in permutations(xrange(1,10)):
    x = ''.join(map(str, p))
    if all( 0 == int(x[0:9-i]) % (9 - i) for i in xrange(0, 9)  ):
        print x


Из "оптимизаций" вижу только такие соображения: ( СПОЙЛЕРЫ !! )

1) на четных местах - только четные числа (из делимости на 2)
2) следовательно, на нечетных местах - нечетные (других не осталось)
3) на 5-м месте - 5 или 0, но 0 (как четное) нельзя
4) на 4-м месте - только 2 или 6 (из делимости на четыре. вариантов 4 и 8 не может быть, из-за ограничений на "нечетных позициях - нечетные").

Как использовать делимость на 3,7,6 для оптимизации перебора - не знаю. Ну т.е. в компьютере понятно, перечислить и пересечь, а вручную как из них что-то полезное приготовить - непонятно.
janatem
Dec. 23rd, 2013 08:08 pm (UTC)
3) нуля нет по условию
pustota
Dec. 24th, 2013 10:23 am (UTC)
интересно, спасибо, делимость на 8 дает три варианта пар на 7-м и 8-м местах (32,72,96), сумма последних трех делится на три - получается пять вариантов трех последних цифр 327, 729, 723, 963, 321. ну и дальше все похоже на игру в судоку, причем правильный вариант выскакивает одним из первых.

особенно интересно, что число 987654321 удовлетворяет всем требованиям, кроме условия с делимостью на 7.
fregimus
Dec. 24th, 2013 10:35 am (UTC)
Последняя находка чудесная!
falcao
Dec. 27th, 2013 11:26 am (UTC)
+1
Хорошая задача! Вполне годится для "ручного" перебора.
fregimus
Dec. 27th, 2013 12:07 pm (UTC)
Re: +1
Да, калькулятором приходится только на 7 делить в самом конце для проверки, остальное, если не ошибаюсь, все в уме считается. Сам удивился!
falcao
Dec. 29th, 2013 09:31 pm (UTC)
mod 7
Можно даже не делить калькулятором: для степеней 10 остатки от деления на 7 известны, и у цифр, про которые известно их положение, сумму остатков можно зафиксировать. Тогда получается перебор где-то шести случаев всего, где надо проверять сумму остатков от деления на 7 у двух или трёх цифр.
( 49 comments — Leave a comment )