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

1. Покажем такую ситуацию, когда первое условие выполняется, а второе - нет. Пусть Ai - i-й человек в группе и пусть A[30k + i] = Ai. Допустим, Ai знаком со всеми, кроме Ai+1.

2. Рассмотрим произвольную выборку четырех человек:

Если Ai не знаком со всеми, значит, Ai+1 среди остальных; Если Ai+1 не знаком со всеми, значит, Ai+2 среди остальных; Если Ai+2 не знаком со всеми, значит, Ai+3 среди остальных; Если Ai+3 не знаком со всеми, значит, Ai+4 среди остальных.

Но это невозможно, поскольку среди Ai, Ai+1, Ai+2, Ai+3 и Ai+4 нет совпадающих. Следовательно, первое условие выполняется при любой выборке, однако, среди них нет такого, который был бы знаком с 29 остальными в группе.

Ответ: не всегда.