сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

В та­ин­ствен­ном лесу два муд­ре­ца в чёрном и белом кол­па­ках раз­да­ют гно­ми­кам гри­боч­ки. К ним в две оче­ре­ди вы­стро­и­лись 2n гно­ми­ков, n в чёрных и n в белых кол­па­ках. Если к муд­ре­цу под­хо­дит гно­мик с таким же цве­том кол­па­ка, то гно­мик по­лу­ча­ет гри­бо­чек и уда­ля­ет­ся, а иначе от­прав­ля­ет­ся в конец оче­ре­ди к дру­го­му муд­ре­цу. За какое наи­мень­шее ко­ли­че­ство на­прав­ле­ний в дру­гую оче­редь муд­ре­цы могут раз­дать всем гно­ми­кам по гри­боч­ку, если в про­цес­се раз­да­чи муд­ре­цы могут один раз по­ме­нять­ся кол­па­ка­ми? (Муд­ре­цы сами ре­ша­ют, в какой мо­мент и к кому из них по­дойдёт сле­ду­ю­щий гно­мик из со­от­вет­ству­ю­щей оче­ре­ди. Оче­ре­ди могут быть раз­ной длины. Все гри­боч­ки со­вер­шен­но оди­на­ко­вы.)

Спрятать решение

Ре­ше­ние.

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

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

 

Ответ: n.

Спрятать критерии
Критерии проверки:

Кри­те­рии оце­ни­ва­ния вы­пол­не­ния за­да­нияБаллы
При­ве­де­но пол­ное до­ка­за­тель­ство.20
До­пу­ще­ны мел­кие не­точ­но­сти.18
При­ведён и обос­но­ван при­мер, когда n пе­ре­хо­дов обя­за­тель­ны.14
При­ведён при­мер с не­точ­но­стя­ми в обос­но­ва­нии либо с не­точ­ным от­ве­том. Или до­ка­за­но, что можно за n, рас­смот­ре­ны «наи­худ­шие» слу­чаи для n (вер­ные, но не обос­но­ван­ные).7
До­ка­за­но, что можно обой­тись не более чем n пе­ре­хо­да­ми (на­при­мер, воз­мож­ность по­ме­нять­ся сна­ча­ла или не ме­нять­ся вовсе).4
Ре­ше­ние не со­от­вет­ству­ет ни од­но­му из кри­те­ри­ев, пе­ре­чис­лен­ных выше

ИЛИ

при­ведён толь­ко ответ.

0
Мак­си­маль­ный балл20