?

Log in

No account? Create an account

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)
Вот это интересно. Пока не рассказывайте, а через пару дней я у Вас спрошу, как Вы решали, хорошо?
(no subject) - lomeo - Dec. 23rd, 2013 06:25 am (UTC) - Expand
(no subject) - spamsink - Dec. 23rd, 2013 07:11 am (UTC) - Expand
(no subject) - lomeo - Dec. 23rd, 2013 08:01 am (UTC) - Expand
pphantom
Dec. 22nd, 2013 11:27 pm (UTC)
576 получается легко: очевидно, что на всех четных позициях должны стоять только четные цифры, а на пятой позиции - пятерка. Соответственно, остается 4!*4! вариантов. А дальше?
pphantom
Dec. 22nd, 2013 11:32 pm (UTC)
Хотя да, уже видно: сумма цифр в каждой группе из трех соседей должна делиться на три. Следовательно, соседями пятерки могут быть только либо 2 и 8, либо 4 и 6. Дальше уже можно практически прямым перебором.
(no subject) - spamsink - Dec. 23rd, 2013 07:04 am (UTC) - Expand
(no subject) - lomeo - Dec. 23rd, 2013 08:03 am (UTC) - Expand
(no subject) - slobin - Dec. 23rd, 2013 08:54 am (UTC) - Expand
(no subject) - utnapishti - Dec. 24th, 2013 09:43 pm (UTC) - Expand
slobin
Dec. 23rd, 2013 12:19 am (UTC)
уф, решил. полтора часа возился. ща придёт кто-нибудь, у кого полторы минуты.

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

fregimus
Dec. 23rd, 2013 12:24 am (UTC)
Я вообще начал с групп и совсем не туда. Это нормально.
(no subject) - pustota - Dec. 24th, 2013 10:31 am (UTC) - Expand
(no subject) - fregimus - Dec. 24th, 2013 10:56 am (UTC) - Expand
(no subject) - pustota - Dec. 24th, 2013 11:17 am (UTC) - Expand
evil_gryphon
Dec. 23rd, 2013 12:52 am (UTC)
Решил. Компьютер перебирает все (987654321-123456789) чисел примерно за 7 секунд.
fregimus
Dec. 23rd, 2013 12:53 am (UTC)
С компьютером кто хошь решит. Без компьютера надо!
(no subject) - erofeich - Dec. 23rd, 2013 09:06 am (UTC) - Expand
(no subject) - fregimus - Dec. 23rd, 2013 06:34 pm (UTC) - Expand
(no subject) - erofeich - Dec. 25th, 2013 09:34 am (UTC) - Expand
(no subject) - fregimus - Dec. 25th, 2013 10:00 am (UTC) - Expand
(no subject) - erofeich - Dec. 25th, 2013 10:07 am (UTC) - Expand
(no subject) - fregimus - Dec. 25th, 2013 10:21 am (UTC) - Expand
(no subject) - erofeich - Dec. 25th, 2013 10:40 am (UTC) - Expand
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

У меня, кажется, еще меньше получилось, но мне надо сформулировать понятно. Я их все не выписывал, а, скорее, как по дереву шел, отсекая сразу ветви.
(no subject) - l_i_d_y_a - Dec. 23rd, 2013 06:43 pm (UTC) - Expand
(no subject) - fregimus - Dec. 23rd, 2013 06:58 pm (UTC) - Expand
janatem
Dec. 23rd, 2013 07:55 am (UTC)
Я эту задачу уже решал и удивлялся, что она предлагается как задача по программированию (тупо берется брутфорсом либо решается математически), а не по математике (вполне осмысленная задача, не совсем простая и не убойно сложная). В том моем решении перебор сокращался до 6 вариантов, которые надо было проверить на делимость на 7, сейчас, пока ехал на работу, в уме прикинул, что варианта всего два.
fregimus
Dec. 23rd, 2013 08:58 am (UTC)
Да, на 7 можно проверять последним. Всего два.
(no subject) - janatem - Dec. 23rd, 2013 02:08 pm (UTC) - Expand
(no subject) - fregimus - Dec. 23rd, 2013 06:37 pm (UTC) - Expand
(no subject) - janatem - Dec. 23rd, 2013 08:07 pm (UTC) - Expand
(no subject) - fregimus - Dec. 23rd, 2013 08:12 pm (UTC) - Expand
(no subject) - pustota - Dec. 24th, 2013 10:30 am (UTC) - Expand
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 делить в самом конце для проверки, остальное, если не ошибаюсь, все в уме считается. Сам удивился!
mod 7 - falcao - Dec. 29th, 2013 09:31 pm (UTC) - Expand
( 49 comments — Leave a comment )