Задача 5 ОЧ-2018 8-9 класс

1) Антон сзади не с Мишей: $2\cdot2\cdot2=8$.
Коля (Сережа) спереди, Антон может поменяться с ним.
Антону станет лучше (сядет вперед), и Коле (Сереже) станет лучше (сядет назад), и Мише станет лучше (будет с Антоном), и Сереже (Коле) станет лучше (будет с Колей (Сережей)).

2) Сережа спереди у окна, Коля спереди у прохода, Антон сзади с Мишей: 2.
Сережа может поменяться местами с Колей, и Сереже станет лучше (сядет у прохода), а всем остальным станет не хуже.

3) Антон спереди с Мишей, Сережа сзади у окна, а Коля - у прохода: 2.
Сережа может поменяться с Колей, Сереже станет лучше (сядет справа), Коле не станет хуже, а Антону с Мишей не стало хуже, так как они остались на своих местах.

4) те, где Антон спереди не с Мишей: $2\cdot2\cdot2=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) Миша сел спереди у прохода, затем Антон сел сзади у прохода, тогда Коля сядет сзади у окна, а Сережа сместит Антона вперед к окну и окажется сзади у прохода.
В обоих вариантах в итоге спереди у окна сидит Антон, спереди у прохода – Миша, сзади у окна – Коля, сзади у прохода – Сережа. Эта итоговая рассадка эффективна.