Логически задачи


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

Списък със задачите

    Много лесни

  1. Чай и Кафе
  2. Сметка
  3. Три Мравки
  4. Букет
  5. Лесни

  6. Фитили
  7. Арабско Наследство
  8. Японска Гатанка
  9. Странна Редица
  10. Лодка и Куфар
  11. Пясъчни Часовници
  12. Страници на Книга
  13. Вълк, Коза, и Зеле
  14. Крушки
  15. Сложно Уравнение
  16. Средно сложни

  17. Шерлок Холмс
  18. Убийство
  19. Плочки
  20. Лъжи
  21. Пришълци
  22. Разделяне на Правоъгълници
  23. Ръкостискания
  24. Морски Шах
  25. Майстори на Логиката
  26. Загадката на Айнщайн
  27. Монети
  28. Кола През Пустинята
  29. Три Врати
  30. Жаби
  31. Сигурно Пренасяне
  32. Слепи Пазители
  33. Разделяне на Тортата
  34. Монети Върху Кръгла Маса
  35. Фалшиви Хапчета
  36. Разбъркване на Карти
  37. Винени бутилки
  38. Червената Шапчица
  39. Пъзел с Шах
  40. Трудни

  41. Опасност в Гората
  42. Три Божества
  43. Затворници
  44. Сини Очи
  45. Дванадесет Монети
  46. Омагьосани Предмети
  47. Крал и Отрова
  48. Петата Карта
  49. Карти с Лицето Нагоре
  50. Избор на Министър
  51. Цветни шапки
  52. Пирати
  53. Затворници и Кутии
  54. Особено трудни

  55. Ултимативна Задача

Задачи

Чай и Кафе

70% от хората в един офис пият чай, а 80% пият кафе. Колко е максималният процент хора, пиещи и двете? А минималният?

Сметка

Една задачка, която показва колко лесно е да се обърка човешката логика:
Ели, Крис и Станчо отсядат в хотел и плащат за стаята общо 30 лева, като всеки плаща по 10 лева. Собственикът на хотела решава да им направи отстъпка от 5 лева, които дава на една от прислужничките, казвайки ѝ да им ги даде. По пътя тя се замисля, че не може да раздели 5 лева по равно на тримата, затова решава да прибере 2 лева за себе си и да даде по един лев на всеки от тях. Така всеки е платил по 10 - 1 = 9 лева за стаята, 2 лева са отишли при прислужничката, като общо станаха 3 * 9 + 2 = 29 лева! Къде се загуби последният лев?

Три Мравки

В триъгълен съд има три мравки - по една във всеки от ъглите на триъгълника. Едновременно всяка от тях тръгва към някой от другите ъгли. Какъв е шансът след като стигнат до ъгъла, към който са тръгнали, отново във всеки ъгъл да има точно по една мравка?

Букет

Имате букет с цветя. Всички цветя в букета освен две са рози; всички освен две са маргаритки и всички освен две са лалета. Колко цветя има в букета?

Фитили

Имате безкраен набор от фитили, като знаете, че всеки от тях изгаря изцяло точно за един час, но не задължително с еднаква скорост навсякъде. С други думи е възможно 2/3 от фитила да изгорят за 10 минути, а останалата 1/3 - за 50. Как можете да измерите точно 45 минути?

Арабско Наследство

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

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

Какво им е казал мъдрецът?

Японска Гатанка

За тази задача се твърди, че оригинално е давана като "входен тест" в японска детска градина за изявени деца:
Дадени са ви:
  • 42 -> 1
  • 1337 -> 0
  • 669 -> 3
  • 1882 -> 4
  • 688 -> 5
  • 12345 -> 1
  • 67890 -> 5
  • 123 -> 0
  • 456 -> 2
  • 789 -> 3
Намерете 45678 -> ?

Странна Редица

Дадена ви е редицата 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211. Намерете следващия ѝ член.

Задача с Лодка и Куфар

Ако изхвърлите куфар от лодка по средата на езеро, равнището на водата ще се покачи ли или понижи? Игнорирайте това, че потенциалното покачване или понижаване ще е много малко.

Задача с Пясъчни Часовници

Имате два пясъчни часовника. В единия от тях пясъкът изтича за точно 4 минути, докато в другия - за точно 7 минути. Как ще измерите точно 9 минути, без процесът на измерване да отнема повече от 9 минути?

Страници на Книга

Книга има N страници, номерирани от 1 до N. Общият брой цифри, използвани за номерирането на книгата, е 1095. Колко страници има книгата?

Вълк, Коза и Зеле

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

Как старецът може да закара от другата страна и трите неща, без вълкът да изяде козата и козата да изяде зелето?

Крушки

Намирате се в изолирана стая с три ключа за осветление, контролиращи три крушки в съседна стая, която не можете да видите. Как бихте могли да разберете кой ключ коя крушка контролира, ако веднъж отишли в стаята с крушките не можете да се върнете в стаята с ключовете?

Сложно Уравнение

Дадено ви е, че A = 1, B = 2A, C = 3B, ..., Z = 26Y. Намерете (X - A) * (X - B) * (X - C) * ... * (X - Z) = ?.

Шерлок Холмс

По идея на Васил Люнчев
Шерлок Холмс и Уотсън не се бяха виждали от повече от 40 години! Един ден те се срещнали на улицата и почнали да си говорят за това как животът им е протекъл след последната им среща. Холмс се поинтересувал дали на Уотсън са му се родили деца.

"Цели три!" - отговорил докторът. "Сумата от годините им е равна на номера на онази къща там, докато произведението на годините им е 36.".

Шерлок се замислил, но после казал, че тази информация не му е достатъчна да разбере на колко години са. Уотсън казал: "А ще ти помогне ли това, че най-възрастният ми син има зелени очи?", при което Шерлок вече знаел на колко години са децата.

Можете ли и вие да намерите на колко години е всяко от тях?

Убийство

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

Дадена ви е следната информация:
  1. Свидетелят и този, който е помогнал на убиеца, не са от един и същи пол.
  2. Най-старият човек в семейството и свидетелят не са от един и същи пол.
  3. Най-младият човек в семейството и жертвата не са от един и същи пол.
  4. Този, който е помогнал за убийството, е бил по-възрастен от жертвата.
  5. Бащата е бил по-стар от майката.
  6. Убиецът не е бил най-младият член на семейството.
Кой е бил убиецът?

Плочки

Стаята на Ели има следната форма:

#......... .......... .......... .......... .......... .......... .......... .......... .......... .........#
Тук с '.' сме обозначили празно пространство, а с '#' - колона. Тя иска да облицова пода с плочки с размер 1х2 или 2х1, тоест някое от следните:

# или ## #

За да има естетичен вид, Ели не иска плочките да излизат извън стаята, да се режат, или да се припокриват. Разбира се, те могат да бъдат поставяни само на празното пространство. По колко различни начина може да бъде покрит подът по желания от Ели начин?

Лъжи

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

Пришълци

Знаете ли задачата за пастира, вълка и агнето? Да? Е, това е нейн усложнен вариант:
Три междугалактически офицера трябва да заведат три пришълеца на друга планета за мирни преговори. Те трябва да сторят това, следвайки следните правила:
  1. Разполагат само с малък двуместен кораб.
  2. Всеки от офицерите може да пилотира кораба, но само един от пришълците може да прави това.
  3. Ако по което и да е време на една планета останат повече пришълци от офицери, пришълците ще убият офицерите.
  4. Корабът е единственият начин за транспортиране. Всички офицери и пришълци трябва да оцелеят.
  5. Считаме, че в началото както офицерите, така и пришълците са на една планета, и искат да стигнат до друга.
Възможно ли е да се осъществи превозът и ако да - как?

Разделяне на Правоъгълници

Имате правоъгълна торта, от която е изрязано правоъгълно парче (със страни, които не задължително са успоредни на тези на тортата). Можете ли с един разрез да разделите остатъка от тортата на две равни части? Как?

Ръкостискания

Джак и жена му отишли на парти, на което (освен тях) присъствали още четири женени двойки. При запознанствата всеки човек е стиснал ръка с всеки друг, когото не познава. Когато свършили с това, Джак попитал с колко души е стиснал ръка всеки от останалите хора (включително жена му). За негова изненада получил девет различни отговора. С колко човека е стиснала ръка жената на Джак?

Морски Шах

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

Ели играе с 'X', а Станчо - с 'O'. В момента дъската е:

OO. OX. XX.

Единственото, което не ви е казано, е кой от двамата е започнал първи (и, съответно, кой от двамата е на ход). Можете ли да определите кой е това?

Майстори на логиката

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

Загадката на Айнщайн

Една особено популярна задачка, която все пак изисква мислене. За нея се твърди, че 98% от човечеството не може да реши, но това е по-скоро мит, отколкото доказано по какъвто и да е начин. Моята теория е, че е скрита реклама за цигари. Все пак, самата задачка е интересна:
Постановка:
  1. На една улица има пет къщи, всяка с различен цвят.
  2. Във всяка от къщите живее човек с различна националност.
  3. Тези пет човека пият конкретен тип напитка, пушат конкретна марка цигари, и отглеждат определен тип домашен любимец.
  4. Никои двама от тях не пият еднакъв тип напитка, не пушат еднаква марка цигари и не отглеждат еднакъв домашен любимец.

Информация:
  1. Британецът живее в червената къща.
  2. Домашният любимец на шведа е куче.
  3. Датчанинът пие чай.
  4. Зелената къща е наляво от бялата.
  5. Собственика на зелената къща пие кафе.
  6. Човекът, който пуши Pall Mall гледа птички.
  7. Собственикът на жълтата къща пуши Dunhill.
  8. Човекът, който живее в къщата по средата, пие мляко.
  9. Норвежецът живее в първата къща.
  10. Човекът, който пуши Davidoff, живее до този, който гледа котки.
  11. Човекът, който гледа коне, живее до този, който пуши Dunhill.
  12. Този, който пуши BlueMaster, пие бира.
  13. Германецът пуши Marlboro.
  14. Норвежецът живее до синята къща.
  15. Човекът, който пуши Davidoff, живее до човека, който пие вода.

Въпрос:Кой гледа рибки?

Монети

Кралят на едно кралство е поставил пред вас три монети: златна, сребърна и бронзова. Също така той ви е казал, че ще ви даде една от монетите ако кажете истина и няма да ви даде нищо, ако кажете лъжа. Какво трябва да кажете за да вземете златната монета?

Кола През Пустинята

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

С колко коли и как може да стане това? А ако не трябваше да изоставяте коли?

Три врати

Намирате се в стая с три врати и призрак, който стои в центъра на стаята. Той ви е казал, че една от вратите води навън, а другите две - към сигурна смърт. Имате право на един въпрос, като призракът отговаря само с "да" и "не". Всичко, което казва, е вярно.

Какъв въпрос трябва да зададете, за да разберете през коя врата да минете без да загинете?

Жаби

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

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

Сигурно Пренасяне

Ели и Крис имат идентични преносими сейфове. Всеки от тях има място за поставяне на няколко катинара, но ключовете на Ели не могат да отключат катинарите на Крис и обратно. Сега едното момиче иска да изпрати на другото ценен предмет по куриер. Проблемът е, че ако изпрати предмета извън сейф, или в сейфа, но с някой от ключовете извън него, по пътя куриерът може или да открадне предмета, или да копира ключовете. Как момичетата могат да си предадат пратката по сигурен начин?
Extra credit: Решението ви (поне като идея) ще работи ли, ако момичетата трябваше да си пратят тайно число по скайп, и знаят, че разговорът им се подслушва?

Слепи Пазители

Ели се намира в стая, която има 2 врати: едната води към нейните най-големи кошмари (място, където ноктите ѝ се чупят по-често, косата ѝ не е толкова блестяща, не всички я харесват, постоянно се чуват песни на Justin Bieber и всеки ден има изпити по анализ), а другата - към нейния рай (всъщност не сме много сигурни какво има там). Всяка от вратите се охранява от пазач. Пазачът на едната врата винаги казва истината, а този на другата - винаги казва лъжата. Ели не знае кой пазач винаги лъже и кой винаги казва истината. Момичето има право на един единствен въпрос и след това трябва да избере врата, през която да мине. Какъв би могъл да бъде този въпрос?

Разделяне на тортата

Дадена ви е кръгла торта. Искате да я разделите на осем равни по обем парчета с три прави разреза. Как може да стане това?

Монети Върху Кръгла Маса

Дадена е кръгла маса с радиус 10 сантиметра. Двама играчи се редуват и слагат по една монета с радиус 1 сантиметър на масата така:
  1. Да не застъпва никоя от досега сложените монети;
  2. Да не пада от масата.
Играчът, който не може да сложи монета, губи.

Има ли стратегия за първия играч, при която той винаги печели? Ако да, каква е тя?

Фалшиви Хапчета

Имате 10 буркана, пълни с хапчета. Казано ви е, че във всички буркани хапчетата тежат по 10 грама, с изключение на един, където хапчетата са по 9 грама. Разполагате с електронна везна, която прецизно измерва теглото на сложените върху нея обекти. Можете ли с едно единствено измерване на везната да определите в кой от бурканите хапчетата са по-леки, и ако да - как?

Разбъркване на Карти

Колко е очакваният брой разбърквания на стандартно тесте карти (с 52 карти), които трябва да направите, преди да постигнете подреждане, което никога до сега не се е срещало преди в историята на човечеството?

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

Винени бутилки

Брат и сестра са наследили винарска изба с ценни вина. В нея има четен брой N бутилки вино, наредени в редица. За простота ще ги номерираме от ляво надясно с числата от 0 до N-1, включително. Техните цени са естествени числа, които са ни дадени в масива P[].

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

Вие сте приятел(ка) на сестрата и искате да ѝ помогнете, измисляйки стратегия, с която тя да вземе бутилки на стойност поне колкото ще останат за брат й. Как бихте процедирали?

Червената Шапчица

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

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

Как бихте процедирали вие, ако бяхте на мястото на някое от момичетата?

Пъзел с Шах

От даденото разположение на фигурите на дадената шахматна партия можете ли да определите на кое поле е била взета бялата царица?


Опасност в Гората

По идея на Михал Форишек
В една гора живеят N на брой зайчета, M на брой мечки и вие. Всеки ден две животни се срещат (вие също сте животно за целите на задачата). Ако се срещнат две зайчета, те просто се любуват едно на друго без да правят нищо. Ако зайче срещне вас или мечка, вие (или мечката) го изяждате. Ако вие срещнете мечка, мечката изяжда вас. Ако две мечки се срещнат, те се сбиват и в крайна сметка и двете загиват от раните си.

Пита се каква е вероятността вие да оцелеете, ако двете животни, които се срещат, се избират на произволен принцип?

Три Божества

По идея на Иван Ганев
Три божества A, B и C са също така известни и като True, False и Random. True винаги казва истината, False винаги казва лъжата, a Random с еднаква вероятност казва истината или лъжата. Проблемът е, че не знаем кое божество е True, кое е False, и кое е Random.

За да определите идентичността на A, B и C вие имате право на три да/не въпроса. Всеки от тези въпроси можете да зададете на един от тях. Божествата ви разбират като говорите, но отговарят на техен си език, в който "да" и "не" са "si" и "ja", като не е ясно дали "si" е да или не (но сме сигурни, че "ja" е обратното на "si").

Какви въпроси трябва да зададете, за да определите кой е True, кой е False, и кой е Random?

Пояснения:
Всеки от трите въпроса се задава на точно едно от божествата. На едно и също божество може да бъдат зададени два или дори и трите въпроса. Въпросите се задават един след друг (тоест можете да решите какво и кого да попитате едва след като сте получили отговора на предходните въпроси). В тази задача нямате право да задавате парадокси (тоест въпроси, на които True или False не биха могли да отговорят), както направихме в задачата Три Врати. Можете да си представите, че ако зададете парадокс, главата на божеството избухва (или по-зле, вашата собствена избухва).

Затворници

По идея на Иван Ганев
В един затвор има 100 затворника в различни килии и една затворена стая. В стаята има два ключа и две лампи - единият ключ включва и изключва едната лампа, докато другият - другата. Всеки затворник влиза поне веднъж в тази стая. Те биват вкарвани в стаята един по един в разбъркан ред, като може някой да се изреди два или повече пъти, а друг още да не е влизал. В безкрайността всеки ще влезе безкрай много пъти.
Затворниците ще бъдат освободени ако някой от тях каже, че със сигурност всеки затворник е влизал поне веднъж в стаята. Ако някой го каже, но това все още не е факт (има поне един затворник, който не е влизал), всички те ще бъдат екзекутирани.
В момента затворниците са в двора на затвора и трябва да направят план, с който да се освободят. След като направят плана и се приберат по килиите, те не могат да говорят помежду си повече. Оказва се, че вие сте един от затворниците. Измислете план, с които биха били освободени.

Сини очи

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

Всички хора на острова знаят информацията, описана до тук.

На острова има 100 човека със сини очи, 100 с кафеви очи и един специален (гуру), който е със зелени. Така всеки синеок човек вижда 100 кафявооки, 99 синеоки и един зеленоок. Забележете, че това не му казва нищо за неговите собствени очи - може, например, да има 101 кафявооки, 99 синеоки и един зеленоок; или пък 100 кяфявооки, 99 синеоки, и двама зеленооки; или пък 100 кафявооки, 99 синеоки, един зеленоок, а той самият да има червени очи.

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

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

Дванадесет Монети

Дадени са ви 12 идентични монети, една от която е фалшива. Фалшивата монета е направена от различен материал и съответно е или по-лека или по-тежка. Дадена ви е и обикновена везна, която показва дали предметите, сложени в лявата ѝ купичка, са по-леки, равни, или по-тежки от тези, сложени от дясната. Можете ли с три измервания да определите коя е фалшивата монета и дали тя е по-лека или по-тежка?

Омагьосани Предмети

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

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

Крал и Отрова

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

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

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

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

Петата Карта

Двама магьосници правят следното представление. Човек от публиката (примерно вие) тегли пет произволни карти от стандартно тесте с 52 карти. Изтеглените пет карти биват показани на единия от магьосниците. От тях той избира 4 и ги дава на другия магьосник. За смайване на публиката, другият магьосник безпогрешно познава каква е била петата карта!

Какъв "протокол" (стратегия) на комуникация биха могли да имат двамата човека за да определят еднозначно 5-тата карта по дадените 4? Картите се дават наредени (тоест ordered set), но не може да се подсказва по друг начин (като например някоя карта да е обърната, завъртяна, маркирана, или каквито и да е други версии на "cheat"). Тоест трябва да намерите решение, основано единствено на логика, а не на някакъв вид "измама".

Карти с Лицето Нагоре

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

След това той подава тестето на Ели и ѝ казва колко на брой карти е обърнал. Тя трябва да раздели тестето на две купчинки, като също има право да обръща картите (колкото и които пожелае). Забележете, че тъй като е тъмно тя не знае кои от картите са обърнати нагоре -- само колко на брой са те.

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

Избор на Министър

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

По даден насочен граф на познанствата с N върха (човека), от вас се иска да напишете програма, която печата индексите на всички перфектни кандидати - тоест такива хора, които биват познавани от всички останали и в същото време не познават никого. Познанствата са зададени чрез предиката bool know(int source, int target);, който връща true ако човекът с индекс source познава човека с индекс target, и false в противен случай. Забележете, че е възможно source да познава target, но target да не познава source. Например вие сигурно сте чували за Бил Гейтс, но дали той знае за вас?

С колко най-малко (приблизително) викания на предиката можете да решите задачата?


Цветни шапки

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

Изпитанието е следното: затворниците биват наредени в кръг и върху главата на всеки от тях бива поставена цветна шапка с един от следните три цвята: червен, зелен или син. Всеки от тях вижда цветовете на шапките на останалите затворници, но не и този на своята. На всеки от тях е разрешено да каже по точно една дума: "червено", "синьо" или "зелено". Ако познае цвета на шапката си бива пуснат на свобода. В противен случай бива убит.

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

Ако вие бяхте един от затворниците, каква стратегия бихте предложили? Колко затворници биха могли да се спасят с нея?

Пирати

Петима пирати (удобно именувани A, B, C, D, и E) са открили сандък със 100 златни монети. Сега те се чудят как да поделят съкровището помежду си.

Пиратите имат стриктна подредба по старшинство: A е по-старши от B, който е по-старши от C, който е по-старши от D, който пък е по-старши от E.

В света на пиратите важат следните правила за дистрибутиране на намерено имане. Първо най-старшият пират предлага разпределение на монетите. Пиратите (включително най-старшият) гласуват дали да приемат или не предложеното разпределение. Ако поне половината от гласувалите са "за", то бива прието. В противен случай най-старшият пират бива изхвърлен зад борда, след което се прави ново предложение (от новия най-старши пират) и ново гласуване. Този процес продължава докато някое предложение бъде прието.
Пиратите взимат техните решения на базата на три фактора:
  1. Първо и най-важно - всеки от пиратите иска да оцелее.
  2. Второ, стига да оцелява, той гледа да спечели най-много златни монети.
  3. Трето, ако това дали той ще каже "да" или "не" не влияе на първите два фактора, той гласува с "не".
Пиратите не си вярват (и с право!) и не правят обещания или договорки помежду си, с изключение на това, че стриктно ще спазват гореописаните правила. Какво ще бъде крайното разпределение, ако считаме, че пиратите действат възможно най-рационално?

Затворници и Кутии

Сто затворника (именувани S1, S2, ..., S100 като SiSj) очакват смъртта си следващата сутрин. Тъмничарите знаят, че надеждата (колкото и малка да е тя) успокоява хората, затова са им казали, че ще им дадат следния последен шанс за спасение.

В стая ще бъдат наредени в редица 100 кутии, всяка от които съдържа по името на един от тях (всяко име се среща точно по веднъж), разбъркани на произволен принцип. Един по един затворниците ще бъдат извеждани от общата килия и пускани в стаята, където ще имат възможността да отворят до 50 от тях. Целта на всеки затворник е да открие името си сред (до) 50-те отворени кутии. След излизането на всеки от затворниците от стаята, кутиите биват затворени и оставени точно в състоянието, в което са били преди влизането му.

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

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

Какво решение бихте предложили вие, ако бяхте един от тях? Какъв е шансът ви за измъкване с него?

Ултимативна Задача

Сто затворника са заключени в стая с три пирата, един от който ще бъде обесен на сутринта. Всеки затворник има по 10 бутилки с вино, една от които е отровна. Те се опитват да си поделят 12 монети, една от които е фалшива и тежи по-малко или повече от истинска такава, докато останалите са им дадени от крал и могат да бъдат златни, сребърни или бронзови. В стаята има един превключвател, който затворниците могат или да променят (включват, ако е бил изключен, или изключват, ако е бил включен). Преди да са били заведени в стаята, затворниците са били със затворени очи и са носели или червена или синя шапка. След това те могат да видят шапката на всички останали, но не могат да видят своите очи, които може да бъдат, но може и да не бъдат сини. В същото време шестцифрено просто число на брой маймуни умножават числа, докато цифрите се обърнат в обратен ред. За нещастие, половината маймуни винаги лъжат, другата половина винаги казват истината, а третата половина - понякога лъжат, понякога казват истината с шанс 1/2. Когато затворник познае цвета на шапката и очите си едновремено и бензинът му ще стигне да премине пустинята, прегазвайки синовете на шейха, той успява да избяга, преминавайки реката с лодка, в която със себе си може да вземе или коза, или вълк, или извънземно.

Знаейки, че N-тият затворник е стигнал до заключението, че една от маймуните знае кой от пиратите последен е използвал превключвателя, определете цвета на шапката на затворника, който е изпил отровното вино.
Страницата е посетена 60726 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: