solitario non molto interattivo...

[ma_go]

il bambino zlatan si trova in spiaggia, in vacanza, ed è molto stupido.
si diverte quindi a fare un solitario che gli hanno insegnato i suoi (altrettanto stupidi) genitori yvonne e xavier:
zlatan dispone di un mazzo di carte francesi (A, 2/10, J, Q, K, quattro semi, semimazzo rosso e semimazzo nero, senza jolly, quindi 13 carte * 4 semi * 2 copie di ciascuna carta), e le mescola. dopodiché (ha le mani molto grandi, per essere un bambino) tiene il mazzo in mano, e gira le carte una ad una, e cerca di costruire le 4 scale (da K ad A) di ciascun seme, semplicemente mettendo tutte le carte al loro posto, e rimettendo le carte inutili in fondo al mazzo.
zlatan vince quando ha 4 scale complete, di 4 semi distinti.
(esempio: appena zlatan trova il primo K di picche, lo mette in tavola; se trova poi una Q dello stesso seme, la mette dopo il K [ehm.. dire "mette la donna sopra il re" suonava malino...]; se invece trova un J prima della Q, lo mette in fondo al mazzo).
ora, il fratellino piccolo di zlatan, walter, che è molto più intelligente di zlatan (si sospettano scambi di culla), comincia a fare qualche considerazione e vi fa qualche domanda, tanto per vedere quanto ne sapete di combinatoria:
- questo stupido zlatan-solitario, è un gioco finito? (ovvero, esistono configurazioni per cui il gioco non finisce?)
- quante sono le disposizioni di carte che consentono la vittoria senza che alcuna carta (carta intesa come terna (valore, seme, colore del retro)) sia passata due volte?
- quante sono le disposizioni di carte che consentono la vittoria senza che alcuna carta (questa volta intesa come coppia (valore, seme)) sia passata tra le mani di zlatan lo stupido due volte?
walter, come tutte le persone intelligente, ha una componente bastarda non trascurabile, e quindi propone delle generalizzazioni bastarde:
consideriamo un mazzo di carte avente v valori per le carte (A, 2, 3... v), ed s semi, e m carte diverse per ogni carta (ovvero ci sono m assi di uno stesso seme)...
- quante sono le configurazioni del mazzo per cui zlatan vince al primo giro? (ovvero senza che una terna-carta ripassi?)
- consideriamo m=1, quante sono le configurazioni per cui si vince al secondo giro ma non al primo?
- al terzo ma non al secondo?
- si riesce a calcolare un numero medio di giri entro cui il gioco finisce?

[enomis_costa88]

- questo stupido zlatan-solitario, è un gioco finito? (ovvero, esistono configurazioni per cui il gioco non finisce?)

1) è finito. Infatti data una quasiasi configurazione si può dimostrare che in un "giro" si togle dal mazzo almeno una carta per seme, se non si è ancora finita la scala per quel seme.
Dim: se non ho ancora finito la scala di un seme vuol dire che ho nel mazzo la carta successiva nella scala e quando essa arriva nelle mani dello stupido zlatan viene tolta dal mazzo.
inoltre le carte nel mazzo sono in numero finito quindi sicuramente entro 13 (non è detto che si possa fare in 13..magari è migliorabile come risultato) giri avrò finito tutte e 4 le scale.

- quante sono le disposizioni di carte che consentono la vittoria senza che alcuna carta (questa volta intesa come coppia (valore, seme)) sia passata tra le mani di zlatan lo stupido due volte?

3) provo a rispondere al terzo quesito..

Step 1: le due carte uguali sono in due metà diverse del mazzo.
Per finire il gioco servono 4*13 carte. Le prime 4*13 carte devono essere diverse tra loro (se no una stessa carta passerebbe 2 volte nella mano di zlatan lo stupido). Ma 4*13 è mezzo mazzo quindi il primo mezzo mazzo è composto da carte diverse da cui deduco che carte uguali stanno in due metà diverse del mazzo.

Step 2: risultato senza tenere conto dei retrocarta.
divido la prima metà mazzo in 4 semi. Ciascuno dei 4 semi ha una disposizione obbligata: K,Q,...A però tra di loro i semi si possono disporre come gli pare e piace.
quindi le disposizioni della prima metà mazzo sono $ \frac {(13*4)!}{(13!)^4} $
Questo perchè voglio sapere solamente come si dispongono i semi tra di loro e quindi i tredici componenti di un seme li posso considerare come indistinguibili (esiste una sola permutazione accettabile per ogni seme nlla prima metà del mazzo) e per calcolarla uso la formula per gli anagrammi con ripetizione.
La seconda metà del mazzo la permuto come voglio e quindi in (13*4)! modi.
$ \frac {(13*4)!}{(13!)^4}*(13*4)! $

Se volessi (non richiesto) approfondire la questione direi anche che ho $ 2^{13*4} $ modi per scegliere i colori del retro delle carte che ho nella prima metà del mazzo in quanto ogni retro può essere scelto in 2 modi.

Va beh..questa sera mi tocca andare ad una festa avrei preferito pensare a questo problema..magari se bevo un po' poi inizio a provare sul serio a risolvere le generalizzazioni (e anche il punto 2) dopo averci giocato un pochino

[enomis_costa88]

- quante sono le disposizioni di carte che consentono la vittoria senza che alcuna carta (carta intesa come terna (valore, seme, colore del retro)) sia passata due volte?

Le configurazioni possibili sono tutte e sole quelle che permettono di finire il gioco entro un giro

Step 1) tolgo di mezzo subito i semi..
in quanti modi i possono combinare tra di loro i 4 semi indipendentemente da cosa contengono?
in $ \frac{(13*8)!}{(26)!^4} $
D'ora in poi lavorerò solamente all'interno di un seme. Le carte sono ora intese come coppia {numero,colore}

Step 2) perche si finisca la scala entro un giro come devono essere messe le carte di un seme?
esse devono contenere almeno una scala in ordine K,Q,J,....,A con le altre 13 carte disposte quasi completamente liberamente (spiego dopo..),
Sono chiamate carte vincolate le 13 carte appartenenti alla scala fissata, carte libere le altre 13.
Le carte vincolate possono essere scelte in $ 2^{13} $ modi differenti (disposizione con ripetizione).
Posso pensare di colorare di verde le carte vincolate e di giallo le carte libere e di numerarle secondo il tipo di carte..{13,12,...1} invece che {K,Q,J,...A}
La condizione necessaria perchè si finisca il gioco in un turno e la scala sia composta solamente da carte verdi è che tra ogni carta verde e la sua successiva (o tra l'inizio e la prima) non ci sia una carta gialla il cui numero è = a quello della successiva carta verde.
si verifica facilmente che questa condizione è anche sufficente.

Step 3)risultato..
Ora, dopo avere contato le combinazioni possibili con una scala date (quella verde) presente, non mi resta che togliere le combinazioni in cui la scala vincente ha almeno una carta gialla.
Tolgo le combinazioni con almeno una carta gialla j tra una carta verde (j+1) e la sua successiva j; in questo modo ho tolto tutte le configurazioni con almeno una carta gialla nella scala vincente almeno una volta (qualcuna l'ho tolta più di una volta..).
Ora però ho tolto 2 volte tutte le combinazioni con almeno 2 carte gialle con le stesse caratteristiche (ovvero j compreso tra j+1 e j verde..) e mi tocca riaggiungerle.
Ora devo continuare così usando il principio inclusione-esclusione.
le combinazioni con almeno K carte gialle nel risultato si trovano fissando 13+k carte in un ordine dato.
Esempio:13(K) Giallo,13 verde,.....A avrà 13 giallo nella scala vincente ed ha 14 carte fissate.
Con pochi calcoli il risultato (spero ) è:
$ (\sum_{k=0}^{13} {13 \choose k} (-1)^k \frac{(26)!}{(13+k)!}) $ .
il totale è quindi:
$ \frac{(13*8)!}{(26)!^4} (2^{13}\sum_{k=0}^{13} {13 \choose k} (-1)^k \frac{(26)!}{(13+k)!})^4 $

Buona Giornata

EDIT: Cancellata una generalizzazione un po' troppo affrettata..

[Marco]

- si riesce a calcolare un numero medio di giri entro cui il gioco finisce?

Claim da pausa caffè: nel caso s=1 (quindi permutazioni semplici di 1..v), il numero di giri medio è (v+1)/2.

[enomis_costa88]

Per mia fortuna questo ragionamento pare generalizzabile..percorrendo gli stessi passi

ora che ci ripenso un po' su mi pare d'avere fatto un'erroraccio e che non sia generalizzabile con questo stesso ragionamento (forse con uno simile si però)..
proverò a correggere se ne sono in grado

[ma_go]

- si riesce a calcolare un numero medio di giri entro cui il gioco finisce?

Claim da pausa caffè: nel caso s=1 (quindi permutazioni semplici di 1..v), il numero di giri medio è (v+1)/2.

ok, piccola simpatica osservazione...
le scale (e i vari semi) sono completamente indipendenti, quindi tale numero medio funziona per ogni s (ci sono solo cose che da contare in più, il numero medio non è funzione di s, per quanto mi risulti)...

ora, sia $ \iota $ tale che $ \iota(k) = v-k $, e sia $ \sigma $ la permutazione associata ad un mazzo qualunque (di un solo seme, tanto abbiam detto che va bene per tutti): supponiamo che $ \sigma $ richieta $ g $ giri di mazzo perché la corrispondente partita sia finita.
allora (claim) $ \iota(\sigma) $ ne richiede $ v+1-g $.
infatti, consideriamo una sequenza massimale $ n_k, n_{k-1}, \dots, n_{l+1}, n_l $ crescente (quindi $ n_k > n_l $, visto che $ v\ge k>l > 0 $) tale che $ \sigma(n_i) = i $ per $ i = l,..,k $.
questa sequenza di carte sarà "messa in tavola" in un solo giro di mazzo, e la carta k sarà la prima ad essere messa giù, in quel giro di mazzo (poiché la sequenza è massimale): questo significa che la carta $ k+1 $ (escludiamo il caso in cui $ k = v $, che tratto dopo) si trova, nel mazzo iniziale, dopo $ k $.
ora, definiamo tutti i possibili $ k $ come "pivot" del mazzo: tutte le prime carte ad essere messe giù ad ogni "giro di mazzo". il numero di pivot di una permutazione è il numero di giri che servono per finire il gioco.
ora, però, se $ \sigma $ ha $ g $ pivot, $ \iota(\sigma) $ ne ha $ v+1-g $, visto che la carta $ v $ dev'essere un pivot, tutti gli altri pivot di $ \sigma $ non sono pivot, e tutti i non-pivot diventano pivot...
quindi ad ogni permutazione con $ g $ pivot ne corrisponde una ed una sola (visto che $ \iota(\iota) $ è l'identità) con $ v+1-g $ pivot, quindi il numero medio di giri è esattamente $ \displaymath \frac{v+1}{2} $...
scusate se mi sono dilungato, ma non riesco a spiegare decentemente combinatoria -.-

[Marco]

ok, piccola simpatica osservazione...
le scale (e i vari semi) sono completamente indipendenti, quindi tale numero medio funziona per ogni s (ci sono solo cose che da contare in più, il numero medio non è funzione di s, per quanto mi risulti)...

Caro MaGo, la tua è una piccola simpatica stupidaggine. Contresempio:
v=2, s=1: il mazzo può essere 1 2 (un giro) o 2 1 (due giri). numero medio di giri: 3/2.
v=2 s=2: un giro sse 1 < 2 e 1' < 2'. Il tutti gli altri casi, due giri. Numero medio di giri: 7/4.

[ma_go]

uh, ok..
almeno, non hai detto che il ragionamento per $ s = 1 $ è completamente cannato ^^

[Marco]

Completamente cannato no, ma certo, che ti complichi la vita!!!

Per induzione. v = 1 son capaci anche i sassi.

Ora, considera un mazzo con v carte. Infila la carta "v+1" da qualche parte

Quand'è che il numero di giri cresce? Quando "v+1" capita prima di "v", serve un giro in più, altrimenti lo stesso numero di giri. E' più probabile che "v+1" sia prima o dopo "v"? E' equiprobabile, per simmetria.

Morale: giri medi(v+1) = g.m.(v) + 1/2. []

Fine della storia. M.