Номер 10, страница 51, часть 2 - гдз по математике 4 класс учебник Дорофеев, Миракова

10 На международную конференцию приехали 10 делегатов, не понимающих языка друг друга. Какое наименьшее число переводчиков требуется для обслуживания делегатов конференции при условии, что каждый переводчик знает только два языка?

Для решения этой задачи представим каждого из 10 делегатов как носителя своего уникального языка, так как по условию они не понимают друг друга. Таким образом, у нас есть 10 различных языков. Цель состоит в том, чтобы обеспечить возможность перевода с любого из этих языков на любой другой, возможно, через цепочку промежуточных переводов.

Эту задачу удобно смоделировать с помощью теории графов. Пусть каждый из 10 языков будет вершиной графа. Каждый переводчик, знающий два языка, представляет собой ребро, соединяющее две соответствующие вершины. Чтобы все делегаты могли общаться между собой, граф, состоящий из языков-вершин и переводчиков-ребер, должен быть связным. Связный граф — это граф, в котором существует путь между любыми двумя его вершинами.

Из теории графов известно, что минимальное количество ребер, необходимое для того, чтобы связать граф с $n$ вершинами, равно $n-1$. Если ребер будет меньше, чем $n-1$, то граф обязательно будет несвязным, то есть распадется как минимум на две части, между которыми нет связи.

В нашем случае количество вершин (языков) $n = 10$.Следовательно, минимальное число ребер (переводчиков), необходимое для обеспечения связи между всеми языками, составляет:$k = n - 1 = 10 - 1 = 9$

Можно доказать, что 9 переводчиков достаточно. Например, можно организовать работу следующим образом: выбрать один язык в качестве центрального (назовем его Я₁) и нанять 9 переводчиков. Каждый из них будет знать язык Я₁ и один из оставшихся 9 языков (Я₂, Я₃, ..., Я₁₀).

Такая схема будет выглядеть так:

• Переводчик 1: знает языки Я₁ и Я₂
• Переводчик 2: знает языки Я₁ и Я₃
• ...
• Переводчик 9: знает языки Я₁ и Я₁₀

При такой организации любой делегат (например, говорящий на языке Я₄) сможет пообщаться с любым другим (например, говорящим на языке Я₇). Перевод будет осуществляться через центральный язык: Я₄ ↔ Я₁ ↔ Я₇. Таким образом, все делегаты смогут общаться друг с другом.

Меньшего количества переводчиков (например, 8) будет недостаточно, так как граф с 10 вершинами и 8 ребрами не может быть связным.

Ответ: 9.