6
2

Вчера мне встретилась такая симпатичная задача (условие я слегка видоизменил). Из цифр от 0 до 9 требуется составить десятизначное число, в котором каждая десятичная цифра используется ровно по разу. Требуется, чтобы число, образованное первыми $%k$% цифрами данного числа, делилось на $%k$% для любого $%k$% от $%1$% до $%10$%.

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

задан 28 Дек '13 10:37

10|600 символов нужно символов осталось
6

Очевидно, что последней цифрой числа должен быть 0, а на пятом месте стоит 5. Также на всех четных местах стоят четные цифры, автоматически на нечетных - нечетные цифры. Сумма первых трех цифр делится на 3, сумма первых шести цифр также делится на 3, тогда сумма 4-ой, 5-ой и 6-ой цифры также делится на 3. Но пятая цифра равна 5, тогда сумма 4-ой и 6-ой должна давать остаток 1 при делении на 3, при этом обе эти цифры четные. Сумма двух чисел дает остаток 1 при делении на 3 только в 3 случаях: остаток 1 + остаток 0, остаток 0 + остаток 1, остаток 2 + остаток 2. Среди четных чисел меньших 9 только два числа с остатком 2 при делении на 3, а именно 2 и 8. Четная цифра, которая при делении на 3 дает остаток 1 это 4, а делится без остатка - 6. Исходное число должно иметь один из четырех следующих видов: * 2 5 8 * * 0 или * * 8 5 2 * * 0 или * * 4 5 6 * * 0 или * * 6 5 4 * * 0. Воспользуемся делимостью на 4 числа, составленного из первых 4 цифр. Второй и третий варианты не удовлетворяют этому условию, так как нет двузначного числа первая цифра которого нечетная, вторая равна 4 или 8 и при этом оно делится на 4. Остаются варианты * * 2 5 8 * * 0 или * * 6 5 4 * * 0. Далее будем использовать делимость на 8. В первом случае (для числа * * 2 5 8 * * 0 ) число 8 * должно делится на 8. При этом на втором месте стоит одна из нечетных цифр (1,3,7,9), а на последнем одна из оставшихся четных (6,4). То есть 8 вариантов: 816, 814, 836, 834, 876, 874, 896 и 894. Поставленному условию удовлетворяет только 816 и 896. * 2 5 8 1 6 * 0 или * * 2 5 8 9 6 * 0. В каждом из этих случаев оставшуюся четную цифру 4 ставим на второе место: * 4 * 2 5 8 1 6 * 0 или * 4 * 2 5 8 9 6 * 0. Используем делимость на 3 числа * 4 . В распоряжении остались только цифры 3,7 и 9. Но ни один из этих вариантов не удовлетворяет условию, так как ни одна из 6 пар в сумме с цифрой 4 не дает остатка 0 при делении на 3. Таким образом первый случай привел к противоречию. Для второго случая (для числа * * 6 5 4 * * 0 ) аналогичные рассуждения относительно делимости на 8 позволяют на 8-ое место поставить цифру 2. Автоматически цифра 8 становится на второе место: * 8 * 6 5 4 * 2 * 0. Для делимости на 8 на седьмом месте может стоять либо 3, либо 7. В силу делимости на 3 числа * 8 * имеем: одна из цифр делится на 3, а вторая дает остаток 1 при делимости на 3. В распоряжении остались нечетные цифры: 1,3,7 и 9. Таким образом имеем следующие варианты: 183, 381, 189, 981, 387, 783, 789 и 987. Получаем перебор из 16 вариантов и осталось реализовать делимость на 7. Из чисел 1836547, 1836549, 3816547, 3816549, 1896543, 1896547, 9816543, 9816547, 3876541, 3876549, 7836541, 7836549, 7896541, 7896543, 9876541, 9876543. С учетом условия на 7 место, остаются только числа 1836547, 3816547, 1896543, 1896547, 9816543, 9816547, 7896543 и 9876543. Среди оставшихся чисел только 3816547 делится на 7. В итоге имеем ответ: 3816547290.

ссылка

отвечен 17 Янв '14 11:28

изменен 17 Янв '14 14:40

@aid78: тут почти всё верно, но надо исправить одну мелкую неточность. Я имею в виду вот это положение: "Среди четных чисел меньших 9 нету двух с остатком 2 при делении на 3, только одно число 8." На самом деле, такие числа имеются -- это 2 и 8. Соответственно, перебор придётся чуть расширить, но там всё легко доводится до конца теми же способами. Можно также чуть подсократить проверку, связанную с делимостью на 7, если обратить внимание на то число, которое должно делиться на 8. Но в целом всё хорошо -- после исправления я готов принять Ваш ответ.

(17 Янв '14 12:04) falcao

@aid78: теперь всё верно; ответ я принимаю. Маленькое замечание по поводу делимости на 7: там можно использовать признак делимости, хотя он и не очень удобный. Но выгода в том, что для тех цифр, положение которых зафиксировано, мы можем один раз подсчитать остаток, а для оставшихся цифр в количестве 2-3 штук проверять, подходят ли их положения.

(17 Янв '14 19:15) falcao

@falcao: спасибо за ссылку и за решение. Почти со всем согласен. Я потратил на эту задачу некоторое время. Постараюсь опубликовать здесь вылизанное до блеска своё решение. Коллекционирую задачи такого уровня для занятий со школьниками. Эта задача хороша тем, что решать можно с 5-ым классом...

(3 Авг '17 23:13) kipot_l

@kipot_l: да, задача хорошая -- в том числе для разбора со школьниками. у меня где-то было записано и своё решение, но ссылку сейчас не помню. Позже попробую отыскать.

(4 Авг '17 1:03) falcao

@falcao: вот я опубликовал свой вариант решения, прошу сравнить и отрецензировать, если можно.

(12 Авг '17 14:43) kipot_l
10|600 символов нужно символов осталось
1

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

Решение. Искомое число обозначим abcdefghkl. Для уменьшения количества вариантов перебора при поиске решения используем признаки делимости на 2, 3, 4, 5 и 8. Признак делимости на 7 не используем ввиду его экзотичности. Начинаем с тривиальных утверждений, которых немало:

  1. Цифра 5 может стоять только на 5-ом месте, 0 - только на 10-м;

  2. Чётные цифры стоят на чётных местах;

  3. Нечётные цифры, соответственно, на нечётных местах.

  4. Суммы всех «троек» делятся на три;

  5. Число cd делится на 4;

  6. Число fgh делится на 8 (!);

  7. Делимость на 9 присутствует "на автомате".

Далее ищем решение, выбирая оптимальные шаги на основе пунктов 1) – 6) : Рядом с цифрой 5 могут стоять пары 6 и 4, или 2 и 8, и только в этом порядке; смотри п. 2) и п. 5) . Получаем два варианта:

        I.    _ _ _ 6 5 4 _ _ _
        II.     _ _ _ 2 5 8 _ _ _

Рассмотрим вариант I: Используя п. 6), получаем 2 случая:

Ia. _ 8 _ 654 32 _ ; остались цифры 1, 7, 9; используя для Ia п. 4), получаем 4 случая:

  1. 789 654 321
  2. 987 654 321
  3. 981 654 327
  4. 189 654 327

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

Ib. _ 8 _ 654 72 _ ; остались цифры 1, 3, 9; используя для Ib п. 4), получаем 4 случая:

  1. 189 654 723
  2. 981 654 723
  3. 381 654 729
  4. 183 654 729

Проверяем руками, что делимость на 7 присутствует только в 3-м случае.

Это решение задачи - 3 816 547 290 .

Рассмотрим вариант II: Используя п. 6), получаем 2 случая:

IIa. _ 4 _ 258 16 _ ; остались цифры 3, 7, 9; используя для IIa п. 4), получаем, что первая тройка никогда не делится на 3.

IIb. _ 4 _ 258 96 _ ; остались цифры 1, 3, 7; используя для IIb п. 4), получаем только 2 случая:

  1. 147 258 963
  2. 741 258 963

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

Итак, задача имеет единственное решение. Для решения задачи нам потребовалось проверить руками делимость на 7 в 10 случаях.

ссылка

отвечен 12 Авг '17 14:00

изменен 12 Авг '17 14:31

@kipot_l: я думаю, у Вас хороший способ решения, но я сейчас не могу его сравнить с тем способом, которым решал я сам. Помню, что у меня использовался признак делимости на 7. Согласен, что он "экзотичен", но в случае, если какие-то цифры фиксированы, проще вычислить значение соответствующей линейной комбинации. Я думал, что сохранилось обсуждение где-нибудь в ЖЖ, но либо это не так, либо я плохо искал.

(12 Авг '17 19:45) falcao

@falcao: ничего нового в моём решении нет, просто я аккуратно, как нас учили в 131-й школе, зачистил опубликованное первым решение. А признак делимости на 7 оставлю на десерт, как в том анекдоте:

-- Сынок, всё это только для отличников!

(12 Авг '17 23:51) kipot_l
10|600 символов нужно символов осталось
0

Пусть I(i,s) = 1 если, число образованное первыми i + 1 чисел удовлетворяет условию из задачи, используя числа из множества s. 0 иначе.

Имеем: I(i,s) -> Element[k,s] ? I(i + 1, s - 2^k) : 0

Элементарно решив это соотношение получаем: 3816547290

Следующее число существует для 14-ичной системы счисления: [9,12,3,10,5,4,7,6,11,8,1,2,13,0]

ссылка

отвечен 27 Дек '14 18:06

изменен 27 Дек '14 18:08

А что значит "элементарно решив"?

(27 Дек '14 19:33) falcao

Это значит найти max(0, I(i + 1, s - 2^k)) для 0<=k<(система исчисления задачи)

(27 Дек '14 19:37) LotsOvPhan

@LotsOvPhan: мне неясен смысл слова "элементарно". В разговорной речи это слово обычно означает что-то типа "очень легко". В данном случае, как я понимаю, речь идёт о компьютерном переборе. Понятно, что он возможен, так как перебрать 10! вариантов для компьютера не составит труда. Но здесь имелось в виду нахождение решения вручную, притом проверяемого человеком.

(27 Дек '14 20:18) falcao

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

(27 Дек '14 20:32) LotsOvPhan
1

@LotsOvPhan: Я не понимаю. Объясните, пожалуйста!

(27 Дек '14 21:26) EdwardTurJ
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×879

задан
28 Дек '13 10:37

показан
12604 раза

обновлен
12 Авг '17 23:54

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru