* Джуджетата и шапките
Публикувано на 17 януари 2012 в раздел Математика.
Следната задача е предложена от потребител Cliff_Burton:
Задача 1. Злият магьосник хванал сто джуджета, наредил ги в редица, така че всяко да вижда тези пред него. На главите им сложил червени и сини шапки – на всяка глава по една шапка. След това започнал да ги пита от последното към първото с какъв на цвят шапка е. Ако джуджето познае го пуска на свобода, в противен случай го убива. Обаче джуджетата успели предварително да разберат за това нареждане и да измислят стратегия, с която да се спасят максимален брой джуджета. Каква е била стратегията и колко джуджета могат да се спасят със сигурност?
И разбира се след лесната задача, следват тежките подусловия :)
Задача 2. Колко джуджета могат да се спасят ако имаме m цвята шапки?
Задача 3. Колко джуджета могат да се спасят ако к от тях са далтонисти?
П.П. (от Филип) За последните две задачи предлагам джуджетата да са „n“ на брой и естествено трябва да имаме n≥m и n≥k. В задача 3 се предполага, че шапките са отново червени и сини. Накрая предлагам още нещо:
Задача 4. Колко джуджета могат да се спасят ако имаме m цвята шапки и k от джуджетата са далтонисти :)
Нечетните казват цвета на шапката на предното, четните го повтарят и така се спасяват поне floor(n/2), а останалите имат 50% шанс да се спасят и те.
Засега гледам, че няма много отговори на задачите, така че ще дам верен отговор на първата:
Спасяват се със сигурност 99 джуджета, а едно се спасява с шанс 50%. Първото джудже, което вижда всички останали казва червена ако вижда четен брой червени шапки и синя, ако вижда нечетен брой червени шапки. По този начин второто джудже вижда всички шапки пред себе си и прави сметка, ако общият брой на червените е четен, а вижда четен брой червени шапки => неговата е синя; ако общият брой червени е нечетен, а вижда четен брой червени шапки => неговата е червена и т.н…
По този начин първото джудже се спасява с шанс 50%, докато всички останали се спасяват със сигурност (ако броят правилно разбира се)