Тази задача е сравнително лесна, тъй като в нейното решение няма нищо особено освен малко сметки.

Донякъде очевидно е, че максималният процент е 70% - няма как да е повече, тъй като просто само 70% от хората пият чай. В същото време това е постижимо, тъй като може всички хора, които пият чай, да пият и кафе (+още 10%, които пият само кафе).

Минималният процент е почти също толкова лесен за намиране. За него можем да си представим, че в офиса има 10 човека, като първите 7 (тоест тези с индекси {1, 2, 3, 4, 5, 6, 7}) пият чай, а последните 8 (тоест тези с индекси {3, 4, 5, 6, 7, 8, 9, 10}) пият кафе. Така засичащото се множество е {3, 4, 5, 6, 7}, тоест 5 от 10 човека, или 50%.

Тази задача се ползва за пример колко е лесно да се отвлече вниманието (съответно да се обърка логиката) на човек. Тъй като получихме 29 лева, интуицията ни веднага подсказва, че трябваше да са 30. Всъщност, обаче, парите трябваше да са 25 - трябва да се получи цената след намалението, а не тази преди него. Стигнахме до 29 защото двата лева, които е прибрала камериерката, не трябва да се добавят, ами трябва да се извадят от 27-те лева, които са дали тримата човека. Така бихме получили 3 * 9 - 2 = 25 - точно това, което трябваше.

Тази задача е относително лесна. Просто трябва да направим наблюдението, че за да е изпълнено условието след прехода отново във всеки връх да има по една мравка, то трябва мравките да се движат в една и съща посока (или по часовниковата или по обратно на часовниковата стрелка). Това дава два благоприятни случая. Тъй като всяка мравка има избор между два други ъгъла, то всички възможни крайни разположения са 2 * 2 * 2 == 8. Така можем да намерим, че шансът е 2/8 = 1/4 = 25%.

Тази е много лесна и няма почти никакъв шанс да я срещнете на интервюта, но все пак :)

След съвсем малко мислене можете да видите, че цветята са 3 - една роза, една маргаритка и едно лале. Важно е да покажете, че това решение е единствено -- в други задачи може да ви "излъжат" като ви питат за решениеТО, но всъщност да има повече от едно решение, като целта на задачата е да видят дали ще се сетите да намерите всички.

За целта можем да означим броя рози с X, броя маргаритки с Y и броя лалета със Z. Търсим общия брой цветя, тоест X + Y + Z. Правим (доста проста) система уравнения от дадената ни информация и я решаваме:

Друга много популярна задачка за деца. Еднаквите числа ни объркват и инстинктивно веднага тръгваме да отговаряме 100. Нека, обаче, игнорираме инстинкта си и разгледаме с проста математика какво се получава. Ако пет човека могат да построят пет къщи за пет дни, то един човек строи една къща за пет дни. Така сто човека могат да построят сто къщи също за пет дни.

Чистил е прозорците от вътрешната страна.

Били са тризнаци/четиризнаци/т.н.

Трябва да направим наблюдението, че ако запалим единия край на фитила, той ще изгори за един час, но ако запалим и двата му края едновременно, той ще изгори за половин. По-общо, ако на един (запален само от едната страна) фитил му остава да гори T минути и запалим и другия му край, той ще догори за T/2 минути.

Така решението е следното: Палим един фитил от единия край и един от двата края. Когато запаленият и от двете страни изгори, ще са минали точно 30 минути (съответно, на другия ще остават още толкова). В този момент палим и другия му край, като скъсяваме оставащите 30 минути на 15. Когато догори ще са минали 30 + 15 = 45 минути.

"Всеки да се качи на камилата на другия."
По този начин всеки от принцовете има стимул да стигне преди другия до указания град (като доказва, че камилата на другия е по-бърза, сътоветно неговата собствена е по-бавна).
Ако се замислите, реално обръщаме задачата от намирането на най-дълъг път (нерешима) в намиране на най-къс път (решима).

Трябва да направим наблюдението, че числото отдясно изразява колко заградени участъци има в цифрите отляво. Тоест 0 загражда един участък, 1, 2 и 3 не заграждат нито един, 4 загражда един, 5 не загражда нито един, 6 загражда един, 7 не загражда нито един, 8 загражда два и 9 загражда един. Така отговорът за 45678 е 1 + 0 + 1 + 0 + 2 = 4.

С изключение на първия член на редицата, всеки следващ "кодира" предходния - тоест го изразява по някакъв начин. В случая дадено число бива разбито на последователности от еднакви цифри (примерно 111221 бива разбито на 111 22 1) и следващото число кодира тези последователности като първо записва дължината на текущата такава и после записва от коя цифра е изградена тази последователност. В примера 111 22 1 ще запишем "три пъти 1, два пъти 2, един път 1", или 312211. На следващата стъпка разбиваме 312211 на 3 1 22 11 и го кодираме като 13112221. Следователно кодирането на предпоследния член 1113213211 би било (след разбиване на 111 3 2 1 3 2 11) 31131211131221.

Тази задача е от тези, където уж трябва да вкарате логика, но реално по-скоро трябва да сте наблюдателни. Оказва се, че това са числата 91, 90, 89, 88, 87, 86 наобратно - тоест примерен отговор би бил L8 или "87 наобратно".

Отговорът е "зависи от теглото и размерите на куфара". Забележете, че тегло и размери могат да бъдат свързани с една величина - плътност. Ако плътността на куфара е по-високо от тази на водата, то равнището ще се понижи, докато ако е по-ниско ще се повиши.
За да покажете ясно защо се получава така ще ви трябва малко физика (насоки тук), но като цяло можете да предположите правилно отговора и с чиста интуиция.

Пускаме едновременно двата часовника. В момента, в който пясъкът от 4-минутния изтече, го обръщаме. В този момент в горната част на 7-минутния има пясък за 3 минути. След като те изтекат, в горната част на 4-минутния остава 1 минута. Обръщаме 7-минутния докато мине тази 1 минута, след което обръщаме отново него. Преди обръщането в неговата горна част е имало пясък за 6 минути, а в долната - за една. В момента, в който пясъкът доизтече, сме измерили точно 9 минути: 4 + 3 + 1 + 1.

От страниците с по една цифра (1..9) имаме 9, остават ни 1095 - 9 = 1086. От страниците с по две цифри (10..99) имаме 90 * 2 = 180 цифри, остават ни 1086 - 180 = 906. От страниците с по три цифри (100..999) има 900 * 3 = 2700 цифри. Тъй като те са повече, отколкото ни остават, следователно книгата има трицифрен брой страници. Колко точно страници можем лесно да сметнем: 906 / 3 = 302 трицифрени страници → книгата има 401 страници (9 едноцифрени, 90 двуцифрени и 302 трицифрени).

Това е известен проблем с добре-познато решение. Нека в началото всички са на западния бряг и искат да стигнат на източния такъв:

1. Закарва козата на източния бряг;
2. Връща се на западния бряг с празна лодка;
3. Закарва зелето на източния бряг;
4. Връща се на западния бряг с козата;
5. Закарва вълка на източния бряг;
6. Връща се на западния бряг с празна лодка;
7. Закарва козата на източния бряг.

Допълнителна информация тук и тук.

Известна логическа задача (малко стара, ще видите защо). Решението е да включите единия ключ за 5-10 минути, след това да го изключите, да включите втория и да отидете в стаята с крушките. Докосвате двете несветещи крушки - една от тях ще е топла (тъй като е светила до сега) - тя отговаря на първия ключ. Светещата крушка отговаря на втория ключ. Несветещата, студена крушка отговаря на третия. Това решение като че ли не работи много добре с халогенни крушки =/

Въпреки че уравнението изглежда непосилно за смятане на ръка (а всъщност ще е сложно дори и с компютър), решението е учудващо просто. В пред-пред-последната скоба имаме (X - X) = 0, следователно цялото произведение е равно на нула. Трололо =)

Това е по-лесна версия на задачата за дванадесетте монети. Тук решението може да бъде измислено и наум - първо ще претеглим три (произволни) монети срещу три други. В случай, че двете тройки са равни, оставаме само с две монети, като е очевидно как ще намерим фалшивата с оставащото едно измерване. Ако не са, знаем сред коя тройка е фалшивата, тъй като съответната тройка ще е по-лека. Вземеме две от монетите в нея и ги претегляме - ако са равни, значи фалшивата е третата; в противен случай по-леката от двете е фалшивата.

От условието разбираме, че Шерлок Холмс знае сумата и произведението на трите числа, но явно те все още не са определени еднозначно.

Всички тройки числа с произведение 36 са:
{(1, 1, 36), (1, 2, 18), (1, 3, 12), (1, 4, 9), (1, 6, 6), (2, 2, 9), (2, 3, 6), (3, 3, 4)}. От тях всички са с различна сума, освен (1, 6, 6) и (2, 2, 9), които са с еднаква сума 13. Тоест, щом Шерлок не знае еднозначно отговора, то годините на децата са или (1, 6, 6), или (2, 2, 9).

Последният "жокер" от Уотсън е, че най-възрастният му син е със зелени очи - тоест има такова дете, което е по-голямо от останалите. Така вече Шерлок (и ние) разбираме, че възрастта на децата е 2, 2, и 9 годинки.

Един от възможните начини е да се фиксира кой е убиецът и кой е убитият и да се провери дали останалите неща съвпадат. Тъй като има само 5 * 4 варианта, като всеки от тях се отхвърля в рамките на няколко секунди, така ще намерите решението за 1-2 минути.

Друг вариант е да се ползва логика (отново отхвърляне на варианти, но базирано на дадената информация). Примерен начин, по който може да се стигне до заключението е:

От 5) стигаме до извода, че бащата е най-старият член на семейството. От това и 2) знаем, че свидетелят е или дъщерята или съпругата. От това и 1) следва, че помощникът е или бащата или синът. От 4) обаче можем да заключим, че бащата е помогнал за убийството. От 3) и 6) следва, че най-младият човек в семейството не е нито убиецът, нито жертвата, демек не остава да е нищо друго, освен свидетелят. Тъй като казахме, че свидетелят е или майката или дъщерята, то явно дъщерята е свидетелят и е по-малка от брат си, който е убит от майката. Иууу!

Отговорът е нула. Представете си пода като шахматно поле (редуващи се черни и бели квадратчета, като никога няма две съседни бели или черни). При четен брой редове и колони, квадратчетата в срещуположните ъгли са с еднакъв цвят, тоест в дадената стая са махнати две бели или две черни такива. В същото време, независимо дали плочка е хоризонтална или вертикална, тя заема едно бяло и едно черено квадратче. Така, за да бъде облицован подът, то той задължително трябва да има равен брой бели и черни квадратчета. Но тъй като или белите или черните са с две повече, следователно подът не може да бъде покрит по желания от Ели начин.

Тази задача е популярна в състезателната информатика в следствие на няколко известни (относително сложни) задачи.
Едната от тях е с почти същото условие като тази задача, само че забранените полета (колоните) могат да бъдат разположени произволно по дъската. Пита се дали има такова облицоване, и ако да - да се покаже един вариант. Другата е: на шахматна дъска са разположени шахматни коне и се пита колко най-малко коня трябва да бъдат премахнати, така че никои два оставени коня да не се атакуват.
При първата задача трябва да направим същото наблюдение, което направихме и тук - една плочка покрива (винаги) едно черно и едно бяло квадратче. При втората наблюдението е почти същото, макар и малко по-неочевидно - кон на бяло поле атакува единствено черни полета и обратно. Така дъската се представя като двуделен граф (черните полета са от едната страна на графа, докато белите - от другата) и се решава с поток (bipartite matching).

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

Да допуснем, че казаното в 1) е истина. Тогава Ели би казвала истината в сряда или в петък (тъй като 3 е лъжа, демек тя не лъже в някой от тези дни). Ако казва истината в сряда, то ден 1 е бил сряда. Тогава, обаче, казаното в ден 2 също би било истина, тъй като би било четвъртък - демек първият ден не е сряда. Може би е петък? По същата логика, ден две би бил събота, което също би било истина. Така разбираме, че допускането ни, че казаното в ден 1 е истина, е грешно.

Така отхвърлихме една от възможностите и разбираме, че казаното в ден три е истина, а това в ден едно е лъжа. С други думи, третият ден, в който Ели е казала нещо, е понеделник или вторник. Ако е понеделник, то първият ден е бил събота, а вторият неделя. Но в такъв случай, във втория тя отново е казала истината, което разваля нещата. Така остава Ели да казва истината във вторник, което е третият ден, в който е казала нещо.

Нека с главни букви 'A' и 'F' отбелязваме, съответно, извънземното и офицерите, които могат да пилотират кораба, докато с 'a' - извънземните, които не могат. P₁ ще бъде планетата, на която се намират първоначално, а P₂ - тази, на която искат да отидат. Превозът е възможно да се осъществи, като последователността е следната:

1. В началото всички са на планета P₁ | {A, a, a, F, F, F} : {}
2. Aa пътуват от P₁ до P₂ | {a, F, F, F} : {A, a}
3. A пътува от P₂ до P₁ | {A, a, F, F, F} : {a}
4. Aa пътуват от P₁ до P₂ | {F, F, F} : {A, a, a}
5. A пътува от P₂ до P₁ | {A, F, F, F} : {a, a}
6. FF пътуват от P₁ до P₂ | {A, F} : {a, a, F, F}
7. Fa пътуват от P₂ до P₁ | {A, a, F, F} : {a, F}
8. FA пътуват от P₁ до P₂ | {a, F} : {A, a, F, F}
9. Fa пътуват от P₂ до P₁ | {a, a, F, F} : {A, F}
10. FF пътуват от P₁ до P₂ | {a, a} : {A, F, F, F}
11. A пътува от P₂ до P₁ | {A, a, a} : {F, F, F}
12. Aa пътуват от P₁ до P₂ | {a} : {A, a, F, F, F}
13. A пътува от P₂ до P₁ | {A, a} : {a, F, F, F}
14. Aa пътуват от P₁ до P₂ | {} : {A, a, a, F, F, F}

Можем да формализираме проблема по следния начин: Имаме бял правоъгълник, във вътрешността на който е нарисуван черен правоъгълник. Страните на черния правоъгълник може да не са успоредни на тези на белия. Трябва да измислим дали можем и ако да - откъде - да прокараме права линия, която разделя остатъка от белия правоъгълник на две части с равна площ.

Тук трябва да направим следното наблюдение – ако просто имаме правоъгълна торта (от която не е махнато парче) и искаме да я разделим на две равни части, можем да го направим по безброй начини, някои от които са: по хоризонтала през средата, по вертикала през средата, през някой от диагоналите... Общото на всички тези разрези е, че всеки един от тях минава през центъра на правоъгълника (тоест пресечната точка на диагоналите му). Всъщност се оказва, че това е необходимо и достатъчно условие един разрез да разполовява правоъгълник на две равни по площ части.

А как да се справим с изрязаното парче? За да може след разреза двете парчета от тортата да са с равна площ, то трябва да направим такъв разрез, който да разполовява едновременно оригиналната торта и липсващото парче. От горното наблюдение стигаме до извода, че този разрез би минал през центровете както на белия правоъгълник (тортата), така и на черния правоъгълник (липсващото парче). Така гарантираме, че след разреза двете парчета ще са равни.


Smartass решение: Да разрежем тортата напреки!
В зависимост от интервюиращия това може да бъде прието като много интелигентно outside the box решение, или като опит за "измъкване" от истинската задача.

Тъй като всеки човек познава себе си и жена си, стигаме до извода, че дадените девет различни отговора са числата от 0 до 8, включително. За простота, когато има възможност или мъжът или жената от дадена двойка да е казал дадено число, ще считаме, че мъжът е казал по-голямото число, а жената - по-малкото. Ако се замислите, това реално не влияе на отговора на задачата.

Човекът, който е казал 8, не е познавал никой друг, освен себе си и жена си. Тъй като това добавя по едно ръкостискане на всички останали хора освен жена му, стигаме до извода, че тя е човекът, който е казал 0.

Човекът, който е казал 7, не е познавал никой друг, освен себе си, жена си, и жената, която е казала 0. Следователно неговата жена трябва да е казала 1, тъй като всички останали хора са се запознали с поне двама души.

С аналогични разсъждения можем да видим, че в третата двойка мъжът е казал 6, а жената - 2, докато в четвъртата мъжът е казал 5, а жената 3.

Така за жената на Джак остава числото 4 - което е и точно броя хора, с които се е запознала (четиримата "мъже").

Подобно на много други задачи с относително малък брой състояния, и тук можем да намерим решението като разглеждаме случаи.

Да допуснем, че на предходния ход е играл Станчо (тоест сега Ели е на ход). Трите възможни дъски, които би могъл да е имал пред себе си, са:


В първия случай би могъл да сложи горе вдясно и да спечели, но след като не го е направил, значи не е било този случай. Във втория случай би пробвал да спре 'X' като сложи или горе вдясно (за да спре диагонала) или долу вдясно (за да спре хоризонтала). В третия случай има три начина 'X' да спечели, като 'O' е опитал да спре един от тях, което е валиден ход - тоест единственият вариант дъската след петия ход да е била:


Възможните ситуации преди този ход са (като 'X' е на ход):


Тук, обаче, и в трите варианта 'X' има печеливш ход! Щом не е направен, стигаме до извода, че допускането ни, че на шестия ход е играл Станчо, е грешно, от което следва, че е играла Ели (тоест 'X'), демек Станчо сега е на ход и печели.

Можем да проверим това, като видим, че ако 'X' е направил шестия ход, единствената възможна дъска преди това е:


(тъй като никой от другите два хода не "запушва" противника). Тази позиция е достижима по правилата, по които играят двамата.

Тоест отговорът е, че Станчо печели.

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

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

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

Така остава единствено вариантът, в който и тримата са с черни шапки. Всеки вижда по две черни, но не знае дали неговата е бяла или черна. След като никой не реагира, то е логично и тримата да са с черни (иначе биха били в някой от предните два случая).

Тук стъпка по стъпка ще получаваме нова информация (задачата е нещо като решаване на Судоку). За да виждате досегашната информация нагледно, можете да си направите табличка с 5 колони (по една за всяка къща) и 5 реда: за националност, напитка, цигари, цвят, и животно.

• От 9) и 14) следва, че втората къща е синя.
• От предходния извод и от 4) следва, че зелената е трета или четвърта. От 5) и 8) можем да изключим третата, като остава единствено да е четвърта.
• Oт предходния извод и това, че Британецът не е в първата, следва, че червената е по средата.
Така къщите са: жълта, синя, червена, зелена, бяла.
• От това разбираме, че Британецът пие мляко, а Норвежецът пуши Dunhill.
• От 5) знаем, че в четвъртата къща се пие кафе - тоест от 8) и 15) можем да стигнем до извода, че в първата или втората се пие вода, а в другата от тях се пуши Davidoff. Но тъй като в първата се пуши Dunhill, разбираме, че в нея Норвежецът пие вода, а във втората се пуши Davidoff.
Така напитките са: вода, чай, мляко, кафе, бира.
• От това и 3) разбираме, че Датчанинът е във втората къща.
• Тъй като бирата е в петата къща, където се пуши и BlueMaster, от 13) можем да разберем, че Германецът е в четвъртата къща.
Така хората са: Норвежец, Датчанин, Британец, Германец, Швед.
• От 13) следва, че Marlboro са в четвъртата къща, а за Pall Mall остава единствено третата.
Така цигарите са: Dunhill, Davidoff, Pall Mall, Marlboro, BlueMaster.
• От 11) разбираме, че конете са във втората къща.
• От 6) знаем, че птичките са в третата къща.
• От предходното и 10) следва, че котките са в първата къща.
• От 2) знаем, че кучето е в петата къща, като така за рибките остава единствено четвъртата
Така животните са: котки, коне, птички, рибки, куче.

Намерихме, че рибките се гледат от човека в четвъртата къща, тоест Германеца.

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

Оригиналното решение (откъдето взех задачата) е следното:
Трябва да ползваме 4 коли. Първата изоставяме на 1/6 от пустинята - в този момент тя има 2/3 от резервоара си. Оставащото гориво се прехвърля поравно в третата и четвъртата кола, като така те стават пълни до горе. Втората кола остава с 2/3 от резервоара си.
Втората кола изоставяме в на 1/3 от пустинята. В този момент тя е изминала още 1/6 от пустинята от мястото, където изоставихме първата, и има 1/3 от резервоара си. Третата и четвъртата кола в този момент имат 2/3 от резервоарите си. Оставащото гориво от втората кола прехвърляме в четвъртата, допълвайки нейния резервоар до отново пълен.
По средата на пустинята третата кола има 1/3 от резервоара си, а четвъртата 2/3. Прехвърляме горивото в четвъртата, допълвайки резервоара ѝ догоре, и с това гориво можем да изминем остатъка от пустинята.

Освен ако не бъркам нещо фундаментално, моето решение като че ли е по-добро (а, освен всичко, е и по-логично). Отново тръгват 4 коли, като:
На 1/8 от пътя всички коли са с 3/4 от резервоара си. Една кола запълва останалите 3.
След още 1/6 от пътя трите оставащи коли са с 2/3 от резервоара си. Една кола запълва останалите 2.
След още 1/4 от пътя двете оставащи коли са с 1/2 от резервоара си. Едната кола запълва другата.

В този момент е изминато 1/8 + 1/6 + 1/4 = 13/24 от разстоянието (над половината), като една от колите е пълна догоре и може да мине още 1/2 от разстоянието, стигайки до крайната точка с оставащо гориво.

Подобна задача е давана на българско състезание по информатика (сега може да се намери в Timus).

Решението на задачката е малко "лъжа". Може би сте видели, че като имаме три варианта и имаме true/false отговор (1 бит информация) няма как еднозначно да определим коя от трите врати е тази, която ни трябва. Затова трябва да се възползваме от това, че призракът отговаря само с "да" и "не" - тоест ако зададем въпрос, чиито отговор не е "да" или "не" призракът няма да отговори нищо. С други думи трябва да зададем въпрос, който има три варианта: "да", "не", или "друго". Няколко варианта са:

• "Ако кръстя първата врата "да", втората "не", а третата "Гошо", как се казва вратата, през която трябва да мина за да оцелея?" - при този вариант при "да" минаваме през първата врата, при "не" минаваме през втората, а при мълчание минаваме през третата.
• "Ако първата врата не е изходът и мина през втората, ще оцелея ли?" - тук при "да" минаваме през втората, при "не" минаваме през третата, а при мълчание минаваме през първата (ако първата врата е изходът, призракът би трябвало да не отговори нищо, тъй като не е изпълнено условието "ако първата врата не е изходът").

Относително лесно се вижда, че никога жаба няма да прескача жаба от същия вид. Ако това се случи, ще имаме разпределение от типа LL_ или _RR (L е жаба, движеща се наляво, а R е жаба, движеща се надясно). Тъй като има само едно свободно поле, и в двете такива разпределения то може да бъде заето само от жаба от същия вид - тоест повече не бихме могли да местим жабите от другия вид. С други думи "запецваме". (Оставяме задачка за читателя да покаже защо това не може да бъде и последен ход.)

Тъй като има една единствена свободна позиция, и вече казахме, че жабите прескачат единствено жаби от другия вид, казвайки "ще преместим жаба от ляво" или "ще преместим жаба от дясно", ако знаем къде е свободната позиция то и преместената жаба е еднозначно определена (а както и нейния вид движение).

Едно възможно решение е следното: правим едно местене на лява жаба, после две местения на дясни, после три местения на леви, четири на дясни и т.н., докато стигнем N. После изпълняваме N за другия вид, и почваме процедурата наобратно от N до 1. Тоест имаме редицата {1, 2, 3, ..., N-1, N, N, N, N-1, ..., 2, 1}, като за всяко число сменяме кои жаби местим. Така са ни нужни N * (N + 1) / 2 + N + N * (N + 1) / 2 = N * (N + 1) + N = N*N + 2N действия.

Оказва се, че този брой е и минимален. Това лесно може да се покаже, като видим колко разстояние общо трябва да изминат жабите. Всяка от тях трябва да се премести N+1 клетки, тоест цялото разстояние е 2N*(N+1) = 2N*N + 2N. От друга страна всяка жаба трябва да прескочи или бъде прескочена от всички, движещи се в обратната посока, тоест имаме N*N прескачания (местения с дължина 2). Така броят ходове можем да намерим като от общото изминато разстояние извадим броя пъти, в които сме правили ход с дължина 2 вместо 1. Което е 2N*N + 2N - N*N = N*N + 2N.

Един възможен начин е следния (да кажем Ели праща на Крис):

1. Ели слага в сейфа предмета и го заключва с един от нейните катинари. След това го изпраща така на Крис.
2. Крис слага един от нейните катинари на сейфа и го изпраща обратно на Ели. Сега сейфът е заключен с два катинара - един на Ели и един на Крис.
3. Ели маха нейния катинар и го изпраща отново на Крис. Сега сейфът е заключен само с катинар на Крис, който тя може да отключи.

Това работи и за число, изпратено по скайп, стига да имаме някаква обратима функция (например XOR, но има и други). Тук "ключовете" са намислени от момичетата (произволни) числа, а "заключването" е да се XOR-не тайното число с числото на момичето.

Повечето хора, с които обсъждахме задачата, имаха следното предложение:

1. Ели заключва в сейфа си предмета и го изпраща по куриер.
2. Крис праща съобщение, че е получила сейфа.
3. Ели изпраща ключа по куриер.

Втората стъпка е важна, тъй като ако сейфът все още пътува, когато се изпрати ключа, е възможно ключът и пакетът да попаднат на едно и също място, преди да стигнат при Крис.

Трето решение, предложено от Мартин Мавров, беше да се ползва идея от крипотграфията с публични и частни ключове:

1. Момичето, което трябва да получи предмета, изпраща отключен катинар на другото момиче.
2. Момичето, което иска да изпрати предмета, го слага в сейфа и го заключва с получения катинар на другото момиче, след като го изпраща така.
3. Първото момиче получава сейфа, заключен с нейния катинар, и си го отключва.

Ели може да попита (когото и да е от двамата пазачи): "Ако попитам другия пазач коя е желаната от мен врата, той коя ще ми посочи?". След това тя трябва да мине през другата врата. Тъй като чрез този въпрос де факто и двамата биват попитани по нещо, то сме сигурни, че отговорът ще е лъжа.

Два разреза под 90 градуса, и един напречен. Интересното е, че ако и трите разреза са "отгоре" на тортата няма как да я разделим на повече от 7 парчета.

Като хинт в задачи, в които ви питат "Има ли стратегия и ако да - каква е тя" можете да сте почти 100% сигурни, че има такава стратегия.

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

Как ни помага това? Нека (като първи) сложим монета точно в центъра на масата. Където и да сложи монета вторият играч, ние можем да сложим точно от другата страна на масата симетрично спрямо центъра. Така вторият играч отново е в ситуация, където всяка точка от масата е еднаква с точката симетрично спрямо центъра. Наистина, центърът на масата е единствената точка, която няма симетрична спрямо центъра. Следователно ако другият играч е сложил монета някъде, ние винаги можем да сложим симетрично на него. Така рано или късно за него няма да остане място къде да сложи монета и ще загуби.

Забележете, че изобщо не използвахме това, че радиусът на масата е 10 см, или това, че радиусът на монетите е 1 см -- нашето решение е валидно за маса с произволен радиус и монети с произволен радиус (стига той да е еднакъв за всички монети, разбира се). Понякога в такива задачи част от ограниченията са дадени "за заблуда".

Тъй като имаме право на едно единствено теглене, трябва по такъв начин да подберем какво ще измерим, че везната да ни даде достатъчно информация за да определим в кой буркан са фалшивите хапчета. Ако от всеки буркан вземем по едно хапче, и ги сложим на везната, резултатът ще е 10 * 10 - 1, тъй като имаме 9 хапчета по 10 грама и едно по 9 грама. Ако сложим по две хапчета от всеки буркан, тогава ще имаме 20 * 10 - 2. Забелязваме, че ако от буркана с фалшивите хапчета сме взели X на брой, то сумата е с X по-малко, отколкото би била ако всички хапчета бяха окей. Как може да ни помогне това? Ако сложим 1 хапче от първия буркан, 2 хапчета от втория буркан, 3 хапчета от третия и т.н., то очакваната сума (ако всички хапчета бяха по 10 грама) би била 10 * 11 / 2 * 10 (сума на числата от 1 до 10 умножено по 10 грама). Обаче, поради наличието на фашивите хапчета, ще е по-малко. С колко по-малко? Ами с броя на фалшивите! Но тъй като взехме от всеки буркан по толкова хапчета, колкото е индекса на буркана, то показанието на везната ще е точно толкова по-малко от очакваното, колкото е и индекса на буркана с фалшивите хапчета.

Първото, което трябва да направим тук, е да изчислим (приблизително) колко човека са живели и разбърквали карти някога на планетата. Сега са 7 милиарда, докато 2000-та година (ако помните) тъкмо станаха 6 милиарда. Следователно, населението сравнително бързо се увеличава. Наистина, 50-те години е имало около 3 милиарда, като общият брой хора някога живели на планетата е по-малък от 100 милиарда. Както се оказва, тази апроксимация е относително точна.

Да допуснем, че всеки човек, живял някога на планетата е направил по 1 милион разбърквания на тесте карти (доста пресилено). Възможните разбърквания на тесте карти са 52! = 8*10⁶⁷.

Шансът произволно разбъркване да се е срещало е равен на броя на вече направените разбърквания (в историята на човечеството) върху всички възможни разбърквания, тоест 100,000,000,000 * 1,000,000 / 52! == 1*10¹⁷ / 8*10⁶⁷ == 1 / 8*10⁵⁰ ≈ 0. Тоест шансът с първото разбъркване да получите несрещано до сега такова е приблизително 100%.

Това е пример за задача с хитро (но не очевидно) решение. Нека разделим бутилките на такива на четни позиции и такива на нечетни позиции. Момичето може да избере да вземе или всички бутилки на четни позиции, или всички на нечетни.

Наистина, в началото най-лявата бутилка ще бъде на четна (нулева) позиция, докато най-дясната ще бъде на нечетна позиция (тъй като N е четно). Ако тя реши да вземе всички бутилки на четни позиции, тя ще започне с лявата, като за брат ѝ ще остане избор между нечетна бутилка както отляво, така и отдясно. Която и от тях той да избере, от същата страна ще се "открие" нова четна бутилка, която момичето ще вземе и ще го остави отново с две нечетни. Аналогично момичето може да вземе всички нечетни бутилки, започвайки с тази в най-дясната позиция.

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

Ако изключим това, че ако сте момче сигурно бихте процедирали по много странни за останалите начини, стратегията ни е следната:

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

Отговорът е H6.

Защо? Първо трябва да забележим, че относително малко фигури са взети. От страна на белите, само един кон, два офицера, и въпросната царица. Забелязваме, че двата офицера няма как изобщо да излязат отвъд пешките, което означава, че са били взети от черен кон. От черните фигури има две пешки, които са се преместили странично - тоест са взели фигура. Взетите две фигури са оставащите кон и царица. Така свеждаме задачата до две полета - E6 или H6.

От страна на белите има една пешка, която е взела фигура (преместила се е странично). От фигурите на черните липсват само двата офицера. Забелязваме, че пешката на белите е взела фигура на бяло поле - тоест именно офицера, движещ се по бели полета. Това означава, че за да излезе царицата, трябва първо пешката да се премести, но за да се премести трябва този офицер да е излязъл, което пък зависи от това пешката на D7 да се премести. От тук стигаме до извода, че конят на белите е бил взет на Е6, след което офицерът е излязъл и е бил взет от пешката на A2, след което царицата е излязла и е била взета на H6.

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

В другия частен случай, в който сме само ние и мечки, положението обаче хич не е толкова розово. Ако има 1 мечка, ние със сигурност ще умрем. Ако има 2 мечки, то шансът ни да оцелеем е само ако те първо се сбият, което се случва с шанс 2/3 * 1/2 = 1/3.
Ако има три мечки, дори две от тях да се сбият, остава една, която, както казахме, със сигурност ни убива - тоест шансът да оцелеем е 0%. Всъщност лесно можем да забележим, че ако броят мечки е нечетен, ние със сигурност умираме.
Ако е четен, оцеляваме само ако всички мечки се избият преди ние да сме участвали в битка. За 4 мечки шансът първата битка да е от мечки е 4/5 * 3/4, а шансът втората да е от мечки е 2/3 * 1/2. Така шансът ни за оцеляване е (4/5 * 3/4) * (2/3 * 1/2) = 3/5 * 1/3 = 1/5. Относително лесно можем да видим рекурентната зависимост, че шансът за оцеляване при 2K мечки е: F(2K) = (2K / 2K+1) * (2K-1 / 2K) * F(2(K-1)). И всъщност се оказва, че е равен на 1 / (M + 1). Друг начин да си представим това е като счетем, че всички животни и ние се нареждаме на опашка да се бием. Тъй като след всяка битка или мечките изчезват, или ние умираме (и не ни интересува какво се случва нататък), то шансът да оцелеем е само ако сме последни в опашката. Тъй като опашката има M + 1 елемента (ние и М-те мечки), то шансът да сме последни е именно 1/(M+1).

Сега да се върнем на зайчетата. Добавяйки зайчета, те се нареждат някъде в тази опашка. Променят ли отговора те, обаче? Всъщност се оказва, че не! Защо?
Нека разгледаме отново опашката с нас и мечките и видим какво се случва ако добавим зайче някъде в нея. Битките продължават както и преди (умираме, ако се паднем срещу мечка, или две мечки изчезват ако се паднат една срещу друга), докато стигнем до зайчето. Независимо дали зайчето се бие с нас или с мечка, то умира (милото!), като остатъкът от опашката не се променя. Всъщност нещата остават точно същите, като все едно го е нямало. Ако добавим второ, трето и т.н. зайче, нещата остават същите. С други думи - зайчетата нямат значение!

Така шансът да оцелеем е 0, ако M е нечетно, и 1/(M+1), ако M е четно.

Задачката е достатъчно популярна (и сложна) да си има собствена страница в Wikipedia. Няколко от възможните решения са описани там много подробно, така че можете да ги разгледате там.

Интересното тук е, че задачата може да бъде решена дори ако имахме само една крушка и ключ за нея. Двата ключа ги дадохме за заблуда :)

Основната идея е да използваме това, че не се иска да съобщят влизането на всички веднага след като то се случи. Вместо това ще се назначи един от затворниците (примерно вие) за "брояч". Идеята е всеки от затворниците да включи крушката точно по веднъж, а вие да броите колко пъти е била включена. Когато сте преброили 99 включвания, то вече всички са минали и можете да кажете това.

Така стратегията за всеки затворник (освен вас) е ако до сега не е включвал крушката и при влизането му тя е изключена, да я включи. Ако вече я е включвал, или пък тя свети в момента, в който влиза в стаята, той не прави нищо. Вашата пък стратегия е всеки път като влизате в стаята да я изключвате, ако свети, и да броите колко пъти сте я изключили.

Ако не сте измислили решението, пробвайте да помислите още 5 минутки ползвайки следния хинт: на кой ден биха си тръгнали, ако не бяха по 100 ами по 2-ма?


Добре, в случай, че още не сте измислили отговора (или искате да видите дали вашето решение е същото като моето), четете нататък.

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

Нека да видим какво би се случило, ако вместо сто човека със сини очи имаше само един. Очевидно, той би се огледал, не би видял никой друг със сини очи и би стигнал до заключението, че той самият трябва да има такива. Съответно би си тръгнал на първата вечер.

Сега да разгледаме случая с хинта какво би се случило ако са двама души. Всеки от тях би видял другия и би си казал "Може би той е човекът, когото гуруто е видял". След като никой от тях не си тръгне на първата вечер, обаче, тяхната логика би била "Ако той беше единственият синеок, по логиката от предходния параграф би си тръгнал на първата вечер. След като не си е тръгнал тогава, значи има още един човек със сини очи. Аз обаче не виждам друг, следователно единственото логично обяснение е самият аз да съм със сини очи."
Така двамата синеоки човека биха си отишли на втората вечер.

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

След като те си тръгнат, всички останали ще знаят, че самите те нямат сини очи, но няма как да научат какъв точно е техният собствен цвят (може да са кафеви, зелени, червени, пимбяни, ...). Съответно никой друг не си тръгва от острова.

Това е сравнително известна -- и сложна -- задача. Стандартният начин за решаване е да се разглеждат случаи (измерваме тези и тези, ако са равни, правим еди какво си, ако не са вземаме тези и тези и сравняваме тях и т.н.). Тъй като на всяко измерване имаме 3 варианта (лявата страна да е по-лека, равна на, или по-тежка от дясната), дървото на възможностите се разклонява до 27 клона, което е сравнително много. Дори да ако направим известни оптимизации (можем да разглеждаме само по 2 варианта - равна или различна) на някои от стъпките, то пак става сравнително сложно. Това е едно от най-интуитивните и съответно най-често срещани решения, но е много лесно да бъде объркано (в най-честия случай - да се пропусне някой случай).

Вместо това ще разгледаме метод, който задава три предопределени въпроса (тоест правещо измервания, независими от вече направените такива). Тези измервания са така направени, че от резултатите да може еднозначно да се определи коя е фалшивата монета и дали е по-лека или по-тежка във всички случаи.

Нека вместо с {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} означим монетите с буквите {A, C, D, E, F, I, K, L, M, N, O, T}. Измерванията, които трябва да направим са:

1. MADO vs. LIKE
2. METO vs. FIND
3. FAKE vs. COIN

Можете да пробвате да си избирате коя да е фалшивата монета и дали е по-лека или по-тежка и да проверявате, че с горните питания и малко логика можете лесно да познаете коя е.

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

Нека за простота номерираме позициите от 1 до N, като 1 e най-лявата, а N е най-дясната. Една интуитивна стратегия би била първо да докоснем 1, после 2 и т.н. докато стигнем до N. Това би работело, ако в началото истинският предмет се е намирал на нечетна позиция. За съжаление, обаче, ако е бил на четна такава (например на 2-ра), след като сме докоснали холограмата на 1-ва позиция и тя не е била истинският предмет, той може да се премести на 1-ва позиция (която ние тъкмо сме докоснали, но той не е бил там), а след това винаги да отива в позицията, където тъкмо сме били. В този случай ние не бихме го "уловили".

За да решим задачата, трябва да се възползваме от единствената "слабост" на истинския предмет - а именно факта, че на всяка стъпка той отива или на лявата му съседна позиция, или на дясната такава. Тоест със сигурност сменя позицията си, а при това и нейната четност - ако е бил на четна позиция отива на нечетна, и обратно - ако е бил на нечетна отива на четна.

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

Забележете, че при горната стратегия (да докоснем 1, 2, ..., N) през цялото време разстоянието между индекса, който докосваме, и индекса, на който се намира истинският предмет, е с една и съща четност. Ако сме го хванали, то тя е била четна, в противен случай е била нечетна.

Явно за да го хванем, трябва да направим това разстояние четно. Затова след като сме стигнали до N-та позиция и не сме го срещнали по пътя, на следващата стъпка можем отново да докоснем предмета на позиция N. Така истинският предмет ще се премести и ще смени четността си, докато ние няма, с което гарантирано ще получим желаната четност. Сега започваме обратно обхождане (от N-1 към 1), като този път сме сигурни, че ще го хванем.

Накратко, обхождането би било 1, 2, ..., N-1, N, N, N-1, ... 2. Забележете, че не е нужно да стигаме до 1, тъй като в най-лошия случай ще сме го хванали на позиция 2.

Отговорът е 10 затворника (двоичен логаритъм от 1000). На първия ще дадете от всяка от първата половина от гозбите. На втория ще дадете от всяка от първата и третата четвъртина от гозбите. На третия ще дадете от 1-вата, 3-тата, 5-тата и 7-мата осмина от гозбите и т.н.

Визуално можем да представим на кой затворник кои гозби даваме чрез битови маски. Например ако имаше 64 гозби, биха ни били нужни 6 затворника:

1111111111111111111111111111111100000000000000000000000000000000 1111111111111111000000000000000011111111111111110000000000000000 1111111100000000111111110000000011111111000000001111111100000000 1111000011110000111100001111000011110000111100001111000011110000 1100110011001100110011001100110011001100110011001100110011001100 1010101010101010101010101010101010101010101010101010101010101010
Разглеждайки колоните (гозбите), във всяка от тях има уникално двоично число - следователно по умрелите затворници (или по това, че никой от тях не е умрял) може да се определи точно коя от тях е отровна. Това, което направихме, е един вид двоично търсене, само че го извършихме "наведнъж". Паралелно двоично търсене, how cool is that! :)

Като допълнителна информация ще ви кажем, че все пак жестокият млад рус крал бива отровен на сватбата му. И току-що ви спойлнах края на четвърти сезон, нях нях.

Преди да започнем с решението трябва да въведем малко правила. Тъй като всяка карта е различна от останалите можем да направим "наредба" на картите - например спатиите са по-малки от карите, карите са по-малки от купите, и купите са по-малки от пиките. Картите от една и съща боя също могат да бъдат подредени: 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A. Така за всяка двойка карти може да се каже коя е по-малката и коя е по-голямата.

Сега, при даване на 4 карти можем да ги дадем в различен ред, и тъй като четирите карти имат наредба и са различни имаме 4! (4 факториел) възможни подредби. Тоест само чрез подредбата на картите можем да изразим число от 1 до 24, включително.

Тъй като сме дали 4 карти, знаем, че 5-тата не е никоя от тях, тоест 5-тата е една от 52 - 4 = 48. За съжаление така можем да изразим само число между 1 и 24, а не 1 и 48 (тоест не ни достига един бит информация). Тази идея (май) може да се доразвие до работещо решение, но става сложно (тоест дори по-сложно от решението, което ще покажем малко по-долу).

Можем да направим наблюдението, че при 5 карти и 4 бои поне една боя ще се среща поне два пъти (принцип на чекмеджетата). Така боята на първата карта от четворката може да показва боята на петата карта. Тъй като вече една карта със същата боя е била дадена (като първа), остават 12 възможни карти с тази боя. В същото време, от четворката, която даваме на другия магьосник, остават три карти. С тях трябва да определят коя от оставащите 12 е петата.

Според пермутацията на тези три карти можем да определим число от 1 до 6. Отново не ни достига един бит информация (можем да определим число от 1 до 6 а ни трябва от 1 до 12). За разлика от варианта с пермутацията с 4 карти, обаче, тук имаме допълнително информация, която можем да прехвърлим чрез първата карта, тъй като не я ползваме в пермутацията.

Нека считаме, че картите от една боя не са редица ами кръг (тоест след A следва отново 2). Така разликата между две карти от една боя е най-много 6 (избирайки по-късото разстояние). Както казахме, чрез пермутиране на останалите 3 карти в четворката можем да изразим именно число между 1 и 6 - тоест можем да кажем колко е това разстояние! Така ако преномерираме картите от една боя от 2, 3, ..., 10, J, Q, K, A, на 0, 1, 2, ..., 12, то винаги можем да изберем първата карта (нека нейният номер след преномерацията е firstCard) по такъв начин, че петата карта да е от същата боя и да е с номер (firstCard + dist) % 13, където dist е числото, зададено чрез пермутацията от останалите 3 карти в четворката.

Нека например петте избрани карти са KS, 6D, 3S, QH, 4C (поп пика, шестица каро, тройка пика, дама купа, четворка спатия). Виждаме, че имаме две карти от цвета пика, следователно една от тях ще е първа. Разликата (нагоре) от тройка до поп е 10 (4, 5, 6, 7, 8, 9, 10, J, Q, K), докато от поп до тройка е 3 (А, 2, 3). Следователно първата карта, която ще дадем, е поп пика (избираме по-малкото разстояние). С останалите три карти (шестица каро, дама купа, четворка спатия) трябва да образуваме третата пермутация. Тъй като 4C е по-малка от 6D, която от своя страна е по-малка от QH, то третата пермутация би била (6D, 4C, QH). Така, давайки (KS, 6D, 4C, QH) на другия, той би могъл да познае, че петата карта е 3S.

Да разгледаме какво постигат ходовете на Ели. За простота ще наречем двете резултатни купчинки "лява" и "дясна", като в началото в лявата са дадените от Станчо 52 карти.

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

Ако момичето реши да обърне карта от дясната купчинка (стига да има вече такива там) се получава същото (отново, освен ако не сме сигурни, че или всички гледат нагоре, или всички гледат надолу).

Какво, обаче, става, ако обръщаме картата докато я местим от лявата купчинка в дясната (това е разрешено, тъй като е еквивалентно на това да преместим карта от лявата в дясната и да обърнем най-горната от дясната).

• Ако картата е била с лицето надолу в лявата купчинка, то така намаляме броя на картите с лицето надолу в лявата купчина и увеличаваме броя на картите с лицето нагоре в дясната;
• Ако картата е била с лицето нагоре в лявата купчинка, то така намаляме броя на картите с лицето нагоре в лявата купчина и увеличаваме броя на картите с лицето надолу в дясната;

Нека Станчо е казал на Ели, че е обърнал K карти (0 ≤ K ≤ 52). Първоначално в лявата купчинка броят на (обърнати, необърнати) е бил (K, 52-K), докато този в другата купчинка е (0, 0). Преместването с обръщане води до едно от:

• (K - 1, 52 - K) в лявата, (0, 1) в дясната;
• (K, 52 - K - 1) в лявата, (1, 0) в дясната;

Можем да генерализираме при X вече взети обърнати с лицето нагоре карти и Y обърнати с лицето надолу такива:

• (K - X - 1, 52 - K - Y) в лявата, (Y, X + 1) в дясната;
• (K - X, 52 - K - Y - 1) в лявата, (Y + 1, X) в дясната;

Нека сме прехвърлили по този начин точно K карти от лявата купчинка в дясната. Не знаем колко от тях ще са били с лицето нагоре (X) и колко ще са били с лицето надолу (Y), но знаем, че сумата им ще е K. В крайна сметка сме получили (K - X, 52 - K - Y) в лявата и (Y, X) в дясната, като X + Y == K.
Но сега, изразявайки Y == K - X виждаме, че първата компонента (броя обърнати с лицето нагоре карти) е равна и в двете купчинки - точно това, което се опитвахме да направим в задачата!

Очевидното решение е за всеки човек да проверим дали е "перфектен" кандидат. Така просто правим два вложени цикъла - с единия селектираме кандидат, а с другия проверяваме дали той отговаря на изискванията. Така задаваме O(N2) въпроса.

Можем да се справим и далеч по-добре! Трябва да направим две важни наблюдения, за да можем да намалим броя зададени въпроси осезаемо.

Първото наблюдение е относително очевидно - ако има перфектен кандидат, то той ще е само един. Наистина, ако има двама кандидати, то те хем ще трябва задължително да се познават, хем задължително да не се познават.

Второто наблюдение е, че с всеки зададен въпрос можем винаги да елиминираме по един човек от потенциалните кандидати. Например, ако разглеждаме двама потенциални кандидата X и Y, то:

1. Ако X познава Y, то X вече не е потенциален кандидат (тъй като познава някого);
2. Ако X не познава Y, то тогава пък Y със сигурност не е (тъй като не бива познаван от всички).

Така можем с N въпроса да ограничим потенциалните кандидати до точно 1. След това не бива да забравяме, че той ще е потенциален кандидат - но не със сигурност ще отговаря на дадените изисквания. Трябва да зададем още (около) 2*N въпроса, с които да проверим дали той наистина не познава никой друг, а както и че никой друг не познава него. Така общият брой зададени въпроси ще е O(N).

Примерна имплементация:

Нека вместо цветове ползваме числа: така червеното ще е 0, зеленото ще е 1, а синьото ще е 2.
Първият затворник, който трябва да отговори, сумира цветовете на останалите и вижда какво число се получава като остатък при деление на 3. След това казва червено, ако се е получило 0, зелено, ако се е получило 1, или синьо, ако се е получило 2. Шансът да познае собствената си шапка е 1 към 3 (колкото би бил ако просто каже рандом цвят), но така той дава много полезна информация на останалите - толкова полезна, че всички останали могат да се спасят със сигурност.

Всеки от останалите затворници не знае собствения си цвят, но знае сумата на всички без първия по модул 3. Така той може да сумира цветовете на всички без първия и своята, отново да вземе сумата по модул три и да определи еднозначно своя цвят!

Нека даден затворник е сумирал всички шапки без неговата и тази на първия затворник. Нека, например, тази сума е 1.

0. Ако първият е казал "червено", то сумата с неговата е 0, следователно неговата е 2, демек синя.
1. Ако първият е казал "зелено", то сумата с неговата е 1, следователно неговата е 0, демек червена.
2. Ако първият е казал "синьо", то сумата с неговата е 2, следователно неговата е 1, демек зелена.

С аналогична логика всеки затворник може да се определи цвета на собствената си шапка.

Интересното при тази задача е, че отговорът е много далеч от това, което подсказва интуицията. Човек би очаквал, че пират A ще даде голяма част (ако не всичките) монети на останалите от страх да не бъде изхвърлен. Оказва се, обаче, че оптималният отговор е съвсем различен.

Нека разгледаме проблема отзад напред. Какво става ако са останали само D и E? D би предложил 100 монети за себе си и 0 за E, тъй като има решаващия глас при гласуването (ще са 1 на 1, тоест 50%, което е мнозинство). Така разпределението ще бъде {D: 100, E: 0}.

Сега да видим какво става, ако има трима останали пирати. C знае, че при неговото изхвърляне D би предложил на E нула монети. Следователно C може да предложи на E 1 монета и да запази останалите 99 за себе си. E ще е доволен, защото получава 1 монета вместо 0 (както би било ако гласува против C), следователно гласува за него и се получава мнозинство 2 към 1. Така разпределението е {C: 99, D: 0, E: 1}.

С четири пирата нещата не са особено по-различни. B знае какво ще се случи ако го изхвърлят зад борда, следователно базира стратегията си на това. Трябва му още един човек, който да гласува за него, за да има мнозинство - следователно може да "подкупи" D с една монета, на която той ще е доволен. Така разпределението е {B: 99, C: 0, D: 1, E: 0}.

Забележете, че ако B беше решил да даде една монета на E, вместо на D, то независимо дали E ще каже "да" или "не", той (D) ще оцелее и ще вземе 1 монета, следователно би гласувал с "не".

Допускайки, че логиката на A е безпогрешна, той ще знае тези неща и би предложил разпределението {A: 98, B: 0, C: 1, D: 0, E: 1}, с което би спечелил гласовете на C и E.

Най-простата "стратегия" (силна дума) е всеки да отваря кутии по произволен начин. 50 от 100, 1/2 шанс, не е толкова зле, нали? Да, но трябва всички затворници да намерят името си, за да не бъдат екзекутирани. Следователно шансът за успех би бил (1/2)¹⁰⁰ - много, много малко число.

Добре, сега да помислим за нещо по-хитро. Нека за простота направим мапинг от имена (стрингове) към числа - в случая нека вместо името S_K ползваме просто числото K. Казано ни е, че имената са различни, следователно с това няма проблем. Така кутиите съдържат по едно число между 1 и 100, включително, разбъркани в произволен ред. Демек рандом пермутация.

Нека първата кутия, която отваря затворник K, е тази с номер K. Не е неговото име? Следователно вътре стои друго име (демек число). Тогава втората кутия, която отваря, е числото, което е стояло в първата. Пак не е то? Третата кутия е числото, което е стояло във втората, и така нататък. Ако с този процес той намери името си, следователно е намерил цикъл в пермутацията (тъй като следващата кутия би била тази с номер K, която вече е отворена).

Следователно той ще намери името си само ако цикълът, съдържащ K, е с дължина по-малка или равна на 50. Погледнато от друг ъгъл, затворниците ще оцелеят само ако пермутацията не съдържа цикъл с дължина по-голяма от 50.

Да видим какъв е шансът това да се случи. Броят пермутации с дължина 51 е C(51, 100) (избираме 51 числа от 100 налични), умножено по 50! (фиксираме едно от тях за "начално" и разджуркваме останалите), умножено по 49! (броя разджурквания на числата, които не участват в цикъла). Това дава (100! / (51! * 49!)) * 50! * 49! = 100! / 51. Демек доста голямо число. Но каква част от всички пермутации е това? Логично, (100! / 51) / 100! = 1/51. С аналогични изчисления виждаме, че шансът да има пермутация с дължина 52 е 1/52, с 53 е 1/53 и т.н.

Забележете, че тъй като сме взели 51 числа, от останалите 49 няма как да се получи цикъл с дължина над 50 - следователно не е нужно да правим гадни включвания/изключвания за да сметнем вероятността.

Тъй като затворниците ще бъдат екзекутирани ако поне един от циклите е с дължина поне 51, то шансът за неуспех е 1/51 + 1/52 + ... + 1/100. Сметки, сметки, и виждаме, че тази сума е приблизително 0.688 - демек малко под 69%. Така шансът за измъкване на затворниците е цели 31%!