W tas
Przed dwoma laty w Stanach Zjednoczonych ukazała się praca naukowa o tasowaniu kart (Persi Diaconis, Jason Fulman, The mathematics of shuffling cards). Nie jest to pierwsza poważna publikacja na ten temat, ale góruje nad kilkoma poprzednimi objętością – bite 350 stron średniego formatu. Wcześniej mieszaniem blotek i figur zajmował się przede wszystkim szkocki programista Alex Elmsley (1929-2006). Nie dziw, że był on także, podobnie jak matematyk Diaconis, profesjonalnym iluzjonistą, oczywiście głównie karcianym. Nie może dziwić także powiązanie tasowania kart z kombinatoryką, teorią prawdopodobieństwa oraz umieszczoną na nieco wyższej półce teorią grup. Jednak przeglądając wspomnianą książkę trudno nie ulec wrażeniu, że ma się do czynienia z dotyczącym błahej czynności nowym działem matematyki – oczywiście powiązanym z już istniejącymi. A to za sprawą wielu pojęć, które niematematykom nic lub prawie nic nie mówią albo wydają się odstawać od zasadniczego tematu. Na przykład: teoria Liego, funkcja signum, algebry Hopfa, homologia Hochschilda, łańcuchy Markowa, model Placketta-Luce’a, formuła Künnetha, hiperpłaszczyzna, entropia… Uff, czy tasujący karty wiedzą w co się pakują? Dla odreagowania proponuję zadanie na temat, choć też nieproste.
Obsługa (wirtualnej) maszyny do tasowania polega na umieszczeniu w niej porcji x kart, wpisaniu w odpowiednie okienko liczby x i wciskaniu w wybranej kolejności guzików z liczbami od 1 do x. Każdy kolejny przycisk oznacza, na którym miejscu po potasowaniu powinna się znaleźć kolejna karta. Na przykład, wciśnięcie jako pierwszej liczby 7 powoduje, że pierwsza (górna) karta wsadu będzie po potasowaniu siódmą. Naciśnięcie drugiego guzika z piątką skutkuje zmianą pozycji drugiej karty na piątą… itd.
W maszynie umieszczono 13 kierów – od asa (1) do waleta (11), damy (12) i króla (13):
A-2-3-4-5-6-7-8-9-10-W-D-K.
Potasowaną porcję ponownie umieszczono w maszynie i potasowano po raz drugi. Końcowa kolejność kart była następująca:
2-W-5-7-9-8-6-3-A-K-D-10-4.
Jak wyglądała kolejność kart po pierwszym tasowaniu, jeśli oba tasowania wykonano w ten sam sposób, czyli przy każdym guziki były wciskane w takiej samej kolejności?
Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.
Komentarze
Z opisu nie wynika jednoznacznie, który z dwóch możliwych algorytmów należy stosować.
1) każdej z pozycji początkowej przypisujemy wszystkie liczby od 1 do 13 a potem jednocześnie przenosimy je do nowych, zadeklarowanych dla nich pozycji. Wtedy karta pierwsza „A” znajdzie się na pozycji 7 a druga „2” na pozycji 5.
2) po każdym, jednym z trzynastu ruchów, zmienia się pozycja początkowa, wtedy przenoszenie drugiej karty będzie przenoszeniem drugiej karty, którą byłaby „3”, bo usunięcie w pierwszym ruchu „A” spowodowałoby przesunięcie pierwszych siedmiu kart do kolejności 2, 3, 4, 5, 6, 7, A, 8… Wtedy w drugim ruchu przesuwana byłaby nie karta „2” ale karta „3”.
Który wariant algorytmu tu działa?
Żeby nie gmatwać prosty przykład z trzema kartami:
ABC > guziki 312 > BCA > ponownie guziki 312 > CAB.
Czyli zawsze: pierwsza karta na trzecie miejsce, druga na pierwsze, trzecia na drugie.
mp
7-6-10-A-K-W-2-D-4-5-8-3-9, co odpowiada ciągowi liczb 4-7-12-9-10-2-1-11-13-3-6-8-5.
Ten układ liczb tworzy ciąg zamknięty w pętli obejmującej wszystkie pozycje. Można by ułożyć podobne zadanie opierając je na podzieleniu takiego zakresu na np. dwie pętle. 🙂
Zadanie wymagało najwyżej 12 podstawień do metody prób i błędów, co daje szanse trafienia nawet w pierwszym podejściu. Wybór jednej wartości liczbowej dla którejś z pozycji determinuje konsekwencje dla pozostałych, a przy błędnym wyborze prowadzi do sprzeczności. Arkusz kalkulacyjny jako wspomaganie okazał się dobrym narzędziem.
Klasyczny pirrwiastek z permutacyji według mnie
7,6,10,A,K,W,2,D,4,5,8,3,9
Kolejność po pierwszym tasowaniu: 7-6-10-A-K-W-2-D-4-5-8-3-9
7,6,10,A,K,W,2,D,4,5,8,3,9
Skojarzenia mam z tym zadaniem takie, jakby to było dla studentów fizyki, mamy wektor w przestrzeni trzynastowymiarowej i z pomocą macierzy transformujemy go raz, potem jeszcze raz, mamy wynik, i trzeba odgadnąć macierz. Już dawno takich rzeczy nie robiłem, więc działam na piechotę: przekładam asa na inne pole (1 i 9 odpadają, bo na polu 9 leży za drugim przełożeniem), no i jak na przykład as na pole 2, i z 2 na 9, to w pierwszym ruchu 2 musi iść na 9, a jak 2 potem na 1, to w pierwszym ruchu 9 musi iść na 1, a jak 9 potem na 5, to A na 5 w pierwszym ruchu, czyli sprzeczność. No ale jeśli A na 4, to wszystko można ładnie rozparcelować i sprzeczności nie ma, stąd drugi „wektor”: (7, 6, 10, A, K, W, 2, D, 4, 5, 8, 3, 9). Sprawdziłem jeszcze tą samą metodą, że nie ma więcej rozwiązań, to może jest oczywiste, ale dla mnie nie było.
Skojarzenie z transformacją wektora w przestrzeni 13-wymiarowej za pomocą macierzy – trafne i oryginalne; podejrzewam jednak, że dla większości główkołamaczy to czarna magia.
mp
Interesujące i wciąga.
7-6-10-A-K-W-2-D-4-5-8-3-9
4,7,12,9,10,2,1,11,13,3,6,8,5
W poprzednim komentarzu umieściłem kod guzikowy.
Odpowiedź na pytanie – kolejność kart po pierwszym tasowaniu:
7,6,10,A,K,W,2,D,4,5,8,3,9
Po pierwszym tasowaniu karty były ułożone tak: 7-6-10-A-K-W-2-D-4-5-8-3-9.
Karty po pierwszym tasowaniu:
Guziki:
Po pierwszym tasowaniu kolejność była następująca:
7, 6, 10, A, K, W, 2, D, 4, 5, 8, 3, 9