Игра происходит на квадрате клетчатой бумаги 9×9. Играют двое, ходят по очереди. Начинающий игру ставит в свободные клетки крестики, его партнер – нолики. Когда все клетки заполнены, подсчитывается количество К строк и столбцов, в которых крестиков больше, чем ноликов,и количество Н строк и столбцов, в которых ноликов больше, чем крестиков. Разность  В = К – Н  считается выигрышем игрока, который начинает. Найдите такое значение B, что
  1) первый игрок может обеспечить себе выигрыш не меньше B, как бы ни играл второй игрок;
  2) второй игрок всегда может добиться того, что первый получит выигрыш не больше B, как бы тот ни играл.

   Решение

Темы:    [ Связность и разложение на связные компоненты ] [ Разбиения на пары и группы; биекции ]

Сложность: 4 Классы: 8,9,10

Прислать комментарий

Условие

Между некоторыми из 2n городов установлено воздушное сообщение, причём каждый город связан (беспосадочными рейсами) не менее чем с n другими.
  а) Докажите, что если отменить любые  n – 1  рейсов, то всё равно из любого города можно добраться в любой другой на самолётах (с пересадками).
  б) Укажите все случаи, когда связность нарушается при отмене n рейсов.

Решение

  а) Предположим, что после отмены некоторых рейсов "связность" нарушилась. Рассмотрим некоторый город A, множество M всех городов, в которые можно проехать из A (возможно, с пересадками) и его дополнение N. Ясно, что между городами из M и N авиалиний нет. При этом в одном из этих множеств не более n городов; пусть их k.
  Первоначально каждый из этих городов был связан авиалиниями не менее чем с n городами, поэтому по крайней мере n + 1 – k  рейсов соединяли его с городами "чужого множества" и, следовательно, были отменены. Значит, всего было отменено не меньше чем  k(n + 1 – k)  рейсов. Но  k(n + 1 – k) > n – 1  при  k = 1, 2, ..., n .  Следовательно, если отменить  n – 1  рейс, то "связность" не нарушается.

  б) Заметим, что  k(n + 1 – k) = n  лишь при  k = 1  и  k = n.  Если  k = 1,  то это значит, что некоторый город был связан рейсами ровно с n городами и все эти рейсы были отменены. Если  k = n,  то это значит, что некоторые n городов A₁, A₂, ..., A_n попарно соединены авиалиниями, оставшиеся n городов B₁, B₂, ..., B_n тоже попарно соединены авиалиниями и есть еще n рейсов, соединяющих города A₁ и B₁, A₂ и B₂, ..., A_n и B_n. На рисунке см. схемы авиалиний для  n = 2  и  n = 3.

Источники и прецеденты использования