Tasowanie kart

[marchewa4]

Jest to zadanie z biezacej olimpiady matematycznej, ale chyba pasuje do tego
forum. Zobaczymy.

Rozwazmy talie 52 kart. Pojedyncze tasowanie polega na podzieleniu talii na
dwie czesci (oczywiscie niekoniecznie rowne) i nastepnie takie zmieszanie
kart z obu tych czesci, zeby porzadek w ramach kazdej czesci zostal zachowany
tzn. karty z jednej czesci moga lezec pomiedzy kartami drugiej czesci, ale
jesli karty x i y lezaly w jednej czesci i x lezala przed y, to po polaczeniu
x musi lezec przed y. (Jesli ktos widzial jak tasuja karty w kasynie, to to
jest wlasnie to.)
I teraz zadanie. Czy mozna z jednego ukladu kart przejsc do innego, dowolnego
ukladu kart wykonujac 5 opisanych powyzej tasowan? Odpowiedz uzasadnij,
najlepiej tak, zeby i inni zrozumieli ;-).

Pozdrawiam

M.

[cardemon]

Nie można. Potrzeba tych tasowań przynajmniej 6, a nakrotszy dowód to:
2^5 < 52 (dwa do potegi piatej jest mniejsze niz 52). :)

pzdr. CdM

[kopperek]

cardemon napisał:

> Nie można. Potrzeba tych tasowań przynajmniej 6, a
nakrotszy dowód to:
> 2^5 < 52 (dwa do potegi piatej jest mniejsze niz 52).
:)
>
> pzdr. CdM

Cardemon - z przykroscia przyznaje, ze nie rozumiem.
Intrygujace zadanie.

A tak w ogole to czesc .

[cardemon]

Tez witam serdecznie. Przyznaję, ze mój dowód nie był żadnym dowodem, raczej
bardzo skrótowym przedstawieniem sedna rzeczy i na dodatek od końca. Moze wiec
lepiej zacznę od poczatku.
Mamy talie 52 kart ułozonych w takiej kolejnosci, ze karta nr 1 jest na
spodzie, a karta nr 52 na wierzchu. Niech ukladem do, ktorego dazymy bedzie
dokladnie odwrotne ulozenia wszystkich kart, czyli ta z wierzchu ma sie znalezc
po tasowaniach na spodzie, ta ze spodu na wierzchu itd. Dlaczego wybieram taki
uklad? Bo jest on tym, ktory bedzie wymagal najwiekszej ilosci
operacji "odwróceń" kolejnosci kart, czyli najtrudniejszym do uzyskania.
No dobrze, zaczynamy tasowanie, dzielimy wiec talie na dwie rowne kupki (po 26
kart) i tasujemy, tak ze kolejno przeplatamy karte raz z jednej kupki raz z
drugiej, a zaczynamy od kupki wierzchniej. Po tym tasowaniu na spodzie bedzie
karta nr 27, na niej karta nr 1, potem nr 26, nr 2...., a na wierzchu karta nr
26. Z ciagu 52 kart do odrocenia mamy teraz w talii dwa ciagi 26 kartowe
wymagajace odwrocenia. Ciagiem nazywam tutaj pewien zbior kolejno nastepujacych
po sobie kart ze wzgledu na przydzielony im poczatkowo numer. Oczywiscie karty
w takim ciagu po pierwszym tasowaniu nie leza juz jedna na drugiej. Powtarzamy
operacje tasowania, teraz otrzymamy cztery ciagi po 13 kart w kazdym. Po
trzecim tasowaniu beda to juz ciagi 7 i 6-kartowe. Wezmy pod rozwazania ciag 7-
kartowy (jako dluzszy), po kolejnym przetasowaniu rozbijemy talie na ciagi 4 i
3-kartowe. Znow wezmy pod uwage dluzszy czyli 4 kartowy. Po kolejnym, czyli juz
piatym tasowaniu nadal zostana w talii ciagi 2-kartowe wymagajace odwrocenia,
czyli starsza nadal bedzie na kupce lezec wyzej, choc miala lezec nizej.
Dopiero szoste tasowanie umozliwi pelne odwrocenie kolejnosci kart w talii i
osiagniecie zaplanowanego koncowego ukladu.
Mam nadzieje, choc nie jestem calkiem przekonany, ze wysłowiłem się w sposób
zrozumiały. :)

Mozna równiez podejść do tej zagadki z drugiej strony. Po jednym tasowaniu kart
mozemy odwrocic kolejnosc maksymalnie dwoch kart, dwa tasowania dla maksymalnie
4 kart, trzy tasowania dla 8 kart (np. 8,7,6,5,4,3,2,1 -> 4,8,3,7,2,6,1,5 ->
2,4,6,8,1,3,5,7 -> 1,2,3,4,5,6,7,8)..., pięć tasowań dla max. 32 kart. Jak wiec
widac pieć to za malo jak na pelna talie 52 kart. :)

pzdr. CdM

[marchewa4]

Bardzo podobnie i ja rozumowalem, zeby dowiesc, ze 5 tasowan nie wystarczy.
Nie zakladalem co prawda zawsze podzialu talonu na polowe, ale to nie ma dla
rozwiazania wiekszego znaczenia.

M.

[mesquaki]

Czy to znaczy, że sześć wystarczy?
Czyli, że istnieje takie sześć tasowań, które odwrócą porządek 52 kart?
m

[cardemon]

mesquaki napisała:

> Czy to znaczy, że sześć wystarczy?
> Czyli, że istnieje takie sześć tasowań, które odwrócą porządek 52 kart?

Witaj Mes. Tak wyglada na to, ze maksymalnie szesc tasowan pozwoli na uzyskanie
dowolnego innego ukladu kart.

pzdr. CdM

[marchewa4]

cardemon napisał:

> mesquaki napisała:
>
> > Czy to znaczy, że sześć wystarczy?
> > Czyli, że istnieje takie sześć tasowań, które odwrócą porządek 52 kart?
>
> Witaj Mes. Tak wyglada na to, ze maksymalnie szesc tasowan pozwoli na
> uzyskanie dowolnego innego ukladu kart.

A mi wcale na to nie wyglada :-( Sprobowalem potasowac te 6 razy z pozycji
wyjsciowej "uporzadkowane rosnaco". Okazalo sie, ze rozbijamy co prawda na
poczatku ciag 26 kart na 2 razy po 13, potem kazdy z tych dwoch na 7 i 6, ale
potem tworza sie miedzy roznymi ciagami dodatkowe uporzadkowane podciagi.
Nie potrafie co prawda udowodnic, ze te 6 tasowan nie wystarczy, ale sklaniam
sie mocno ku takiej hipotezie.

Pozdrawiam

M.

[marchewa4]

Sprawdzilem jeszcze jedno: jesli bedziemy talon zawsze dzielic na polowe i
wtasowywac karty dokladnie naprzemiennie, to odwrocenie porzadku otrzymamy po
26 tasowaniach.

M.

[Gość: johndoe]

co prawda nie liczylem, jakos algorytm sluszny nie chce mi do glowy przyjsc, ale nie sadze, zeby najlepsza droga bylo przekladanie karta na karte, poza tym szesc na pewno nie wystarczy, dowodu nie mam oczywiscie:), ale moj maly rozumek nijak tego nie widzi / a dla uproszzenia baie sie 10 kartami/.
a tak btw witam systkich
pzdr

[cardemon]

Gość portalu: johndoe napisał(a):

> co prawda nie liczylem, jakos algorytm sluszny nie chce mi do glowy przyjsc,
> ale nie sadze, zeby najlepsza droga bylo przekladanie karta na karte, poza >
> tym szesc na pewno nie wystarczy, dowodu nie mam oczywiscie:), ale moj maly
> rozumek nijak tego nie widzi / a dla uproszzenia baie sie 10 kartami/.
> a tak btw witam systkich

Rwoniez serdecznie witam "starego" uczestnika tego forum. :)
Oczywiscie przekladanie "karta na karte" nie jest obligatoryjne. Po prostu dla
załozonego przeze mnie koncowego ukladu takie tasowanie bylo optymalne.
Wiadomo, ze jesli w wyjsciowej kupce jakies dwie karty znajda sie w takiej
samej kolejnosci, w jakiej maja rowniez byc w koncowym ukladzie, to podczas
zadnego tasowania nie beda one rozdzielane (mozemy sie nawet umowic, ze
wpuscimy miedzy te karty kropelke kleju).
Czy szesc tasowan wystarczy, czy nie, tez nie jestem w stanie udowodnic, ale
piec na pewno jest za malo.

pzdr. CdM

[cardemon]

marchewa4 napisał:

> Sprawdzilem jeszcze jedno: jesli bedziemy talon zawsze dzielic na polowe i
> wtasowywac karty dokladnie naprzemiennie, to odwrocenie porzadku otrzymamy po
> 26 tasowaniach.
>
> M.

Ha! Bardzo mi sie to podoba. Czuje, ze najlepiej by bylo napisac do tego jakis
program komputerowy, ktory by odpowiednio tasowal te karty. Jesli ktos by taki
program napisal, to bardzo prosze o kontakt na moj adres e-mail. :)

pzdr. CdM

[vortex]

marchewa4 i cardemon, obaj macie rację. Z moich obliczeń wynika że jeżeli
liczba katr jest równa 2 do n-tej to wtedy wystarczy n tasowań, jak mówił
cardemon. Jednakże próbowałem zastosować to do innych ilości kart i nie zawsze
to wychodzi. Liczy się wtedy najbardziej odległość karty na wierzchu do środka
talii czyli połowa kart. Zakładałem dzielenie kart na równe połowy (wydaje mi
się że wtedy będzie najszybciej) i tasowanie jedna za drugą. Tak więc tym
sposobem aby potasować 10 katr trzeba 10/2=5 tasowan a nie 4 tasowan jak by
wynikało z teorii cardemona. Nie wiem czy miał to na myśli marchewa4 czy tylko
podał liczbę ale 26 tasowań to połowa 52, to mnie naprowadziło na ten trop.
Polega to na tym że 2 do n-tej dzielone na 2 zawsze da liczbę która da się
jeszcze podzielić na dwa, w innych liczbach tak nie ma i dlatego po 3
tasowaniu dzieli się nam na kupki po 7,6 kart co psuje wszystko, i właśnie
dlatego twierdzenie cardemona nie ma zastosowania w takich przykładach.
Jak na razie jestem przekonany co do prawdziwości moich słów, proszę jednak
spróbować potasować 10 katr w mniej niż 5 tasowań, używając nieregularnego
tasowania. Powodzenia.

[mesquaki]

vortex napisał:

> Liczy się wtedy najbardziej odległość karty na wierzchu do środka
> talii czyli połowa kart.

To jest chyba najgorszy przypadek. Czasami wystarczy mniej tasowań, np.
do odwrócenia kolejności 40 kart wystarczy 10 tasowań, 26 - 9, a 42 - 7.

pozdrawiam wszystkich
mes (z wędzidłem w pysku :)

[vortex]

no tak, wyszlo z tego ze mozna byc pewnym tylko co do ilosci kart rownej 2 do
n-tej. Resztę trzeba indywidualnie albo jakimś wzorem. Pozdrawiam.

[musztardek]

marchewa4 napisał:

> I teraz zadanie. Czy mozna z jednego ukladu kart przejsc do innego, dowolnego
> ukladu kart wykonujac 5 opisanych powyzej tasowan? Odpowiedz uzasadnij,
> najlepiej tak, zeby i inni zrozumieli ;-).

witam wszystkich,

Wygląda na to, że można wszystko udowodnić i wyjaśnić dość przejrzyście.

Jeśli 52 karty i chcemy odwrócić ich kolejność, to 5 tasowań nie wystarczy, ale
6 NA PEWNO wystarczy.

Ponumerujmy karty po kolei od dołu - od 1 do 52. Teraz spójrzmy na nie od góry:
Nazwijmy ciągiem takie leżące jedna pod drugą karty, że każda kolejna ma
większy numer od poprzedniej. Jeśli karta leżąca poniżej ma numer niższy, to w
tym miejscu kończy się jeden ciąg, a zaczyna kolejny.

A zatem w początkowym układzie mamy 52 ciągi jednokartowe, prawda?

W pierwszym tasowaniu dzielimy karty na dwie równe kupki i nakładamy na siebie
karty raz z jednej kupki, raz z drugiej. Patrząc od góry karty będą leżały w
takiej kolejności:
26,52,25,51,24,50,23,49....2,28,1,27.

A więc mamy 26 ciągów po 2 karty każdy.

Tasowanie drugie - rozdzielamy karty na dwie kupki po 13 ciągów (będą znowu
równe).
tasujemy je tak, aby ciąg 1 utworzył jeden ciąg z ciągiem 14, C2 z C15, C3 z
C16 itd.

Efekt: mamy 13 ciągów po 4 karty każdy.

Tasowanie trzecie - rozdzielamy karty na dwie kupki: 6 ciągów w jednej, 7 w
drugiej(tym razem kupki będą nieówne).
tasujemy je tak, aby ciąg 1 utworzył jeden ciąg z ciągiem 7, C2 z C8, C3 z C9
itd. Ciąg C13 pozostanie taki jaki był, nie zmieszany z niczym

Efekt: mamy 7 ciągów; 6 x 8 kart i ostatni z 4 kartami.

Tasowanie 4 - rozdzielamy karty na dwie kupki: 3 ciągi w jednej, 4 w drugiej.
tasujemy je tak, aby ciąg 1 utworzył jeden ciąg z ciągiem 4, C2 z C5, C3 z C6.
Ciąg C7 pozostanie taki jaki był, nie zmieszany z niczym

Efekt: mamy 4 ciągów 3 x 16 kart i ostatni z 4 kartami.

Tasowanie 5 - rozdzielamy karty na dwie kupki: 2 ciągi w jednej, 2 w drugiej.
tasujemy je tak, aby ciąg 1 utworzył jeden ciąg z ciągiem 3, a C2 z C4.

Efekt: mamy 2 ciągi; jeden ma 32 karty, a drugi 20.

Tasowanie szóste: dzielimy na dwie kupki, po jednym ciągu w każdej. Tasujemy
tak, żeby oba ciagi ułożyły się w jeden ciąg.
A jeden ciąg 52-kartowy to kolejność od 1 do 52, patrząc od góry. Czyli
dokładnie na odwrót niż na początku, prawda?

A więc wystarcza 6 tasowań.

Skoro z każdym tasowaniem liczba ciągów zmniejsza nam się o połowę (z
zaokrągleniem w górę), to ogólnie rzecz biorąc:

n tasowań wystarczy do zmiany kolejności od 2^(n-1)+1 do 2^n kart.

Głowy nie dam, że napisałem to jasno, ale pewnie zozumiecie o co mi chodzi :)
Pozdrawiam serdecznie i cieplutko,

Musztardek

[vortex]

a jednak kardemon mial rację, ja zakładałem że zawsze daje sie równy połowy do
tasowania. Sam potem zasugerowałem żeby tasowac nierówno. :P Próbowałem zrobić
to co napisał marszałek ale niezbyt mi wyszło. Marszałku może rozpisz wyniki
wszystkich tasowań :) bo nie wiem czy wlasciwy ciąg pomijam podczas tasowania
nieparzystej ilości ciągów. Pozdrawiam.

[musztardek]

vortex napisał:

> Marszałku może rozpisz wyniki
> wszystkich tasowań :) bo nie wiem czy wlasciwy ciąg pomijam podczas tasowania
> nieparzystej ilości ciągów. Pozdrawiam.

Jejku, nie moge rozpisać wszystkiego - czasu mi nie starcza ostatnio :((
Ale tak naprawdę to wygląda na to, że nie ma znaczenia, które ciągi będziesz
mieszać, a który pozostawisz nietknięty - pierwszy, ostatni, czy któryś ze
środka. Ważne jest, żeby trzymać się zasady, że z każdych dwóch ciągów, które
mieszasz tasując, musi wyjść jeden ciąg. Popróbuj. Jak nie wyjdzie, to w końcu
rozpiszę wszystko :))

Pozdrawiam,
Musztardek

[mesquaki]

musztardek napisał:
(..)

A to zgrabne :).

pozdrawiam
m

[marchewa4]

Bardzo mi się podoba Twoje uzasadnienie, że kolejnośc można odwrócić w 6
tasowaniach. Gratulacje.
Pozostaje jeszcze otwarte pytanie: czy można z jednego układu uzyskać w 6
tasowaniach *dowolny* inny układ? Czy zajmowałeś się też tym zagadnieniem?

Z noworocznymi pozdrowieniami

M.

[musztardek]

marchewa4 napisał:

>> Pozostaje jeszcze otwarte pytanie: czy można z jednego układu uzyskać w 6
> tasowaniach *dowolny* inny układ? Czy zajmowałeś się też tym zagadnieniem?

Wygląda na to, że można. Wystarczy zastosować procedurę analogiczną do opisanej
przeze mnie:

1. Ułóż karty w kolejności "docelowej" (układ taki, jaki ma być po 6
tasowaniach)
2. Ponumeruj karty od góry - od 1 do 52.
3. Ułóż karty w kolejności 'wyjściowej'.

Będziesz miał pewną liczbę ciągów

(dla przypomnienia - Nazwijmy ciągiem takie leżące jedna pod drugą karty, że
każda kolejna ma większy numer od poprzedniej. Jeśli karta leżąca poniżej ma
numer niższy, to w tym miejscu kończy się jeden ciąg, a zaczyna kolejny).

Na pewno nie będzie ich więcej niż 52, prawda? Teraz, według tego co napisałem
w poście powyżej (18-12-2002 13:08) , z każdym tasowaniem możesz zmniejszyć
liczbę ciągów o połowę (z zaokrągleniem w górę). Tak więc bez względu na to,
jaki jest układ początkowy i docelowy, można to spokojnie wykonać w 6
tasowaniach.

Za chwilę spróbuję to przetestować na 'żywym organizmie', i pooglądam
jednocześnie skoki Małysza:) Jeśli moja procedura nie zda egzanimu, to się
odezwę z dementi :)
Pozdrawiam,
Musztardek

[vortex]

hahaha dopiero teraz zauważyłem że nazwałem Cie Marszałkiem a ty musztardek
jesteś, hahahha ale ze mnie jełopa. Kurde starzeje się. :P

[cardemon]

vortex napisał:

> hahaha dopiero teraz zauważyłem że nazwałem Cie Marszałkiem a ty musztardek
> jesteś, hahahha ale ze mnie jełopa. Kurde starzeje się. :P

A mnie nazwales kardemonem i choc fonetycznie jest to OK, to jednak jestem
cardemonem od cardamomu (w pisowni angielskiej), czyli przyprawą będącą
mieszanką techniki (samochody i temu podobne) oraz sił transcendentalnych
(demonów i innych zjaw parafizycznych). A może ja tez sie juz starzeję... :)))

pzdr. C.deMon

[andy._]

A ja myślałem, że cardemon to pirat drogowy ;-)

Pozdr. A.

[vortex]

Dobra może zostanę przy Generale Musztardku, :P

[andy._]

vortex napisał:

> ... nazwałem Cie Marszałkiem a ty musztardek jesteś ...

Nie degraduj musztardka bo pewnie już wyjął buławę z plecaka i nie chciałby
wracać tylko do lampasów i akselbantów ;-)

Pozdr. A.

[musztardek]

andy._ napisał:

> Nie degraduj musztardka bo pewnie już wyjął buławę z plecaka i nie chciałby
> wracać tylko do lampasów i akselbantów ;-)

Ech, gdzie mi tam do tak zaszczytnych tytułów? Kiedyś, owszem, piąłem się po
szczeblach kariery wojskowej, ale, widzicie, za miękkie serce miałem (może się
po prostu starzeję, hahaha;). Zawsze mi żal było tych wszystkich więźniów i
skazańców, którzy coś tam przeskrobali i już wyrok śmierci na cich czekał.
Wdałem się w konspirację - a to coś pokombinowaliśmy z żarówką na świetlicy, a
to z kapturami na głowach, no i w końcu ktoś zauważył, że już od lat wyroki
śmierci pozostają tylko na papierze. Ktoś to pokojarzył z moją komitywą ze
skazańcami i pa pa, kariero :(

Pozdrowienia dla wszystkich Demonów z tego Forum :)
Musztardek_cywilny

jeszcze jedna zabawa

[mesquaki]

Mamy 52 karty. Pierwszą z nich chcemy umieścić na dowolnym innym miejscu w
talii, stosując tylko idealne tasowania. Idealne tasowanie to takie, w którym
dzielimy talię na połowy a następnie łączymy je: karta z jednej połowy na
przemian z kartą z drugiej. Ile i jakich tasowań trzeba wykonać?