C, PHP, VB, .NET

Дневникът на Филип Петров


* Джуджетата и шапките

Публикувано на 17 януари 2012 в раздел Математика.

Следната задача е предложена от потребител Cliff_Burton:

Задача 1. Злият магьосник хванал сто джуджета, наредил ги в редица, така че всяко да вижда тези пред него. На главите им сложил червени и сини шапки - на всяка глава по една шапка. След това започнал да ги пита от последното към първото с какъв на цвят шапка е. Ако джуджето познае го пуска на свобода, в противен случай го убива. Обаче джуджетата успели предварително да разберат за това нареждане и да измислят стратегия, с която да се спасят максимален брой джуджета. Каква е била стратегията и колко джуджета могат да се спасят със сигурност?

И разбира се след лесната задача, следват тежките подусловия :)

Задача 2. Колко джуджета могат да се спасят ако имаме m цвята шапки?

Задача 3. Колко джуджета могат да се спасят ако к от тях са далтонисти?

П.П. (от Филип) За последните две задачи предлагам джуджетата да са "n" на брой и естествено трябва да имаме n≥m и n≥k. В задача 3 се предполага, че шапките са отново червени и сини. Накрая предлагам още нещо:

Задача 4. Колко джуджета могат да се спасят ако имаме m цвята шапки и k от джуджетата са далтонисти :)

 



2 коментара


  1. Нечетните казват цвета на шапката на предното, четните го повтарят и така се спасяват поне floor(n/2), а останалите имат 50% шанс да се спасят и те.

  2. Засега гледам, че няма много отговори на задачите, така че ще дам верен отговор на първата:

    Спасяват се със сигурност 99 джуджета, а едно се спасява с шанс 50%. Първото джудже, което вижда всички останали казва червена ако вижда четен брой червени шапки и синя, ако вижда нечетен брой червени шапки. По този начин второто джудже вижда всички шапки пред себе си и прави сметка, ако общият брой на червените е четен, а вижда четен брой червени шапки => неговата е синя; ако общият брой червени е нечетен, а вижда четен брой червени шапки => неговата е червена и т.н...

    По този начин първото джудже се спасява с шанс 50%, докато всички останали се спасяват със сигурност (ако броят правилно разбира се)

Добави коментар

Адресът на електронната поща няма да се публикува


*