занимательная задачка: составить число из цифр

[дворникЪ]

Вот такая вот задачка:

Даны 9 цифр, 1, 2, 3, 4, 5, 6, 7, 8, 9. Из этих цифр нужно составить число таким образом, что 2 старшие разряда этого числа делятся на 2, 3 старшие - на три, и так далее, вплоть до полного числа.
Найдите такое число, докажите его существование, единственность (если она конечно присутствует).

С комьпьютерным перебором просьба не обращаться.

[cepesh]

каждая цифра используется только один раз и число, которое нужно составить 9-значное, да?

[дворникЪ]

так точно

[garri_spbsu]

Я довел перебор до 10 вариантов, вроде.

Пятая цифра - 5, это очевидно.
На четных местах стоят четные цифры, на нечетных - нечетные - тоже понятно.
Так как первые три цифры делятся на три, а 6 - на 6, то сумма первых трех цифр, вторых трех и третьих трех - делятся на 3.

Таким образом, на местах "4" и "6" могут стоять либо 2 и 8, либо 4 и 6.

Ясно, что если число из первых 8 цифр делится на 8, то предпоследняя цифра не делится на 4 - потому, что если бы делилась, то ("6 цифра"*100 + "8 цифра") делится на 4, а "7 цифра"*10 - не делится, т.е. противоречие с признаком делимости на 8.

Итак, предпоследняя цифра - 2 или 6.
Проведя аналогичные рассуждения для 4-й цифры, получаем, что она тоже или 2, или 6

Разберем эти 2 варианта.
1) предпоследняя - 6. Тогда четвертая - 2. Шестая - 8, так как средние три цифры в сумме делятся на 3. Тогда вторая - 4. Имеем _4_258_6_.

7-я цифра - либо 9, либо 1 - так как 7-я с 8-й должны дать двузначное число, делящееся на 8. Разбираем 2 варианта:
1а) _4_25896_. Тогда последняя - 3, так как послендие три - тоже делятся на 3. Имеем да случая расположения 1 и 7, честно проверяем, что ни в одном из этих случаев делимости на 7 не будет.
1б) _4_25816_. Тут все просто - последней цифры не подобрать так, чтобы три последних в сумме делились на 3.

2) Предпоследняя - 2. Тогда, рассуждая аналогично 1, имеем
_8_654_2_. Опять же, из признака делимости на 8 имеем, что 7-я цифра - либо 3, либо 7.

2а) Пусть, 3. Тогда _8_65432_ Последняя цифра - 1 или 7.
Имеем 4 варианта
987654321
789654321
189654327
981654327
Для всех из них первые 7 цифр не делятся на 7.

2б) Пусть 7. Тогда _8_65472_. Последняя цифра - 3 или 9.
Имеем еще 4 варианта.
189654723 - первые 7 цифр не делятся на 7
981654723 - первые 7 цифр не делятся на 7
183654729 - первые 7 цифр не делятся на 7
381654729 - да!!!

[дворникЪ]

УРА!

Меня лично более всего впечатлил тот факт, что такое число в десятиричной системе уникально.

А как в других системах счисления?

[Бывший вундеркинд]

Хе-хе.

Всегда приятно вспомнить время, когда был не бывшим, а самым чтонинаесть настоящим вундеркиндом. Иными словами, вспомнить свое физматшкольное детство.

Итак, разбираемся.

Здесь и далее, когда говорится о том, что цифры или "группа цифр" делится на ... подразумевается, что делится число, составленное из этих цифр.

Сначала об очевидном: Четные цифры стоят на четных местах, нечетные - на нечетных, причем цифра 5 - на 5-м месте. Кроме того, группы цифр с 1 по 3, с 4 по 6, с 7 по 9 должны делиться на 3, группа цифр с 3 по 4 - на 4, а с 6 по 8 - на 8.

Для вас это не очевидно? Учите признаки делимости. Что, и теперь?! Тогда к дохтуру. Ну или капелек каких попейте.

Так как 6-я цифра - четная, то последнее требование облегчается: гцыфры 7-8 должны делиться на 4. Выписываем все такие пары, состоящие из нечетной+четной цифры:

16, 32, 56, 72, 96.

56, ясен пень, не годится, т.к. пятерка уже занята. 16 не годится по той же причине, так как за ней может следовать (из нечетных цифр) только пятерка - ведь нужно, чтобы эти три цифры делились на 3. Остается 32, 72, 96. Дополняем их до тройки нечетной цифрой, чтобы вся тройка делилась на 3. Получаем следующие варианты для последней триады цифр:

321, 327, 723, 729, 963.

Другие варианты невозможны. Теперь займемся второй триадой. Там пятерка обрамлена двумя четными цифрами. Чтобы вся триада делилась на 3, возможны только пары 8 и 2, или 4 и 6. Но цифры с 3 по 4 должны делиться на 4, а треться цифра - нечетная. Следовательно, четвертая цифра - четная, но не кратная 4 - 6 или 2. Таким образом, вторая триада выглядит следующим образом:

654 или 258.

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

Ну а с первой триадой все очевидно. В центре - оставшаяся "свободной" четная цифра, а по краям - две нечетные. Таким образом, получаем множество чисел, удовлетворяющих всем требованиям, кроме делимости на 7:

789654321 и 987654321,
189654327 и 981654327,
189654723 и 981654723,
183654729 и 381654729,
147258963 и 741258963.

Проверяем все числа на оставшееся требование и убеждаемся, что ему ужовлетворяет только число 381654729.

Задача решена.

[george_spbsu]

Ну... В других системах счисления Вы хорошо знаете признаки делимости? Я и в этой-то признак делимости на 7 так и не вспомнил... Может, удалось бы сократить док-во.

[дворнкЪ]

про признаки делимости

Я полагаю, что можно самому выводить признаки делимости в N-ричной системе счисления.

Например посмотрев на последовательности k*n, n=1...N можно увидеть структуру и характерные свойства операции деления на k.

Для примера, (по предверительным прикидкам) в нечётно-ричной системе счисления признаком деления на 2 будет чётность суммы цифр числа.

[Бывший вундеркинд]

Во сне вспомнилось/придумалось:

Что касается признаков делимости для чисел, записанных по произвольному основанию q, то они практически те же самые что и для частного случая q=10. Таких "элементарных" признаков всего 3: для чисел, делящих q^n, q-1 и q+1.

1. Если число k делит q^n, то k делит заданное число тогда и только тогда, когда оно делит "n последних цифр" этого числа (т.е. остаток от деления заданного числа на q^n).

2. Если число k делит q-1, то оно делит заданное число тогда и только тогда, когда оно делит сумму цифр заданного числа.

3. Если число k делит q+1, то оно делит заданное число тогда и только тогда, когда оно делит разность сумм цифр заданного числа, стоящих на четных и нечетных местах.

Остальные признаки более сложны, - как, например, признаки делимости десятичных чисел на 7 и 13, опирающиеся на факт, что 1001=7*11*13. В принципе, аналогичные признаки для чисел, записанных по произвольному основанию можно вывести, разложив число 10...1 на множители. При решениии задачи этого обсуждения данные признаки использовать неудобно.

Что же касается исходной задачи в общей формулировке, то для нее есть ряд очевидных фактов:

- для нечетных оснований q подобных чисел не существует (доказательство тривиальное);
- для четных оснований q выполняются следующие условия:
-- четные цифры стоят на четных местах, нечетные - на нечетных;
-- "в середине числа", т.е. на позиции q/2 всегда стоит цифра q/2.

Больше [очевидных] общих закономерностей пока не просматривается. Что касается существования и единственности решения для четных оснований, то тут, похоже, "дело случая". Например:
q=4: 123, 321
q=6: 14325, 54321
q=8: 3254167, 5234761, 5674321

Кстати, задача к размышлению на 3-5 минут: доказать, что для q=12 решения не существует.

Пока всё.

[дворникЪ]

>> "Кстати, задача к размышлению на 3-5 минут: доказать, что для q=12 решения не существует. "

Не совсем улавливаю Вашу мысль. Поясните, пожалуйста.

[Бывший вундеркинд]

дворникУ:

Доказать, что не существует [очевидно, конечной] последовательности 11 различных 12-ричных цифр (от 1 до "11"), такой, что число, записанное первыми n цифрами последовательности делится на n для всех целых n: 1<n<12. Ну то есть что задача, аналогичная исходной задаче, но сформулированная в 12-ричной системе счисления, неразрешима.

Пытался проверить для 14 и 16, но заленился. Может, когда-нибудь потом.