Question

Среди n человек каждые двое - либо друзья, либо враги. у каждого из этих людей ровно шесть врагов, причём враги его друзей являются его врагами. при каких n такое возможно? укажите все возможные варианты и докажите, что нет других.

Answer 1

Каждый  имеет  по  личному  врагу  и  по  5  врагов  своих  5  друзей. Любое  другое  соотношение нарушит  условие  о  6  врагах.
Поэтому,  встретились  12  человек,  у  каждого:   по  5  друзей,  одному личному  врагу  и  5  врагам,  по  поговорке.  

Answer 2

Для решения данной задачи мы будем использовать метод математической индукции.

1. Базис индукции: Для n = 1 условие задачи выполняется, так как у каждого человека нет ни друзей, ни врагов.

2. Предположение индукции: Предположим, что условие задачи выполняется для любого n ≤ k, где k - некоторое положительное целое число.

3. Шаг индукции: Докажем, что условие также выполняется для n = k + 1.

Рассмотрим первого человека. У него есть ровно 6 врагов, и эти 6 врагов не могут быть другими членами группы из n = k + 1 человека, так как каждый человек имеет ровно 6 врагов. Значит, из оставшихся n - 6 человек они могут быть только друзьями первого человека.

По предположению индукции, для группы из n - 6 человек условие задачи выполняется. То есть у каждого из них есть ровно шесть врагов, причем враги его друзей являются его врагами.

Теперь рассмотрим врагов первого человека. Каждый из них может быть друзьями других n - 6 человек, так как по условию у каждого человека должно быть ровно 6 врагов. При этом, из этой группы из n - 6 человек каждый враг первого человека будет иметь ровно 6 врагов и враги его друзей будут являться его врагами.

Таким образом, группа из n = k + 1 человек также удовлетворяет условию задачи.

Итак, мы доказали, что условие задачи выполняется для произвольного положительного целого числа n.

Так как условие задачи требует указать все возможные варианты и доказать, что других вариантов нет, мы можем отметить, что условие выполняется для всех положительных целых чисел n, кратных 6 (так как каждый человек имеет ровно 6 врагов). Других вариантов не существует, так как в противном случае нарушилось бы условие, что каждый человек имеет ровно 6 врагов.