Есть схема доказательства того, что ответ 1/2. Но это явно не то решение, что имеет в виду автор: во-первых, надо знать ответ, чтобы так решать задачу, во-вторых, доказательство вовсе не в две строки. Я его даже не буду полностью приводить, набросаю только схему.
Пронумеруем для начала мосты:
Горизонтальные:
первая строка - (x1, x2, x3 )
вторая строка - (y1, y2, y3)
третья строка - (z1, z2, z3)
Вертикальные:
A, C
B, D
Каждую букву можно считать булевой переменной: 0 - мост сломан, 1 - мост цел.
Мы имеем набор из 13 нулей или единиц - всего 213 набора. Каждый набор будет или "связным" (есть маршрут с одного берега на другой), или "несвязным" (маршрута нет).
Введем "диагональное преобразование" набора мостов: все горизонтальные мосты повернем по диагонали, так чтобы строки перешли в столбцы; из вертикальных мостов оставим в покое те два, что примыкают к диагонали, а два других поменяем местами.
При таком преобразовании набор
(x1, x2, x3, A, C, y1, y2, y3, B, D, z1, z2, z3)
перейдет в набор
(x1, y1, z1, A, B, x2, y2, z2, C, D, x3, y3, z3)
(нарисуйте на бумажке, сразу будет ясно, что я имею в виду).
Далее: для данного набора из 13 нулей и единиц укажем "сопряженный" набор по следующему правилу: сначала поменяем местами координаты по вышеизложенному "диагональному преобразованию", а потом инвертируем все координаты - заменим нули на единицы, а единицы на нули.
Для каждого набора однозначно указывается один сопряженный, т.е. мы ввели взаимно однозначное отображение.
Имеет место быть следующее предположение:
Набор, сопряженный связному, будет несвязным, и наоборот - набор, сопряженный несвязному, будет связным.
Из этого предположения сразу вытекает, что несвязных наборов столько же, сколько связных, что и приводит нас в итоге к ответу 1/2.
Доказательство этого предположения основано на двух тривиальных наблюдениях:
1. Наше преобразование переводит очевидное достаточное условие связности (есть строка из единиц) в достаточное условие несвязности(есть столбец из нулей), и наоборот.
2. Если наше преобразование переводит связный набор N в несвязный, то набор, полученный из N заменой произвольного числа нулей на единицы, будет тем более переходить в несвязный (ну и опять же, наоборот).
Эти два наблюдения позволяют сконцентрироваться на некоторых наборах "минимальной связности" (или "максимальной несвязности"). Их всего 10 штук (4 с одной вертикальной перемычкой, 2 с двумя диагональными, 4 с двумя соседними перемычками), и я их просто перебрал...
PS Нет, перебор все-таки был не полный. Теперь там 12 вариантов... Короче, указанное предположение я считаю правильным, но красивое его доказательство - отдельная задача...
