индукция - Задача на индукцию

Здесь в условии должно подразумеваться, что каждый из преподавателей также в какой-то момент заходил в аудиторию, и в какой-то момент уходил, повторно не возвращаясь. Без этого дополнительного предположения доказываемое утверждение не будет верно. Действительно, если было 2 студента и 2 преподавателя, и последние могли неограниченно приходить и уходить, то сначала мог прийти первый студент, поговорив поочерёдно, но не одновременно с каждым преподавателем. Далее он уходит, и второй студент делает то же самое.

Если дополнительное предположение принять, то утверждение можно доказать индукцией по количеству студентов. Если студент был один, то доказывать нечего: в какой-то момент он присутствовал, то есть в аудитории были все студенты. Теперь шаг индукции: пусть для случая $%k$% студентов утверждение доказано. Рассматривая случая $%k+1$% студентов, временно исключим кого-то одного из рассмотрения. Пусть его зовут Иван. Тогда, без учёта Ивана, по индукционному предположению получается, что в какой-то момент в аудитории были или все преподаватели, или все студенты. При этом первый случай имел бы место и с учётом Ивана. Поэтому будем считать, что в какой-то момент в аудитории были все студенты, кроме Ивана. Это могло иметь место или до прихода Ивана, или после его ухода (в противном случае все они были бы вместе с Иваном).

Рассмотрим первый из случаев. Тогда, если все $%k+1$% студентов не присутствовали вместе, то кто-то из них, пусть это будет Пётр, ушёл до прихода Ивана. При этом Пётр смог поговорить с каждым из преподавателей, и то же верно относительно Ивана. Тогда, если в момент прихода Ивана присутствовали не все преподаватели, то это значит, что кто-то из них успел уже уйти после разговора с Петром. По принятому условию, он уже не возвращается, и тогда Иван с ним не поговорит.

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