Microsoft brainteaser

Следната задачка е една от по-трудните алгоритмични задачи давани на интервю за работа в Майкрософт на позиция програмист.

Играч А изтегля пет произволни карти от тесте с карти (52 карти общо). Показва 4 от картите на играч Б, задачата на играч Б е да познае каква е петата карта. Преди да изтегли 5-те карти двамата играчи се разбират за алгоритъм (начин за подредба на 4-те карти) благодарение на който играч Б винаги да познава петата скрита карта. Какъв е алгоритъма?

Уточнение: в задачата няма "out of the box thinking", маркиране на картите по определен начин, поставяна на картите под ъгъл или друг начин за подсказване.

N

Клан, клан недоклан
дран, дран недодран
дялан, дялан недодялан.

хм тая задча я има в едни доста популярни лекции по дискретна математика :)

hm... imash 4 karti ili 4! nachina z podredbata im t.e. 24 razlichimi systoiania
a kartite koito sa neizwestni sa 48. spored men ne moje da se izmisli
takyw algoritym....

може :) няма да ви казвам кои са лекциите все пак да не развалям кефа на някой, койт иска да се помъчи

В 4 карти има 24 различими състояния наистина, но не забравяй, че играч А може да избира точно кои 4 от 5-те карти да покаже.

osven ako kartite ne sa kvadratni, ima tochno 48 nachina tyi kato kartite mogat da bydat pokazani v portrait ili landscape layout ;)

Expert, ти уцели проблема в десятката, а именно как да се събере информация за 48 състояния когато има само 24 състояния на разположение. Проблема е труден - спор няма. Ето два жокера:
1) принципа на Дерихле
2) модулус 12

Успех,

N

Клан, клан недоклан
дран, дран недодран
дялан, дялан недодялан.