В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с семью другими. Верно ли, что из любого города можно добраться до любого другого, возможно, проезжая через другие города? В случае ответа «да», запишите в ответ цифру 1, если «нет» — цифру 0.

Решение:

Данная задача описывается теорией графов. У нас есть 15 городов (вершин графа) и дороги, соединяющие их (рёбра графа).

Условие гласит, что каждый город соединен дорогами не менее, чем с семью другими. Это означает, что степень каждой вершины в графе не менее 7 ( \( d(v) \ge 7 \) для всех вершин \( v \)).

Для того чтобы из любого города можно было добраться до любого другого, граф должен быть связным. В связном графе для любых двух вершин \( u \) и \( v \) существует путь между ними.

По теореме о связности графа, если для графа с \( n \) вершинами выполняется условие \( d(v) \ge \frac{n-1}{2} \) для всех вершин \( v \), то граф является связным.

В нашем случае \( n = 15 \). Проверим условие:

\[ \frac{n-1}{2} = \frac{15-1}{2} = \frac{14}{2} = 7 \]

Так как степень каждой вершины \( d(v) \ge 7 \), что равно \( \frac{n-1}{2} \), то граф является связным.

Следовательно, из любого города можно добраться до любого другого.

Ответ: 1