Задача по математике

Овца

Универсальный способ состоит в том, чтобы читать условие задачи, выделять все известные и неизвестные числовые величины, относящиеся к вычислениям, обозначать неизвестные значками x, y, z ... (можно любыми другими, но традиционно используют такие). Составлять простые уравнения вида a=b+c, a=b-c, a=b⋅c или a=b:c там, где это возможно, но не пытаться составлять более сложные уравнения - пусть лучше будет много простых уравнений, чем мало сложных. Давайте внимательно читать условие задачи:
Фрагмент текста задачи Величины Уравнения Объяснение
Дано 8 домов 8 ←вел.1 Величина №1 известна и равна 8.
и 8 колодцев. Дорога может соединять дом и колодец (но не два дома и не два колодца). 8 ←вел.2
x ←вел.3 x = 8 + 8 Величина №2 известна и равна 8.
Величина №3 пока неизвестна, обозначим её как "x", она есть сумма величин №1 и №2.
Какое минимальное количество дорог нужно для того, чтобы y ←ответ x = 3 ⋅ y Результат (штука) пока неизвестен, обозначим его как "y" (это будет ответ). Величина №3 есть произведение величин №5 и №4 (ответ).
от любого дома можно было добраться до любого колодца, пройдя не более чем по 3 дорогам? 3 ←вел.5 Величина №4 известна и равна 3.

Для того чтобы от каждого дома можно было дойти по дорогам до двух колодцев, достаточно трёх дорог.
Чтобы доказать это, рассмотрим один из домов в качестве центра графа дорог и предположим, что от него можно дойти до каждого из остальных семи домов по отдельной дороге. Тогда от этого дома можно дойти по дорогам минимум до трёх разных колодцев (иначе они образуют связную компоненту, а значит, до всех остальных колодцев тоже можно дойти).
Теперь добавим ещё две дороги, соединяющие этот дом с другими двумя домами, так, чтобы каждая из этих дорог соединяла его с домом, который не был соединён дорогой с каким-либо из колодцев. Таким образом, от каждого из этих двух домов можно дойти до ещё одного колодца, не считая уже соединённых с ними. Итого получается три разных колодца, соединённых дорогами с данным домом.
Итак, мы добавили только три дороги, и теперь от каждого дома можно дойти минимум до двух разных колодцев. Более того, мы не использовали более трёх дорог, поэтому нельзя пройти больше, чем по этим трём дорогам.
Ответ: достаточно трёх дорог.