Олимпиада имени Леонарда Эйлера 2020-2021 учебный год, II тур дистанционного этапа

В автобусе ехали мужчины и женщины, всего 32 человека. Каждый из пассажиров знаком ровно с одним мужчиной и ровно с одной женщиной из остальных. $N$ пассажиров одновременно узнали некоторую новость. Далее каждую минуту новость узнавал от кого-то из своих знакомых ещё один пассажир, причём если это была женщина, то новость в этот момент уже знали оба её знакомых. Через несколько минут оказалось, что новость знают все пассажиры. При каком наименьшем $N$ такое могло случиться? ( С. Берлов, Н. Власова )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Ответ. 8.
Решение. Пусть каждый пассажир возьмётся за руки с обоими своими знакомыми. Очевидно, после этого образуется один или несколько хороводов, в каждом из которых пары мужчин будут чередоваться с парами женщин. Пусть в хороводе $2k$ мужчин. Тогда женщин там тоже $2k,$ а всего в хороводе $4k$ пассажиров. Таким образом, мужчин и женщин среди пассажиров поровну, то есть по 16.
   Назовём тех, кто узнал новость первыми, первоисточниками. Заметим, что та из двух знакомых женщин, которая узнала новость первой, является первоисточником — в противном случае ее знакомая должна была бы узнать новость раньше. Так как пар знакомых женщин у нас $16:2 = 8,$ то и первоисточников минимум 8, то есть $N \ge 8.$
   Покажем, что $N$ может равняться 8. Пусть в каждой паре знакомых женщин первая по часовой стрелке является первоисточником, а среди мужчин первоисточников нет. Тогда можно организовать дело так, что через 8 минут окажется, что каждая женщина-первоисточник поделилась новостью со знакомым мужчиной (после чего ее узнали по одному мужчине из каждой пары знакомых), через следующие 8 минут каждый знающий новость мужчина поделился ею со своим не знающим новости знакомым и, наконец, в течение последних 8 минут новость узнали все не знавшие ее вначале женщины: ведь через 16 минут новость знали все мужчины и по одной женщине из любых двух знакомых женщин.