Название: интересная игра
Отправлено: revan от Март 31, 2010, 09:13:01
Два мудреца играют в следующую игру. Выписаны числа 0, 1, 2,..., 1024. Первый мудрец зачёркивает 512 чисел (по своему выбору), второй зачёркивает 256 из оставшихся, затем снова первый зачёркивает 128 чисел и т.д. На десятом шаге второй мудрец зачёркивает одно число; остаются два числа. После этого второй мудрец платит первому разницу между этими числами. Как выгоднее играть первому мудрецу? Как второму? Сколько уплатит второй мудрец первому, если оба будут играть наилучшим образом? :rest: :sing: :think:
Название: Re: интересная игра
Отправлено: buka от Март 31, 2010, 21:40:41
Показать скрытый текст Первый мудрец должен стремиться увеличивать минимальное расстояние между числами (первоначально оно равно 1: МинРас = 1.
Кроме того перед ним всегда нечётное кол-во чисел = 2^К + 1 и он должен зачеркнуть 2^(К-1) число. Поэтому он зачёркивает каждое второе.
Т.е. сначала - 1,3,5,...,1023.
Второй мудрец заинтересован не помогать первому в этом и поэтому будет зачёркивать цифры с краю (можно с обоих, но проще - с одного)
Таким образом 2-й мудрец просто гарантированно не увеличит минимум расстояния.
Вот, собственно, и всё:
1. На первом шаге 1-й мудрец обеспечит минимум расстояния в 2. Остаётся 513 чисел
2. 2-й не увеличит его. Остаётся 255 чисел
3. 1-й -> МинРас = 4, остаётся 127 чисел
4. 2-й, 4, 65
5. 1, 8, 33
6. 2, 8, 17
7. 1, 16, 9
8. 2, 16, 5
9. 1, 32, 3
10.2, 32, 2
Второй должен заплатить 1-му 32
|