Наткнулся на задачку. Я ее решил при помощи экселя. А у нее есть решение без перебора?
У вас есть по одной цифре от 1 до 9. Нужно расставить их так, чтобы число образованное первыми двумя цифрами, было кратно двум, первыми тремя цифрами – трем, первыми четырьмя цифрами – четырем и т.д. Например, привычный порядок 123456789 не подходит. 12 делится на 2, 123 делится на 3, но 1234 на 4 не делится (без остатка).
Все, что мне видится очевидным упростить - это 5 на 5 месте. Потому что на 5 делятся только числа заканчивающиеся на 5 и на 0. Четные цифры на четных местах, нечетные на нечетных. Потому что на 2,4,6,8 могут делиться только четные числа. А вот дальше этого у меня мысли кончаются.
Вот вариант решения "в лоб"
Еще чтобы число делилось на три, сумма цифр должна делиться на три. То же самое с девяткой, но тут в любых комбинациях будет соблюдаться.
Если на второй позиции стоит "2", тогда сумма оставшихся двух нечетных чисел может быть равна 4, 7, 10, 13, 16, при этом исключая число 5. Очевидно, что нечетные суммы не подходят, потому что сумма нечетных чисел четная. Остаются варианты: 4, 10, 16.
Получаем комбинации первых трех цифр: 123, 321, 129, 921, 327, 723, 729, 927.
Признак делимости на 4: две последних цифры составляют число, делящееся на 4.
123Х. Х = 6
321Х. Х = 6
129Х. Х = 6
921Х. Х = 6
327Х. Х = 6.
723Х. Х = 6.
729Х. Х = 6.
927Х. Х = 6.
Четвертая цифра - 6, пятая - 5.
Признак делимости на 6: число делится на 2 и на 3, то есть оно четное и сумма цифр кратна 3.
12365Х и 32165Х. Сумма остальных цифр 17, Х = 4
12965Х и 92165Х. Сумма остальных цифр 23, Х = 4.
32765Х и 72365Х. Сумма остальных цифр 23, Х = 4.
72965Х и 92765Х. Сумма остальных цифр 29, Х = 4.
Шестая цифра - 4, значит восьмая - 8.
Чтобы определить седьмую цифру, воспользуемся признаком делимости на 8.
Число делится на 8, когда три последние цифры составляют число, делящееся на 8. Трёхзначное число делится на 8 тогда и только тогда, когда цифра в разряде единиц, сложенная с удвоенной цифрой десятков и учетверённой цифрой сотен, делится на 8.
NNN654X8. 8+2Х+16 должна делиться на 8
123654Х8 и 321654Х8. Оставшиеся цифры 7 и 9, решений нет
129654Х8 и 921654Х8. Оставшиеся цифры 3 и 7, решений нет
327654Х8 и 723654Х8. Оставшиеся цифры 1 и 9, решений нет
729654Х8 и 927654Х8. Оставшиеся цифры 1 и 3, решений нет.
Значит вторая цифра - не два.
Если на второй позиции стоит "4", тогда сумма оставшихся двух нечетных чисел может быть равна 2, 5, 8, 11, 14, при этом исключая число 5. Очевидно, что нечетные суммы не подходят, потому что сумма нечетных чисел четная. Остаются варианты:2, 8, 14. Но вариант 2 не набирается разными нечетными, вариант 14 без использования числа 5 - тоже, остается 8.
Получаем комбинации первых трех цифр: 147, 741.
Признак делимости на 4: две последних цифры составляют число, делящееся на 4.
147Х. Х = 6 или Х = 2
741Х. Х = 6 или Х = 2
Четвертая цифра - 6 или 2, пятая - 5.
Признак делимости на 6: число делится на 2 и на 3, то есть оно четное и сумма цифр кратна 3.
14765Х и 74165Х. Сумма остальных цифр 23, Х = 8.
14725Х и 74125Х. Сумма остальных цифр 19, Х = 8
Шестая цифра - 8, значит восьмая - 2 или 6.
Чтобы определить седьмую цифру, воспользуемся признаком делимости на 8.
Число делится на 8, когда три последние цифры составляют число, делящееся на 8. Трёхзначное число делится на 8 тогда и только тогда, когда цифра в разряде единиц, сложенная с удвоенной цифрой десятков и учетверённой цифрой сотен, делится на 8.
NNN658X2. 2+2Х+32 должна делиться на 8
147658Х2 и 741658Х2. Оставшиеся цифры 3 и 9, подходит вариант "3".
Возможные комбинации: 147658329 и 741658329.
NNN258Х6. 6+2Х+32 должна делиться на 8
147258Х6 и 741258Х6. Оставшиеся цифры 3 и 9, подходит вариант "9".
Возможные комбинации: 147258963 и 741258963.
Проверяем деление на "7".
Число делится на 7 тогда и только тогда, когда модуль алгебраической суммы чисел, образующих нечётные группы по три цифры (начиная с единиц), взятых со знаком «+», и чётных со знаком «-» делится на 7. Например, 138 689 257 делится на 7, так как на 7 делится |138-689+257|=294.
Число делится на 7 тогда, когда утроенное число десятков, сложенное с цифрой в разряде единиц, делится на 7. 29*3+4 = 61.
Проверяем:
|1-476+583| = 108, 10*3 +2 = 32, не делится.
|7-416+583| = 174, 17*3 +4 = 55, не делится.
|1-472+589| = 118, 11*3 +8 = 41, не делится.
|7-412+589| = 184, 18*3 +4 = 58, не делится.
Значит, вторая цифра - не 4.
Если на второй позиции стоит "6", тогда сумма оставшихся двух нечетных чисел может быть равна 3, 6, 9, 12, 15, при этом исключая число 5. Очевидно, что нечетные суммы не подходят, потому что сумма нечетных чисел четная. Остаются варианты:6,12. Но вариант 6 не набирается разными нечетными без использования числа 5, остается 12 (3 и 9).
Получаем комбинации первых трех цифр: 369, 963.
Признак делимости на 4: две последних цифры составляют число, делящееся на 4.
369Х. Х = 2
963Х. Х = 2
Четвертая цифра - 2, пятая - 5.
Признак делимости на 6: число делится на 2 и на 3, то есть оно четное и сумма цифр кратна 3.
36925Х и 96325Х. Сумма остальных цифр 25, Х = 8.
Шестая цифра - 8, значит восьмая - 4.
369258N4N или 963258N4N
Чтобы определить седьмую цифру, воспользуемся признаком делимости на 8.
Число делится на 8, когда три последние цифры составляют число, делящееся на 8. Трёхзначное число делится на 8 тогда и только тогда, когда цифра в разряде единиц, сложенная с удвоенной цифрой десятков и учетверённой цифрой сотен, делится на 8.
N6N258X4. 4+2Х+32 должна делиться на 8
369258N4 и 963258Х4. Оставшиеся цифры 1 и 7, подходящих вариантов нет.
Значит, вторая цифра - не 6.
Если на второй позиции стоит "8", тогда сумма оставшихся двух нечетных чисел может быть равна 4, 7, 10, 13, 16, при этом исключая число 5. Очевидно, что нечетные суммы не подходят, потому что сумма нечетных чисел четная. Остаются варианты:4,10,16.
Получаем комбинации первых трех цифр: 183, 381, 387, 783, 789, 987.
Признак делимости на 4: две последних цифры составляют число, делящееся на 4.
183Х и 381Х. Х = 2 или 6
387Х и 783Х. Х = 2 или 6
789Х и 987Х. Х = 2 или 6
Четвертая цифра - 6 или 2, пятая - 5.
Признак делимости на 6: число делится на 2 и на 3, то есть оно четное и сумма цифр кратна 3.
18365Х и 38165Х. Сумма остальных цифр 23, Х = 4.
18325Х и 38125Х. Сумма остальных цифр 19, вариантов нет.
38765Х и 78365Х. Сумма остальных цифр 29, Х = 4
38725Х и 78325Х. Сумма остальных цифр 25, вариантов нет
78965Х и 98765Х. Сумма остальных цифр 35, Х = 4
78925Х и 98725Х. Сумма остальных цифр 31, вариантов нет
Значит, шестая цифра - 4, а восьмая - 2.
Возможные комбинации: 183654N2N, 381654N2N, 387654N2N, 783654N2N, 789654N2N, 987654N2N
Чтобы определить седьмую цифру, воспользуемся признаком делимости на 8.
Число делится на 8, когда три последние цифры составляют число, делящееся на 8. Трёхзначное число делится на 8 тогда и только тогда, когда цифра в разряде единиц, сложенная с удвоенной цифрой десятков и учетверённой цифрой сотен, делится на 8.
NNN654X2. 2+2Х+16 должна делиться на 8
183654Х2 и 381654X2. Оставшиеся цифры 7 и 9, подходит вариант "7".
387654X2 и 783654X2. Оставшиеся цифры 1 и 9, вариантов нет.
789654Х2 и 987654Х2. Оставшиеся цифры 1 и 3, подходит вариант "3".
.
Возможные комбинации: 183654729, 381654729, 789654321 и 987654321.
Проверяем деление на "7".
Число делится на 7 тогда и только тогда, когда модуль алгебраической суммы чисел, образующих нечётные группы по три цифры (начиная с единиц), взятых со знаком «+», и чётных со знаком «-» делится на 7.
Число делится на 7 тогда, когда утроенное число десятков, сложенное с цифрой в разряде единиц, делится на 7.
Проверяем:
|1-836+547| = 288, 28*3 +8 = 92, не делится.
|3-816+547| = 266, 26*3 +6 = 84, делится.
|7-896+543| = 346, 34*3 +6 = 108, не делится.
|9-876+543| = 324, 32*3 +4 = 100, не делится.
Значит, единственный правильный ответ:
381654729
