В компании из 30 человек некоторые люди знакомы между собой (знакомство взаимно) Известно, что среди любых четырех людей один из них знает хотя бы двух из остальных. Докажите, что можно выбрать 29 человек и выстроить их так, чтобы любые два соседа были знакомы.

Докажем это утверждение методом математической индукции.

База индукции: для 4 человек это утверждение верно, так как из условия следует, что среди любых четырех людей один из них знает хотя бы двух из остальных, следовательно, можно выстроить их так, чтобы любые два соседа были знакомы.

Предположение индукции: предположим, что утверждение верно для n человек.

Шаг индукции: добавим еще одного человека к группе из n человек. По предположению индукции, можно выстроить этих n+1 человек так, чтобы любые два соседа были знакомы. Рассмотрим теперь группу из n+2 человек. Разделим эту группу на две подгруппы: первая подгруппа из n человек, вторая подгруппа из двух человек. По предположению индукции первую подгруппу можно выстроить так, чтобы любые два соседа были знакомы. Рассмотрим вторую подгруппу из двух человек. По условию задачи среди любых четырех людей один из них знает хотя бы двух из остальных, значит, можно выстроить эти два человека так, чтобы они были знакомы. Таким образом, можно выстроить всю группу из n+2 человек так, чтобы любые два соседа были знакомы.

Таким образом, по принципу математической индукции доказано, что можно выбрать 29 человек и выстроить их так, чтобы любые два соседа были знакомы.