Версия для печати
Убрать все задачи

---

Прямоугольник 1×3 будем называть триминошкой. Петя и Вася независимо друг от друга разбивают доску 20×21 на триминошки. Затем они сравнивают полученные разбиения, и Петя платит Васе столько рублей, сколько триминошек в этих двух разбиениях совпали (оказались на одинаковых позициях). Какую наибольшую сумму выигрыша может гарантировать себе Вася независимо от действий Пети?

   Решение

Темы:    [ Теория алгоритмов (прочее) ] [ Рекуррентные соотношения (прочее) ] [ Графики и ГМТ на координатной плоскости ] [ Треугольник Паскаля и бином Ньютона ] [ Сочетания и размещения ]

Сложность: 5 Классы: 10,11

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

Условие

Перед Алёшей 100 закрытых коробочек, в каждой – либо красный, либо синий кубик. У Алёши на счету есть рубль. Он подходит к любой закрытой коробочке, объявляет цвет и ставит любую сумму (можно нецелое число копеек, но не больше, чем у него на счету в данный момент). Коробочка открывается, и Алёшин счет увеличивается или уменьшается на поставленную сумму в зависимости от того, угадан или не угадан цвет кубика. Игра продолжается, пока не будут открыты все все коробочки. Какую наибольшую сумму на счету может гарантировать себе Алёша, если ему известно, что
  a) синий кубик только один;
  б) синих кубиков ровно n.
(Алёша может поставить и 0, то есть просто бесплатно открыть коробочку и увидеть цвет кубика.)

Решение 1

  a) Обозначим через B_m наибольший "выигрыш" Алёши для случая m коробочек. Очевидно,  B₁ = 2.
  Если  m > 1,  Алёша делает ставку на цвет первой коробочки. Заметим, что поставить x на красный цвет, это то же самое, что поставить –x на синий. Поэтому можно считать, что Алёша всегда ставит на синий цвет, а  x ∈ [–1, 1].
  Если в первой коробочке окажется синий кубик, капитал Алёши станет равным  1 + x,  а в конце игры он (ставя все свои деньги на заведомо известный цвет) может его довести до  (1 + x)2^m–1.  Если же в первой коробочке красный кубик, то выигрыш Алёши равен  (1 – x)B_m–1.  Итак,
B_m = max {f(x)| x ∈ [–1, 1]},  где  f(x) = min {(1 + x)2^m–1, (1 – x)B_m–1}.  Нарисовав график, видим, что  f(x) достигает максимума в той точке x₀, где
(1 + x₀)2^m–1 = (1 – x₀)B_m–1.  Таким образом,  B_m = (1 + x₀)2^m–1 = (1 – x₀)B_m–1.
  Положив    получим  (1 + x₀)P_m = 2,  (1 – x₀)P_m = 2P_m–1.  Сложив последние равенства, имеем  P_m = 1 + P_m–1.  Отсюда (поскольку  P₁ = 1)
P_m = m.

  б) Обозначим через    наибольший "выигрыш" Алёши для случая m коробочек и n синих шариков. Очевидно,  B_1,0 = B_1,1 = 2,  B_m,0 = 2^m,  то есть  P_1,0 = P_1,1 = P_m,0 = 1.
  Рассуждая аналогично а), приходим сначала к системе  B_m,n = (1 + x₀)B_m–1,n–1 = (1 – x₀)B_m–1,n,  а потом – к соотношению  P_m,n = P_m–1,n–1 + P_m–1,n.
  Это соотношение, очевидно, позволяет однозначно восстановить числа P_m,n по указанным выше начальным условиям. Но и им и соотношению, как известно, удовлетворяют биномиальные коэффициенты    Следовательно,  

Решение 2

  Предположим, что после каждого шага Алёша платит налог в размере половины имеющихся денег (в результате он получит в 2¹⁰⁰ раз меньше денег).
  При наличии перед очередным шагом суммы S и ставке d, у него после этого шага остаётся либо  ½ (S + d),  либо  ½ (S – d),  что в сумме снова дает S. Поэтому можно считать, что он просто раскладывает свои деньги на две кучки – на случай того или иного цвета кубика. Всего в процессе игры он разложит свой рубль на 2¹⁰⁰ кучек. Из них    кучек соответствуют n синим кубикам, и в них должно лежать денег поровну – по     (иначе в одном из вариантов выигрыш меньше), а в остальных – 0.
  Умножив на 2¹⁰⁰, получаем ответ.

Ответ

a)       б)     рублей.

Замечания

1. Баллы: 3 + 5.

2. Задача также предлагалась в Задачнике "Кванта" ("Квант", 2008, №3, зад. М2095).

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