До­ка­жем, что можно обой­тись n не­пра­виль­ны­ми по­па­да­ни­я­ми в оче­редь. До­пу­стим, муд­ре­цы не ме­ня­ют­ся во­об­ще, и тогда в не­пра­виль­ную оче­редь по­па­да­ет k гно­ми­ков. Если муд­ре­цы по­ме­ня­лись бы кол­па­ка­ми в самом на­ча­ле, то в не­пра­виль­ной оче­ре­ди ока­за­лись бы в точ­но­сти все осталь­ные, то есть 2n − k. Ми­ни­мум из 2n − k и k не пре­вос­хо­дит n.

По­ка­жем, что су­ще­ству­ет из­на­чаль­ная рас­ста­нов­ка, при ко­то­рой по­лу­чит­ся не мень­ше n по­па­да­ний в не­пра­виль­ную оче­редь. До­пу­стим, все гно­ми­ки вы­стро­и­лись в оче­редь к бе­ло­му муд­ре­цу, при этом сна­ча­ла все чёрные. Если белый муд­рец не пе­ре­на­пра­вит всех чёрных, он будет вы­нуж­ден до этого по­ме­нять­ся кол­па­ка­ми с кол­ле­гой, после чего ему придётся пе­ре­на­пра­вить всех белых, то есть в любом слу­чае ми­ни­мум n.

Ответ: n.