Alice has a dozen cartons, arranged in a 3×4 grid, which for convenience we have labeled A through L:
A B C D E F G H I J K L
She has randomly chosen two of the cartons and hidden an Easter egg inside each of them, leaving the remaining ten cartons empty. She gives the dozen cartons to Bob, who opens them in the order A, B, C, D, E, F, G, H, I, J, K, L until he finds one of the Easter eggs, whereupon he stops. The number of cartons that he opens is his score. Alice then reseals the cartons, keeping the eggs where they are, and presents the cartons to Chris, who opens the cartons in the order A, E, I, B, F, J, C, G, K, D, H, L, again stopping as soon as one of the Easter eggs is found, and scoring the number of opened cartons. Whoever scores lower wins the game; if they score the same then it’s a tie.
For example, suppose Alice hides the Easter eggs in cartons H and K.
Then Bob will stop after reaching the egg in carton H and will score 8, while Chris will stop after reaching the egg in carton K and will score 9. So Bob wins in this case.
Who is more likely to win this game, Bob or Chris? Or are they equally likely to win?
Pokušajte riješiti zadatak, a tek onda čitajte dalje.
Rješenje možete naći na gornjoj poveznici, ili malo ljepše napisano na http://datagenetics.com/blog/march12017/index.html.
Rezultat je vrlo neobičan jer se protivi mojoj, a možda i vašoj intuiciji, koja kaže da poredak ne bi smio igrati nikakvu ulogu. Riječ je o običnim permutacijama; po čemu je ABCDEFGHIJKL bolja (i uopće drugačija) od AEIBFJCGKDHL? U čemu je fora?
Ovaj zadatak vidio sam kada ga je shareao docent Vedran Čačić s PMF-a na (bivšoj) društvenoj mreži Google+, gdje je dao i dobar uvid u odgovor na ovu neobičnost, te postavio dodatni zadatak koji će osobito informatičarima biti zanimljiv:
Of course, it’s completely obvious that there are no absolutely better/worse strategies, as long as you stick to bijections between [1..12] and [A..L] (after all, that’s why S12 is called the symmetry group), so there must be some intransitivity in the “order” of strategies. Can you find a permutation that beats Bob’s ABCDEFGHIJKL, yet is beaten by Charlie’s AEIBFJCGKDHL? 🙂