Задача 188 (Али Баба и 4те разбойника)

Петима разбойници успели да заграбят 1000 златни монети. Според разбойническия им кодекс, този от тях с най-висок ранг предлага подялба. Ако предложението му получи мнозинство при гласуване делят парите, ако ли не - убиват го и е ред на следващия в йерархията да предложи подялба между 4мата останали при същите правила. ... и така докато си разделят заграбеното или докато остане разбойникът с най-нисък ранг да прибере всичко. Всеки може да предложи всякаква подялба, рангът не им гарантира по-голям дял. Считайте, че всички разбойници са:

% безкрайно алчни

% безкрайно логически мислещи

% безкрайно кръвожадни и жестоки

% всеки знае, че и другите са такива



$ Приоритет на всеки разбойник е да заграби колкото може повече монети

$ Приоритет #2 за всеки е да убие другите



Разбойник ще гласува за убийството на друг, дори и ако това не му носи монети, дори ако това би коствало неговия собствен живот, но не и ако би загубил дори една монета.



Каква подялба да предложи пирвият?

Ето как предлагам да започне разсъжденията си Първият:

Приемаме за улеснение, че разбойниците имат номера - 1 е първият с най-старши ранг, а 5 е този с най-младши...

Би трябвало разбойник 4 да се съгласи с всяко едно предложение, направено преди него - логично е, ако останат само 4 и5, 5 да убие 4 и да вземе всичко. Следователно трябва да спечели още <s>два гласа</s> един глас, за да спечели с 3:2 (включвайки собствения си глас).



Така мисля...

0 на втория и четвъртия

1 на третия

2 на петия

останалите за себе си



Ако съм права, ще го обоснова.

Аз пък мисля, че:



1 за втория

0 за третия

2 за четвъртия

0 за петия

останалите за първия



Това е най-многото което биха спечелили втория и четвъртия - останалите така или иначе са против

<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">0 на втория и четвъртия

1 на третия

2 на петия

останалите за себе си



Ако съм права, ще го обоснова.



<div align="right">Originally posted by Bibi*-*25/02/2005*:* 20:43:09</div id="right">

</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">



подкрепям[:)]

и аз дотам стигнах



едит//

ами 997,0,1,2,0 дали не сработва по същия начин??



едит//

не - не бях прочел внимателно, че и собствения му труп се брои[:(!]

Bibi, права си, но нека да обясниш.



kamenf, привет. Дай ако искаш и ти обосновка, понеже аз мисля, че няма да проработи твоята делба.

А пък аз да се таковам в любопитството нямерих отговора в нета...и си утрепах цялото удоволствие от решаването....

Ако останат само двама, 4-тият, дори да предложи всичко на 5-тия, оня ще предпочете да го убие, защото нищо не губи, а е кръвожаден.

Значи останат ли само двама е ясно какво става.

Когато (ако) се стигне до предложението на 3-тия, то ще спечели мнозинство

(3-ти, 4-ти - за, 5-ти - против). Стига да не е предложил 4-тия да получи нула. Значи 3-тия е достатъчно да предложи една паричка на четвъртия и с нея да купи гласът му.

Тогава Втория би трябвало да предложи 0 на 3-тия, 2 на 4-тия и 1 на 5-тия.

4-тия и 5-тия ще го подкрепят, защото иначе получават по-малко.

Първият трябва да подкупи двама.

Най-евтино това става с посоченото 1 на 3-тия и 2 на 5-тия.



@Wise,

<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">

ами 997,0,1,2,0 дали не сработва по същия начин??



<div align="right">Originally posted by Wise - 25/02/2005 : 21:10:01</div id="right">

</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">

Според мен 4-тия би гласувал против такова предложение.

Абсолютно.



гласът на 4ия струва 2 монети при 4ма разбойници и следователно поне 3 при 5. Няма как 997,0,1,2,0 да сработи.

Привет на всички! (забраван съм - извинете ;) )

В условието се споменава мнозинство "за", което ще рече, че при четен брой участници не трябва да има равен брой гласове. Как ли ще му е на втория, който трябва да подкупи двама?!



//EDIT

Одзад напред:

4 и 5 - каквото и да става 4 е мъртъв

3, 4 и 5 - 5 е против, 4 ще е за, ако взима изобщо нещо

2, 3, 4 и 5 - 5 пак е против, 3 няма да е съгласен, занейки, че ще вземе повече ако той е на ход.

Значи 2 няма шанс и би предпочел да не се стига до негово предложение.

Знаейки това, номер 1 изключва от сметките 3 и 5, за да предложи на 2 и 4.

на 2 - 1 монета (иначе 2 няма шанс), на номер 4 - 2 (по-добре от 1 при предложение на 3)

<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">



4 и 5 - каквото и да става 4 е мъртъв

3, 4 и 5 - 5 е против, 4 ще е за, ако взима изобщо нещо



</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">

за тези съм съгласен безспорно, но

<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">2, 3, 4 и 5 - 5 пак е против, 3 няма да е съгласен, занейки, че ще вземе повече ако той е на ход.

Значи 2 няма шанс и би предпочел да не се стига до негово предложение.

</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">



Виж решението на Bibi при 4 разбойници - може да купи гласовете на четвърти и пети:

Тогава Втория би трябвало да предложи 0 на 3-тия, 2 на 4-тия и 1 на 5-тия.

4-тия и 5-тия ще го подкрепят, защото иначе получават по-малко.



Така първи не може да купи гласа на втори, остават другите трима, от които си избира най-евтините двама.

Как би изглеждала за 40 разбойника?

дали ще се запази принципа!

просто ми е любопитно

При 40 разбойника Първият ще трябва да се раздели с 21 от монетите.

Защото иначе Вторият би подкупил 19 души и ще спечели. Остават други 19, които той би пренебрегнал. Първият ще предложи по една на всеки от тях и две на някой от хората, които Вторият иска да прекара само с една паричка.

-----------

Въпреки това считам, че обобщаването на задачата не може да протече по същата логика както до сега.

Ако продължим да увеличаваме броя на разбойниците, при 6 Първият от тях има печеливша тактика (много, 0, 1, 2, 1, 0).

Какво обаче става при 7?

Техният първи трябва да подкупи трима. Ясно е кои ще бъдат двамата. Обаче за трети "печеливш" той може да избира между двама. Така че, ако разбойниците бяха 7, Главатарят им би имал дори две печеливши стратегии. Но, ако са 8, никой няма да знае коя от тях ще бъде избрана и тук нещата се усложняват.



Ако някой има желание, нека даде още идеи.

Ако смея да се обадя...не всяка задача има решение за всяко Н...много задачи се решават само за к [:D]

Ако се промени условието - да не се иска мнозинство, а поне половината гласове да са достатъчни за деление и всеки разбойник предпочита да остане жив, от теория на игрите не би било май трудно да се намери равновесие за произволен брой пирати. Обаче тук гадая.

Bibi, ти няма ли да даваш следващата? [:D]