Разбираем нестандартную задачу, которая учит строить графы и работать с делимостью
Условие
Выпишите в ряд все цифры от 1 до 9 так, чтобы любое число, составленное из двух соседних цифр, делилось либо на 7, либо на 13.
👉 Пример: если рядом стоят 7 и 8, получается число 78. Оно делится на 13 (78 : 13 = 6). Значит, такая пара подходит.
Шаг 1. Составляем список разрешённых чисел
Выпишем все двузначные числа из цифр 1–9, которые делятся на 7 или на 13.
✅ Кратные 7 (делятся на 7): 14, 21, 28, 35, 42, 49, 56, 63, 77, 84, 91, 98
✅ Кратные 13 (делятся на 13): 13, 26, 39, 52, 65, 78, 91
❗ Важно:
- Число 77 есть в списке кратных 7, но в нашем ряду каждая цифра встречается только один раз. Для числа 77 нужны две семёрки подряд, а у нас только одна семёрка. Поэтому 77 мы не сможем использовать в построении ряда.
- Число 91 есть в обоих списках.
Шаг 2. Строим ориентированный граф
Что такое ориентированный граф? Это точки (их называют вершинами), соединённые стрелками (их называют ориентированными рёбрами). Каждая стрелка показывает направление. Например, стрелка 1 → 3 означает, что из 1 можно попасть в 3. Если есть и стрелка 3 → 1, значит, можно двигаться в обе стороны.
В нашей задаче:
- Вершины — это цифры от 1 до 9.
- Стрелку от X к Y рисуем, если число XY есть в наших списках (то есть делится на 7 или на 13).
Разберём на примерах:
Смотрим на первую цифру числа — это будет начало стрелки. Смотрим на вторую цифру числа — это будет конец стрелки.
👉 Число 13 есть в списке. Первая цифра 1, вторая 3. Значит, рисуем стрелку 1 → 3.
👉 Число 14 есть в списке. Первая цифра 1, вторая 4. Значит, рисуем стрелку 1 → 4.
👉 Число 17? Его нет в списке. Значит, стрелки 1 → 7 НЕТ.
👉 Число 21 есть. Первая цифра 2, вторая 1. Значит, стрелка 2 → 1.
👉 Число 26 есть. Стрелка 2 → 6.
👉 Число 28 есть. Стрелка 2 → 8.
И так далее — для каждого числа из наших списков.
Вот какие стрелки получились:
🔹 Из 1 → 3, 4
🔹 Из 2 → 1, 6, 8
🔹 Из 3 → 5, 9
🔹 Из 4 → 2, 9
🔹 Из 5 → 2, 6
🔹 Из 6 → 3, 5
🔹 Из 7 → 8
🔹 Из 8 → 4
🔹 Из 9 → 1, 8
Шаг 3. С какой цифры начинать?
Посмотрим на цифру 7.
🔸 Из неё идёт одна стрелка → к 8.
🔸 А есть ли стрелки, которые ведут к 7?
❌ В вершину 7 не ведёт ни одно ребро (стрелки).
Это важное свойство: если в вершину нельзя попасть из другой, она может быть только самой первой в ряду.
✅ Ряд начинается с 7.
Шаг 4. Строим цепочку
Теперь идём по стрелкам, каждый раз переходя в новую (ещё не использованную) цифру. Если есть выбор — пробуем один вариант.
- С 7 можно только в 8 → 8
- С 8 можно только в 4 → 4
- С 4 можно в 2 или 9 → выбираем 9 (почему 9? Потому что позже это приведёт к полному пути, а выбор 2 заведёт в тупик — можешь проверить сам в вопросе для самопроверки).
- С 9 можно в 1 или 8 (8 уже была) → 1
- С 1 можно в 3 или 4 (4 была) → 3
- С 3 можно в 5 или 9 (9 была) → 5
- С 5 можно в 2 или 6 → выбираем 2
- С 2 можно в 1, 6, 8 (1 и 8 уже были) → остаётся 6
- С 6 можно в 3 или 5 (оба уже были) → идти некуда, но и все цифры уже использованы!
Получился ряд:
7 8 4 9 1 3 5 2 6
Шаг 5. Проверка
Убедимся, что каждая пара даёт число из наших списков.
- 7–8 → 78 : 13 = 6 ✅
- 8–4 → 84 : 7 = 12 ✅
- 4–9 → 49 : 7 = 7 ✅
- 9–1 → 91 : 13 = 7 ✅
- 1–3 → 13 : 13 = 1 ✅
- 3–5 → 35 : 7 = 5 ✅
- 5–2 → 52 : 13 = 4 ✅
- 2–6 → 26 : 13 = 2 ✅
Все 8 пар подходят!
✅ Ответ: 7 8 4 9 1 3 5 2 6
Что важно запомнить
- Если в вершину не входит ни одной стрелки — она может быть только началом.
- Графы помогают решать задачи, где простой перебор занял бы слишком много времени.
- Такой способ называется поиск пути, проходящего через все вершины (в старших классах его назовут гамильтоновым путём).
Вопрос для самопроверки
А что было бы, если бы мы на шаге 4 из цифры 4 пошли не в 9, а в 2? Дойдём ли мы до конца? Попробуйте проверить самостоятельно!
Понравился разбор? Подписывайтесь на канал, чтобы не пропускать новые статьи по математике и подготовке к ОГЭ!
#Математика #7Класс #ВиС #ВероятностьИСтатистика #Графы #ОриентированныйГраф #ЗадачиСЦифрами #Алгебра #РазборЗадач #ПодготовкаКОГЭ #Образование