Задача 5 ОЧ-2018 8-9 класс
В одной школе на окраине столицы всё хорошо, но вот только хромает дисциплина. Представьте: каждое утро сразу 4 ученика "A" класса опаздывают на первый урок: Серёжа, Антон, Миша и Коля. В классе очень много ребят, поэтому мест на опоздавших остаётся немного: всего 4 – две парты в левом ряду (по 2 места каждая – у окна и у прохода) – первая и последняя.
Как и в любом нормальном классе, у ребят различаются предпочтения в вопросе того, где и с кем сидеть, ведь кто-то любит сидеть сзади и болтать с соседом по парте, а кому-то безразлично, где сидеть, лишь бы списать удалось. Предпочтения ребят устроены не так уж и просто: к примеру, для Миши в первую очередь важно сидеть вместе с Антоном (назовём это желанием 1 степени важности), чуть меньше его волнует то, что он любит сидеть сзади (желание 2 степени важности), и еще чуть меньше – то, что он любит сидеть у прохода (желание 3 степени важности), потому что часто выбегает попить. То есть для Миши лучше сидеть с Антоном спереди, чем с Колей или Сережей сзади, а если Мише удаётся сидеть вместе с Антоном, то лучше сзади (даже у окна), чем спереди, и т.д.
Предпочтения всех опоздавших (где и с кем сидеть) описываются следующим образом:
Будем называть итоговую рассадку школьников неэффективной, если опоздавшие могут перераспределить между собой эти 4 места так, чтобы хотя бы одному из них стало лучше, а остальным – не хуже. В противном случае рассадку будем называть эффективной.
(a) Приведите пример неэффективной рассадки и обоснуйте её неэффективность. Приведите пример эффективной рассадки и обоснуйте её эффективность. Сколько всего существует эффективных и неэффективных рассадок?
Взаимодействие между мальчиками происходит последовательно: первым в 9:05 приходит Миша и занимает какое-то место. Затем в 9:20 прибегают Коля и Антон, Мальчики договариваются о том, кто из них куда сядет, причем если они захотят сесть на одно и то же место, то Коле придётся уступить Антону и выбрать другое место, потому что он зачастую у него списывает и не хочет с ним спорить лишний раз. Наконец, в 9:30 прибегает Серёжа – самый сильный мальчик в классе, который без промедления занимает единственное оставшееся свободное место. Однако если Серёже не понравится это место, то он может быстро поменяться своим местом с любым из опоздавших.
(б) Все опоздавшие действуют рационально, зная о порядке взаимодействия и о предпочтениях других. Определите, может ли Миша в итоге оказаться сзади? Как в итоге рассядутся мальчики? Обязательно ли итоговая рассадка будет эффективной?
a) Всего расположений: 4!=24.
Неэффективные рассадки: 8+2+2+8=20.
Чтобы доказать неэффективность рассадки, необходимо указать хотя бы одну такую пересадку, что в результате этой пересадки хотя бы одному из ребят стало лучше, а остальным – по крайней мере не хуже.
1 ) Антон сзади не с Мишей: 2*2*2=8.
Коля (Сережа) спереди, Антон может поменяться с ним.
Антону станет лучше (сядет вперед), и Коле (Сереже) станет лучше (сядет назад), и Мише станет лучше (будет с Антоном), и Сереже (Коле) станет лучше (будет с Колей (Сережей)).
2 ) Сережа спереди у окна, Коля спереди у прохода, Антон сзади с Мишей: 2.
Сережа может поменяться местами с Колей, и Сереже станет лучше (сядет у прохода), а всем остальным станет не хуже.
3 ) Антон спереди с Мишей, Сережа сзади у окна, а Коля - у прохода: 2.
Сережа может поменяться с Колей, Сереже станет лучше (сядет справа), Коле не станет хуже, а Антону с Мишей не стало хуже, так как они остались на своих местах.
4 ) те, где Антон спереди не с Мишей: 2*2*2=8.
Миша сзади, а Коля (Сережа) спереди, значит Миша может поменяться с Колей (Сережей) местами, и Мише станет лучше (сядет с Антоном), и Коле (Сереже) (сядет сзади), и Антону станет лучше (будет с Мишей), и Сереже (Коле) станет лучше (будет с Колей (Сережей)).
Эффективные рассадки: 2+1+1=4.
Чтобы доказать эффективность рассадки, необходимо продемонстрировать, что при любом изменении местоположения ребят хотя бы одному из них станет хуже.
1 ) те, где Антон спереди с Мишей, Сережа сзади у прохода, а Коля сзади у окна: 2.
Докажем вначале, что для обоих случаев нельзя пересаживать Сережу и Колю со своих мест: до пересадки Сережа сидит сзади у прохода с Колей - наилучшее возможное расположение для него, поэтому если в результате пересадок как-то изменятся места Сережи или Коли, то Сереже гарантированно станет хуже.
Осталось рассмотреть возможность поменять местами только Мишу с Антоном спереди: если это сделать, то тому, кто сидел до пересадки у прохода, станет хуже.
Таким образом, данные расположения эффективны.
2 ) Сережа спереди у прохода, Коля спереди у окна, Антон сзади у окна, Миша сзади у прохода: 1.
Если в результате пересадки как-то изменится положение Миши и Антона, то Мише станет хуже, потому что сейчас для него наилучшее возможное расположение.
Осталось рассмотреть возможность поменять спереди местами Колю с Сережей, но тогда станет хуже Сереже.
Данное расположение также эффективно.
3 ) Сережа спереди у прохода, Коля спереди у окна, Антон сзади у прохода, Миша сзади у окна: 1
Если в результате пересадки Миша окажется спереди, то ему станет хуже.
Если в результате пересадки Антон окажется спереди, то Мише станет хуже.
Если поменять местами Мишу с Антоном, то хуже станет Антону (окажется у окна).
Значит, осталось рассмотреть перестановку Сережи с Колей: Сережа окажется не у прохода - ему станет хуже.
Данное расположение также эффективно.
(б) Взаимодействие стоит воспринимать как динамическое: сначала место выбирает Миша, потом - Антон, только потом - Коля (так как при совпадении желаний Антона и Коли место отдается Антону, то взаимодействие между ними двумя можно трактовать как последовательное), и в конце - Сережа выбирает одно место для себя, а школьник, на место которого он садится, попадает на оставшееся свободное (либо Сережа занимает оставшееся свободное место).
Докажем несколько утверждений последовательно, чтобы ограничить число возможных равновесий (это всего лишь один из возможных путей решения).
(1 ) Сережа всегда сядет и окажется сзади у прохода:
Это местоположение для него лучше всего независимо от того, кто будет его соседом, то есть он не будет садиться ни на какое другое место – это заведомо ухудшит его положение.
(2 ) Антон не окажется на заднем ряду:
Для Антона важнее всего оказаться спереди, поэтому если мы покажем, что для любого выбора места Мишей Антон сможет оказаться спереди, то так и произойдёт. Куда бы Миша ни сел, на переднем ряду в любом случае останется хотя бы 1 свободное место. Если Антон займёт его, то сместить его сможет только Сережа, который не будет этого делать в силу утверждения (1).
(3 ) Миша сядет на место спереди у прохода и останется на нём:
Миша понимает, что Антон, действуя рационально, в итоге всегда окажется спереди. Поскольку Миша выбирает первым, покажем, что он может добиться наилучшего возможного для себя при этих условиях расположения (с Антоном, у прохода - сзади Миша вместе с Антоном оказаться не может никак исходя из предыдущего доказанного утверждения) тогда и только тогда, когда он изначально сядет на переднее место у прохода.
1 ) Если он сядет спереди у прохода, то исходя из утверждения (1 ) Антон окажется в итоге спереди у окна. Сережа не будет смещать Мишу, так как хочет сидеть сзади у прохода в первую очередь.
2 ) Если он сядет спереди у окна, то исходя из утверждения (1 ) Антон окажется спереди у прохода. Сережа не будет смещать Мишу, так как хочет сидеть сзади у прохода в первую очередь.
3 ) Если он сядет сзади у окна, то Сережа не будет смещать его, и в итоге Миша окажется сзади, а Антон - спереди.
4 ) Если он сядет сзади у прохода, то Сережа сместит его на оставшееся свободным место после выбора Антона и Коли. Если при этом Антон с Колей сядут спереди, то Миша окажется сзади, а Антон – спереди. Если Антон сядет сзади у окна, то Миша в итоге окажется спереди (его пересадит Сережа, а Антон – сзади). Если Антон сядет спереди, а Коля – сзади, то в итоге Миша попадёт на оставшееся свободным место спереди рядом с Антоном, но так как они оба в таких условиях хотят сидеть у прохода, то Антон сядет спереди у прохода и останется там. В итоге Миша будет спереди у окна с Антоном.
Из (1 ), (2 ) и (3 ) утверждений однозначно следует, что спереди у прохода сядет и окажется в итоге Миша, спереди у окна окажется в итоге Антон, а сзади у прохода сядет и окажется Сережа. Чтобы оказаться спереди у окна после того, как Миша сел спереди у прохода, Антону нужно сесть либо спереди у окна (тогда Коля займет любое место на заднем ряду и окажется сзади у окна), либо сзади у прохода (тогда Коля сядет сзади у окна и останется там, что для него лучше, чем сесть спереди у окна и остаться там, значит, Антон в итоге будет пересажен Сережей на место спереди у окна). Если же Антон сядет сзади у окна, то Сережа не сместит его оттуда, и Антон останется сзади.
Значит, в равновесии возможны следующие варианты взаимодействия:
1 ) Миша сел спереди у прохода, затем Антон сел спереди у окна, Коля сел сзади у прохода или у окна, после чего Сережа занял место сзади у прохода, а Коля оказался сзади у окна.
2 ) Миша сел спереди у прохода, затем Антон сел сзади у прохода, тогда Коля сядет сзади у окна, а Сережа сместит Антона вперед к окну и окажется сзади у прохода.
В обоих вариантах в итоге спереди у окна сидит Антон, спереди у прохода – Миша, сзади у окна – Коля, сзади у прохода – Сережа. Эта итоговая рассадка эффективна.