Zbiór zadań, (zadania różne)
Zadanie 287
- Jasiu - woła Stasiu - mam dla Ciebie łamigłówkę!
- Super, lubię łamigłówki.
- Popatrz, mam tu siedem kart ponumerowanych od 1 do 7. Układam je na stosie w takiej oto kolejności: 1 6 2 5 3 7 4. A teraz zobacz co się będzie działo. Odwracam całą talię i pierwszą kartę z góry wykładam odkrytą na stół, jest to karta z numerem 1, drugą kartę wkładam na spód talii, trzecią na stół, czwartą na spód i tak dalej. W ten sposób na stole pojawiają się karty ułożone rosnąco.
- Fajne, ale gdzie ta łamigłówka?
- Zrób to samo dla 52 kart, a zobaczysz, że nie jest to takie łatwe.
Rozwiązanie
Poniżej rozwiązania problemu dla liczby kart od $n=1$ do $n=10$.
1
1 2
1 3 2
1 3 2 4
1 5 2 4 3
1 4 2 6 3 5
1 6 2 5 3 7 4
1 5 2 7 3 6 4 8
1 9 2 6 3 8 4 7 5
1 6 2 10 3 7 4 9 5 8
Każdy wiersz pokazuje, w jakiej kolejności ułożyć karty w talonie, aby przy zastosowaniu zasady opisanej w treści zadania podczas wykładania na stole pojawiły się rosnąco. Oznaczmy przez $K(n,k)$ $k$-ty wyraz w $n$-tym wierszu wypisanego trójkąta.
Oto zaobserwowane własności:
Pierwszy wyraz w każdym wierszu równy jest $1$, $K(n,1) = n$ dla każdego $n$.
Druga liczba w każdym wierszu jest o jeden większa niż ostatnia stojąca w wierszu powyżej, czyli $ K(n,2) = K(n-1,N-1) +1$.
Każda liczba stojąca dalej niż na drugiej pozycji w wierszu, jest o $1$ większa od liczby stojącej w wierszu powyżej na pozycji z numerem o $2$ mniejszym. Zatem $K(n,k) = K(n-1,k-2)$, dla $k>2$.
Możemy więc rozwiązać problem rekurencyjnie, ale to wymaga wypisania wszystkich ciągów długości od $1$ do $n$.
Inne, szybsze rozwiązanie, to na $n$-kącie wypukłym zaczynamy w dowolnym wierzchołku od karty nr $1$, obieramy dowolny kierunek i pozostałe karty wykładamy w co drugim nie zajętym jeszcze wierzchołku. Po wyłożeniu wszystkich kart leżą one na brzegu wielokąta w porządku, który nas interesuje.
Rozwiązaniem dla $n=52$ jest ciąg:
1 27 2 40 3 28 4 51 5 29 6 41 7 30 8 47 9 31 10 42 11 32 12 50 13 33 14 43 15 34 16 48 17 35 18 44 19 36 20 52 21 37 22 45 23 38 24 49 25 39 26 46.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>