138 В деревне 9 домов. Соседними будем считать участки, у которых есть общий забор. Известно, что у Петра соседи Иван и Антон, Максим сосед Ивану и Сергею, Виктор Дмитрию и Никите, а также по соседству живут Евгений с Никитой, Иван с Сергеем, Евгений с Дмитрием и Сергей с Антоном и больше соседей в деревне нет. Может ли Пётр, перелезая через заборы соседних участков, пробраться на участок к Никите?

Решение:

Представим эту задачу как граф, где дома — это вершины, а соседство — это рёбра.

Известные соседства:

• Пётр (П) — Иван (И), Антон (А)
• Максим (М) — Иван (И), Сергей (С)
• Виктор (В) — Дмитрий (Д), Никита (Н)
• Евгений (Е) — Никита (Н)
• Иван (И) — Сергей (С)
• Евгений (Е) — Дмитрий (Д)
• Сергей (С) — Антон (А)

Составим список всех рёбер (соседств):

• (П, И)
• (П, А)
• (М, И)
• (М, С)
• (В, Д)
• (В, Н)
• (Е, Н)
• (И, С)
• (Е, Д)
• (С, А)

Проверим, являются ли Иван и Сергей соседями Петра, или могут ли они быть связаны через других людей.

Пётр сосед Ивана и Антона.

Сергей — сосед Ивана и Антона.

Таким образом, Пётр и Сергей — соседи Антона и Ивана. Это означает, что Пётр может пройти к Сергею через Антона или Ивана. Например, Пётр → Антон → Сергей.

Теперь проверим, может ли Пётр добраться до Никиты.

Мы знаем, что Пётр может пройти к Сергею (П → А → С).

Сергей сосед Антона, а Пётр тоже сосед Антона.

Виктор сосед Дмитрия и Никиты.

Евгений сосед Дмитрия и Никиты.

Иван сосед Сергея.

Максим сосед Ивана и Сергея.

Чтобы Пётр добрался до Никиты, нам нужно найти путь от Петра к Никите.

Мы знаем, что Пётр → Антон → Сергей.

Сергей не является соседом Виктора, Евгения или Никиты напрямую.

Иван сосед Сергея.

Иван сосед Петра.

Мы можем пройти так: Пётр → Иван → Сергей.

Теперь посмотрим, кто сосед Сергея. Сергей сосед Антона и Ивана.

Кто сосед Ивана? Иван сосед Петра и Сергея. Максим сосед Ивана.

Мы ищем путь к Никите. Виктор сосед Никиты. Евгений сосед Никиты.

Есть ли связь между {Пётр, Иван, Сергей, Антон} и {Виктор, Дмитрий, Никита, Евгений}?

У нас есть:

• (П, И), (П, А)
• (И, С)
• (С, А)
• (В, Д), (В, Н)
• (Е, Н)
• (Е, Д)

Это два несвязных компонента.

Первый компонент: {Пётр, Иван, Сергей, Антон}.

Второй компонент: {Виктор, Дмитрий, Никита, Евгений}.

Эти два компонента не соединены никакими рёбрами (соседствами).

Поскольку нет общего соседа между этими двумя группами домов, Пётр не может перелезать через заборы и попасть на участок к Никите.

Ответ: Нет, Пётр не может пробраться на участок к Никите.