LIV OM - I - Zadanie 10

Mamy talię 52 kart. Tasowaniem będziemy nazywać wykonanie następujących czynności: dowolny podział talii na część górną i dolną, a następnie dowolne zmieszanie kart z zachowaniem porządku w obrębie każdej części. Mówiąc formalnie, tasowaniem jest dowolne przemieszanie kart, w którym $ i $-ta karta od wierzchu przechodzi na pozycję $ p_i $, przy czym istnieje takie $ m\in \{ 1, 2, 3, \ldots, 51\} $, że $ p_i < p_{i+1} $ dla $ i<m $ oraz dla $ i > m $.

Rozstrzygnąć, czy rozpoczynając od ustalonego początkowego uporządkowania kart, można uzyskać każde inne uporządkowanie wykonując pięć tasowań.

Rozwiązanie

Udowodnimy, że po pięciu tasowaniach nie można uzyskać porządku odwrotnego do wyjściowego.

Zauważmy, że karty, które podczas pewnego tasowania znalazły się w tej samej części, nie zmieniają wzajemnego porządku po tym tasowaniu.

Spośrod 52 kart podczas pierwszego tasowania w jednej z części znajdzie się co najmniej 26 kart. Spośród tych 26 kart co najmniej 13 znajdzie się w jednej części także podczas drugiego tasowania.

Rozumując podobnie dalej wnioskujemy, że istnieje co najmniej 7 kart, które będą się znajdowały w tej samej części przez pierwsze trzy tasowania. Co najmniej 4 z nich będą w tej samej części także przy czwartym tasowaniu, a pewne dwie po wszystkich pięciu tasowaniach. Zatem zawsze będą istniały dwie karty, które przez pięć tasowań nie zmienią wzajemnego położenia.

Nie można więc uzyskać kart w porządku odwrotnym do wyjściowego, gdyż wtedy każde dwie karty musiałyby zmienić wzajemną kolejność.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź