ГДЗ по вероятности и статистике, 10 класс, Высоцкий, номер 124: *. Эйлерова характеристика

Нам нужно составить последовательность из цифр 1,2,3,4,5,6,7,8,9 (каждая используется ровно один раз). Любые две соседние цифры образуют двузначное число, которое должно делиться на 7 или на 13.

Давайте выпишем все возможные двузначные числа с различными ненулевыми цифрами, которые делятся на 7 или на 13:

• Делящиеся на 7: 14,21,28,35,42,49,56,63,70 (не подходит, есть 0), 77 (повтор), 84,91,98. Отбираем те, где цифры различны и не равны нулю: 14,21,28,35,42,49,56,63,84,91,98.
• Делящиеся на 13: 13,26,39,52,65,78,91. Все они подходят по условию уникальности цифр внутри числа.

Объединим эти списки в множество допустимых переходов «первая цифра → вторая цифра»:

Задача сводится к поиску гамильтонова пути в ориентированном графе, вершинами которого являются цифры от 1 до 9, а рёбрами — допустимые переходы из таблицы выше.

Заметим особенности некоторых вершин:

• Цифра 7 имеет только один исходящий переход: 7→8. Значит, если 7 стоит не в конце ряда, за ней обязательно должна следовать 8.
• Цифра 8 имеет только один входящий переход? Нет, посмотрим на столбец "Куда":
  • В 1 можно попасть из 2,9.
  • В 2 можно попасть из 4,5.
  • В 3 можно попасть из 1,6.
  • В 4 можно попасть из 1,8.
  • В 5 можно попасть из 3,6.
  • В 6 можно попасть из 2,5.
  • В 7 нельзя попасть ниоткуда (в списке нет чисел вида X7, делящихся на 7 или 13 с разными цифрами: 17,27,37... не делятся). Это значит, что 7 должна быть первой цифрой в ряду .

Итак, начало ряда фиксировано: 7.

Раз 7 первая, то следующий шаг строго определён: 7→8.

Текущий ряд: 7,8.

Теперь смотрим, куда можно пойти из 8. Из таблицы: 8→4 (число 84 делится на 7). Других вариантов нет.

Текущий ряд: 7,8,4.

Из 4 варианты: 4→2 (42) или 4→9 (49).

Попробуем ветвление:

1. Вариант А: 4→2. Ряд: 7,8,4,2. Из 2 варианты: 2→1 (21) или 2→6 (26).
   • Если 2→1: Ряд 7,8,4,2,1. Из 1: 1→3 (13) или 1→4 (занято). Значит 1→3. Ряд 7,8,4,2,1,3. Из 3: 3→5 (35) или 3→9 (39).
     • Если 3→5: Ряд ...,3,5. Из 5: 5→6 (56) или 5→2 (занято). Значит 5→6. Ряд 7,8,4,2,1,3,5,6. Осталась цифра 9. Из 6 варианты: 6→3 (занято) или 6→5 (занято). Тупик. Не подходит.
     • Если 3→9: Ряд ...,3,9. Из 9: 9→1 (занято) или 9→8 (занято). Тупик. Не подходит.
   • Если 2→6: Ряд 7,8,4,2,6. Из 6: 6→3 (63) или 6→5 (65).
     • Если 6→3: Ряд ...,6,3. Из 3: 3→5 (35) или 3→9 (39).
       • Если 3→5: Ряд ...,3,5. Из 5: 5→2 (занято) или 5→6 (занято). Тупик.
       • Если 3→9: Ряд ...,3,9. Из 9: 9→1 (91) или 9→8 (занято). Значит 9→1. Ряд 7,8,4,2,6,3,9,1. Осталась цифра 5. Из 1: 1→4 (занято) или 1→3 (занято). Тупик.
     • Если 6→5: Ряд ...,6,5. Из 5: 5→2 (занято) или 5→6 (занято). Тупик.
2. Вариант Б: 4→9. Ряд: 7,8,4,9. Из 9 варианты: 9→1 (91) или 9→8 (занято). Значит, 9→1.

   Текущий ряд: 7,8,4,9,1.

   Из 1 варианты: 1→3 (13) или 1→4 (занято). Значит, 1→3.

   Текущий ряд: 7,8,4,9,1,3.

   Из 3 варианты: 3→5 (35) или 3→9 (занято). Значит, 3→5.

   Текущий ряд: 7,8,4,9,1,3,5.

   Из 5 варианты: 5→6 (56) или 5→2 (52).

   • Если 5→6: Ряд ...,5,6. Из 6: 6→3 (занято) или 6→5 (занято). Тупик.
   • Если 5→2: Ряд ...,5,2. Из 2: 2→1 (занято) или 2→8 (занято) или 2→6 (26). Значит, 2→6.

   Текущий ряд: 7,8,4,9,1,3,5,2,6.

   Проверим использованные цифры: 1,2,3,4,5,6,7,8,9. Все использованы по одному разу.

   Проверим последний элемент 6. Он является концом ряда, поэтому исходящих переходов от него проверять не нужно.

Полученная последовательность: 7,8,4,9,1,3,5,2,6.

Выпишем все пары соседних цифр и проверим их делимость:

1. 78: делится на 13 (78=13·6). OK.
2. 84: делится на 7 (84=7·12). OK.
3. 49: делится на 7 (49=7·7). OK.
4. 91: делится на 13 (91=13·7). OK.
5. 13: делится на 13 (13=13·1). OK.
6. 35: делится на 7 (35=7·5). OK.
7. 52: делится на 13 (52=13·4). OK.
8. 26: делится на 13 (26=13·2). OK.

Все условия выполнены.