Регистрация
Регистрация Поиск Пользователи Все разделы прочитаны  
Важные объявления
Старый 09.06.2007, 23:46     TS Старый   #1 (permalink)
Увлечённый
 
Аватар для InFlammable
 
Регистрация: 07.02.2007
Адрес: Киев
Сообщений: 563
При прочтении одной темы в разделе одностоловых турниров, мне вспомнилась одна игра. Чтобы сильно не оффтопить, выложу ее здесь. Если баян, отпишитесь плз, если нет, попробуйте решить

100 пиратов делят сокровище в 100 золотых слитков. Дележ происходит так
1) Каждый пират имеет свой ранг. От самого высшего (капитана) до низшего (юнги). Пусть, к примеру, в числах это от 1 до 100. Одинаковых рангов нет.
2) Самый высший по рангу пират предлагает свой вариант дележа. Если хотя бы половина оставшихся (включая того, кто делит) пиратов поддержит этот дележ, то дележ принимается. Если же больше половины пиратов будет против, то тому, кто делит отрубают голову и следующий по рангу осуществляет попытку дележа опять.
То есть, к примеру, если пиратов двое, то высший по рангу просто забирает себе все, и дележ проходит, т.к. половина(он сам) за.

Существует ли дележ, при котором дележ капитана пройдет? Или же ему отрубят голову, а кто-то следующий сможет поделить? Кто?

Сразу оговорюсь, понятия жадности по отношению к соседу в этой игре нет - каждый пират имея выбор из двух альтернатив:

а)он получает 1 слиток, его сосед - миллион слитков
б)он получает 0, но и сосед получает 0,

выберет а). То есть, каждый максимизирует свой выигрыш.

Если кто решит, ответ плз белым напишите.
__________________
when i bet i either have nuts or balls
InFlammable вне форума      
Старый 12.06.2007, 17:34   #2 (permalink)
Старожил
 
Регистрация: 25.05.2006
Сообщений: 805
Если я правильно понял условия задачи, решение тут.

Обозначим пиратов п1, п2, ..., п100 в соответствии с рангом.
Решаем с конца.
Если пиратов осталось двое (п2 и п1), то п2 забирает все 100 слитков, п1 - 0 слитков.
Если пиратов осталось трое, п3 для того, чтобы делёж прошёл, нужна поддержка одного пирата, для этого ему достаточно дать 1 слиток п1 (слитки ведь нельзя делить на части?). Так как п1 понимает, что отказавшись от этого дележа он не получит ничего, он поддержит его. Остальные 99 слитков п3 забирает себе.
Когда пиратов 4, п4 нужна поддержка одного, его делёж: п2 - 1, п4 - 99, п2 поддерживает.
В общем случае при 2N пиратах п2N даёт по 1 слитку всем пиратам чётного ранга, остальное забирает себе; при 2N+1 пиратах п2N+1 даёт по 1 слитку всем пиратам нечётного ранга, остальное забирает себе.
Для N=1 доказано, индукционный переход доказывается аналогично.
Таким образом, в случае 100 пиратов капитан заберёт себе 51 слиток и даст по 1 слитку пиратам п2, п4, ..., п98, и этот делёж пройдёт.
__________________
Нужно уметь проигрывать. К этой мысли следует постепенно приучать всех своих противников.
SunnyRay вне форума      
Старый 12.06.2007, 21:26     TS Старый   #3 (permalink)
Увлечённый
 
Аватар для InFlammable
 
Регистрация: 07.02.2007
Адрес: Киев
Сообщений: 563
SunnyRay, все верно
__________________
when i bet i either have nuts or balls
InFlammable вне форума      

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
в казино "Planet Hollywood" в Вегасе запланирован открытый шахматный турнир для хайроллеров "Millionaire Chess Open" GolDima Новости казино 0 04.09.2014 12:06
PokerStars.net представляет серию передач "Один день со звездой покера" на телеканале "Дождь" -LOKI- Новости, статьи, репортажи.. 0 19.05.2012 19:55
"Психология покера", "Ваш злейший покерный враг", "Ваш лучший покерный друг" Titanium Теории, стратегии, основы покера 29 22.01.2011 04:40
Ищете "кряк", "лекарство", "таблетку"? ВАМ СЮДА :) Grey Покер софт 4 22.02.2010 00:25


Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Выкл.
Pingbacks are Выкл.
Refbacks are Выкл.

Быстрый переход
Правила форумов CGM Контакты Справка Обратная связь CGM.ru Архив Вверх Главная
 
Использование материалов сайта разрешено только при наличии активной ссылки на источник.
Все права на картинки и тексты принадлежат Информационному агентству CGM и их ПАРТНЕРАМ. Политика конфидециальности
CGM.ru на Youtube CGM.ru на Google+ CGM.ru в Twitter CGM.ru на Facebook CGM.ru в vKontakte CGM.ru в Instagram

В сотрудничестве с Pokeroff.ru
Текущее время: 11:26. Часовой пояс GMT +3.
Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2022, vBulletin Solutions, Inc. Перевод: zCarot