Задача от интервю на Google(UK)

[admin]

Задачата е дадена на интервю при кандидатстване в Google(UK).


5-ма пирати на различна възраст намират съкровище от 100 златни монети.
Те решили да го разделят по следната схема.

Най-старият трябва да разпредели монетите така, че всички да гласуват дали са съгласни или не(вкл. и най-стария гласува).
Трябва поне 50% да гласуват ЗА иначе го убиват и новия най-възрастен го разпределя по същата схема докато остане поне един жив пират.

И петимата са много алчни и умни.

Как ще го разпредели най-старият, за да не умре и да вземе най-голяма част от 100-те златни?

[pal702004]

Скрит текст: покажи

При двама пирати - Б и А (Б е по-старият), при такива условия Б взема всичко. А-нищо
При трима пирати ВБА трябва да се осигури гласа на А - на него 1 монета, на Б - нищо.
При четирима пирати ГБВА на Г му трябва още 1 глас - най-добре е на Б да се даде 1 монета (иначе ще трябва на А да му се дават две). А и В не получават нищо, така че при 5 пирата е най-добре да се даде по монетка на тях.
И така, кой какво получава при 2, 3,4 и 5 пирата:

Код: Избери целия код

А Б В Г Д
0 G
1 0 G 
0 1 0 G
1 0 1 0 G

Значи при четен брой пирати разпределението е
0101....0G
при нечетен
1010...0G

[inveidar]

И защо този, който получава 1 жълтица, трябва да е щастлив? Нали знае, че жълтиците са 100?

[pal702004]

И защо този, който получава 1 жълтица, трябва да е щастлив? Нали знае, че жълтиците са 100?

Защото иначе и една няма да получи. Двама пирати - аз и ти. Да речем, аз съм по-възрастният. Разпределям така: 100 за мен, 0 за теб. Гласуваме, 50% ще бъдат "за".
При трима пирати най-възрастният трябва да подхвърли една жълтица на най-младият и той ще е "за", защото иначе и нея няма да получи - случаят с двама пирати го описахме.
И така по индукция...най-възрастиният взема почти всичко, на останалите (с намаляване на възрастта) 010101...
Той и тези с единичките гласуват "за".

По-скоро, защо като са толкова умни, по-младите са се съгласили на този регламент.

[grav]

А, ако втория по старост предложи на третия повече от една жълтица за да гласува против стария? Така и вторип и третия ще са по-добре от това което ти предлагаш, тогава естествено биха го предпочели.

[Гост]

http://en.wikipedia.org/wiki/Pirate_game

[pal702004]

А, ако втория по старост предложи на третия повече от една жълтица за да гласува против стария? Така и вторип и третия ще са по-добре от това което ти предлагаш, тогава естествено биха го предпочели.

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

[grav]

Именно защото са алчни може да се полакоми. Но тези задачи са по-скоро гатанки отколкото математика.

[inveidar]

Ако пиратите наистина бяха алчни и умни, то те щяха да се сетят за стратегията на най-стария(а и са се сетили щом казваш, че се съгласяват на една монета), който е единствения печеливш, а те всички са здраво прецакани! Тогава дружно биха гласували против него, биха го убили и без повече жертви, нали, биха си разделили по 25 монети. Според мен това е решението, ако получат по 1 или 0 монети. Ако пък старият е достатъчно умен би ги разделил по 20 монети на всеки и той също ще спаси кожата. В противен случай, според мен, това са петима много тъпи пирати! А колкото до Гугъл, нямам си на идея какъв е правилният, според тях, отговор.

[inveidar]

Бих се съгласил с другото решение, ако пишеше, че това са били изключително алчни и не толкова глупави пирати!

[inveidar]

http://en.wikipedia.org/wiki/Pirate_game

Доколкото виждам, условието на оригиналната задача не е преведено изцяло и това променя решението.

[inveidar]

Като се замислих при даденото условие печелившата стратегия е 97,0,0,1,2. Защо? Ако останат последните двама, последният ще вземе 0. Ако останат последните трима, то за да си спечели последния най-старият ще му даде 1 монети, а за него ще остави 99 и по този начин ще си осигури гласа на последния. Ако останат четирима, то последният ще получи отново 1, а най-старият ще вземе 99, като така си осигурява 50 процента. Както забелязвате четвъртият при всички тези варианти не печели нищо! Така при първоначалното положение, вземайки предвид голямата алчност и ум на пиратите, най-старият си осигурява повече от 50 процента при 97,0,1,2.
Чакам някой да коментира това решение.

[pal702004]

Ако останат четирима, то последният ще получи отново 1, а най-старият ще вземе 99, като така си осигурява 50 процента.

Грешиш. При четирима последният няма да получи нищо, а предпоследният ще получи 1 жълтица. Тъй като при трима последният получава жълтица, и тъй като сега пак му предлагат жълтица, като нищо ще гласува "против". Ако иска неговият глас, трябва да му даде поне 2 жълтици, а това вече не е оптимално.

Принципът е ясен: При n пирати се дава по жълтица на тези, които при n-1 пирати не получават нищо.

[Гост]

Даа, задачата за пиратите се оказа трудна и важна! Дано да се разтълкува в скоро време.

[kmitov]

Дадох точки на задачата ама не можах повече, системата не позволява да давам неограничено. Утре пак ще додам на останалите колеги да се не сърдят. Опитах с ВЛЕЗ ИЗЛЕЗ ама пак не стана. Утре.

[inveidar]

Ако останат четирима, то последният ще получи отново 1, а най-старият ще вземе 99, като така си осигурява 50 процента.

Грешиш. При четирима последният няма да получи нищо, а предпоследният ще получи 1 жълтица. Тъй като при трима последният получава жълтица, и тъй като сега пак му предлагат жълтица, като нищо ще гласува "против". Ако иска неговият глас, трябва да му даде поне 2 жълтици, а това вече не е оптимално.

Принципът е ясен: При n пирати се дава по жълтица на тези, които при n-1 пирати не получават нищо.

ОК, за да не гласува против ще му дадат 2 жълтици, т.е 98, 0, 0, 2. Тогава печелившата стратегия е 96,0,0,1,3. Аз така и го бях написал, но го изтрих. А ти стига вече с това 0,1, щото така си го видял в Гугъл. Там условието не е точно такова. Преведи го и ще спорим пак.

[pal702004]

А ти стига вече с това 0,1, щото така си го видял в Гугъл.

Грешиш. За много задачи (особено такива от интервю) не е небходим, гугъл

[inveidar]

Казвам го конкретно за тази задача, а не за решаването на задачи за интервюта по принцип. Що ли не ме разбра?

[inveidar]

Оф, май наистина е 98,0,1,0,1. Аз бъркам. Извинявайте, ако съм засегнал някой.

[admin]

Ако пиратите наистина бяха алчни и умни, то те щяха да се сетят за стратегията на най-стария(а и са се сетили щом казваш, че се съгласяват на една монета), който е единствения печеливш, а те всички са здраво прецакани! Тогава дружно биха гласували против него, биха го убили и без повече жертви, нали, биха си разделили по 25 монети. Според мен това е решението, ако получат по 1 или 0 монети. Ако пък старият е достатъчно умен би ги разделил по 20 монети на всеки и той също ще спаси кожата. В противен случай, според мен, това са петима много тъпи пирати! А колкото до Гугъл, нямам си на идея какъв е правилният, според тях, отговор.

И аз така отговорих.

[Гост]

Според мен за да вземе най -много той трябва непременно да има поне 3 гласа. Понеже е логично че ще гласува за себе си той трябва да предложи на двама най - възрастни пирати след него възможно най - много пари. Прочетох един коментар че трябва да получи 1 монета. Не знам дали съм прав но според мен може да получи възможно най-много 10 вторият пират 60 а третият 30. Така вторият ще си каже че има най -много пари а третият повече от най-стария. И така според мен те ще гласуват за както и тай-стария а най-младите понеже не са получили нищо гласуват против.