Реши понятно задачу по статистике Как решить задачу по статистике В стране есть 12 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если сумма чисел, составленное из цифр-названий этих городов, делится на 3. В) сколькими путями можно добраться в город 7?
Короче говоря, задача про граф: города 1–12, ребро между i и j существует тогда и только тогда, когда сумма цифр чисел i и j делится на 3. Нужно посчитать числа путей до города 7.
1) Разложим города по сумме цифр mod 3.
- Сумма цифр для i = 1..12:
- 1→1, 2→2, 3→3→0, 4→4→1, 5→5→2, 6→6→0, 7→7→1, 8→8→2, 9→9→0, 10→1, 11→2, 12→3→0.
- Значит по модулю 3:
- Класс 0: {3, 6, 9, 12}
- Класс 1: {1, 4, 7, 10}
- Класс 2: {2, 5, 8, 11}
2) Условие связи: две города соединены если (сумма цифр i) + (сумма цифр j) ≡ 0 mod 3.
- В классах: 0+0 ≡ 0 (соединены внутри класса 0) — это полный граф K4 между {3,6,9,12}.
- 1+2 ≡ 0 — между классами 1 и 2 образуется полное двудольноеGraph K4,4 между {1,4,7,10} и {2,5,8,11}.
- Между классами 0 и (1 или 2) соединения нет, так что граф распадается на две компоненты: C0 = K4 по узлам {3,6,9,12} и C12 = K4,4 между {1,4,7,10} и {2,5,8,11}.
3) Город 7 относится к классу 1, значит нас волнит только компоненту C12 (K4,4) и пути из города 1 в город 7 внутри нее. Городов, относящихся к классу 0, в путь не залезут.
4) Считаем простые пути из города 1 в город 7 в графе K4,4 (A = {1,4,7,10}, B = {2,5,8,11}):
- Пути длины 2 (1 - b - 7): b выбирается из всех 4 узлов B → 4 путя.
- Пути длины 4 (1 - b1 - a1 - b2 - 7):
- выбрать b1 из 4 узлов B: 4 варианта
- выбрать a1 из A \ {1,7} — осталось 2 узла: 2 варианта
- выбрать b2 из B \ {b1} — остаётся 3 варианта
- всего: 4 × 2 × 3 = 24 путя
- Пути длины 6 (1 - b1 - a1 - b2 - a2 - b3 - 7):
- выбрать упорядоченную тройку узлов B (b1, b2, b3 все различны): 4 × 3 × 2 = 24 варианта
- выбрать упорядоченную пару узлов A (a1, a2) из оставшихся двух узлов A \ {1,7}: 2 варианта (это просто перестановка двух оставшихся)
- всего: 24 × 2 = 48 путей
5) Итого путей из города 1 в город 7: 4 + 24 + 48 = 76.
Ответ: 76 путей (из города 1 в город 7). Если старт не указан в задаче, принято считать именно такие начальные условия: из города 1 в город 7.
