Математикадан Эйлер олимпиадасы, 2020-2021 оқу жылы, Дистанциялық кезеңнің 2-ші туры

Автобуста 32 адам болған, олардың әрқайсысы немесе ер немесе әйел адам. Жолаушылардың әрқайсысы қалғандарынан дәл бір ер адамды және бір әйел адамды таниды. $N$ жолаушы бір уақытта белгілі бір жаңалықты білді. Содан кейін әр минут сайын басқа бір жолаушы жаңалықты өзінің таныстары арқылы біліп отырды. Ал егер бұл әйел адам болса, онда оның екі танысы да сол сәтте жаңалықты білетін болған. Бірнеше минуттан кейін жа-ңалықты барлық жолаушылар білген. $N$-нің қандай ең кіші мәнінде бұл жағдай болуы мүмкін? ( С. Берлов, Н. Власова )

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

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