Il gioco dei tre mazzetti

[shuzz]

Per 39 carte:
Dopo la I scelta:
No______No______No
No______No______No
No______No______No
No______No______No
No______X_______X
X_______X_______X
X_______X_______X
X_______X_______X
X_______X_______No
No______No______No
No______No______No
No______No______No
No______No______No

Dopo la II scelta:
No______No______No
No______No______No
No______No______No
No______No______No
No______No______No
No______No______X
X_______X_______X
X_______No______No
No______No______No
No______No______No
No______No______No
No______No______No
No______No______No

Dopo la III scelta:
No______No______No
No______No______No
No______No______No
No______No______No
No______No______No
No______No______No
X_______X_______X
No______No______No
No______No______No
No______No______No
No______No______No
No______No______No
No______No______No

Quindi qualsiasi gruppo metterò in mezzo avrà le prime 13 (oppure n/3) carte davanti più ((n/3)-1)/2 che faranno essere la carta scelta (n+1)/2

[MindFlyer]

Allora shuzzino, vedo che perseveri in questa tua diabolica convinzione che bastino sempre 3 scelte per determinare la carta.
Ora, vorrei solo farti notare che dai tuoi schemini si vede chiaramente che dopo la terza scelta vi sono non una, ma 3 carte possibili. Quindi si rende necessaria una quarta scelta! Questo è vero fino a 81 carte, dopodiché 4 selte non basano più, ma ce ne vogliono 5, e così via.
Ti prego adesso seriamente di convincerti di questo, leggendo con calma i post precedenti, e magari facendo anche qualche esperimento in più (però conta bene il numero di scelte, altrimenti siamo da capo!).

[moebius]

Dovendo studiare una cosa che non mi piace, passo il tempo a farti lo "schemino 4 dummies" (senza offesa) con le famose 39 carte.
Scelgo la carta 1 che segnerò in bold e segnerò pure la 28 sottolineata, per i motivi che leggerai sotto:
-Step 1

Mazzetti:
01 02 03
04 05 06
07 08 09
10 11 12
13 14 15
16 17 18
19 20 21
22 23 24
25 26 27
28 29 30
31 32 33
34 35 36
37 38 39

- Step 2

Mazzetti:
02 05 08
11 14 17
20 23 26
29 32 35
38 01 04
07 10 13
16 19 22
25 28 31
34 37 03
06 09 12
15 18 21
24 27 30
33 36 39

- Step 3

Mazzetti:
02 11 20
29 38 07
16 25 34
06 15 24
33 05 14
23 32 01
10 19 28
37 09 18
27 36 08
17 26 35
28 29 30
31 03 12
21 30 39
13 22 31

A questo punto il terzo mazzetto va in mezzo, quindi la carta 01 va in posizione:
13 + 6 = 19 e non (n+1)/2 = 20
E non provare a dire che è (n+1)/2 - 1 in questo caso per qualche tipo di parità o di macumba del numero 39, perchè la carta 28 va in posizione 20=(n+1)/2...

[shuzz]

E' vero. Mi sono sbagliato.

Però a prescindere dal numero di volte che va scelto il mazzo la carta sarà sempre la (n+1)/2 -esima, giusto?

[moebius]

No, controesempio sciocco, n potrebbe non essere dispari

[shuzz]

Infatti avevo successivamente posto le condizioni di n dispari e multiplo di 3.

[fph]

E' vero. Mi sono sbagliato.

No problem. La cosa importante e' che hai posto un problema interessante e che stiamo riuscendo a "risolverlo" completamente.
I problemi "aperti" al momento sono:
1) date n carte, quante iterazioni del "gioco dei tre mazzetti" servono per essere sicuri di indovinare la carta scelta? Sappiamo già che sono almeno log_3 n; bastano sempre?
(questo secondo me abbiamo tutti gli elementi per chiuderlo, qualcuno si faccia avanti...)
2) se volete, c'è sempre il mio problemino su "dimostrare che ci vogliono almeno log_2 n! confronti per ordinare n numeri".

e poi, possiamo porci qualche altro problema e cercare di risolverlo... dopotutto, la matematica funziona cosi'

ciao,

[moebius]

Bastano log_3 n "arrotondato per eccesso" iterazioni:

passo 1) Stabilisci la posizione della carta nel mazzo (modulo 3)
passo 2) Stabilisci la posizione della carta nel mazzo (modulo 9)
passo 3) Stabilisci la posizione della carta nel mazzo (modulo 27)
....
passo n) Stabilisci la posizione della carta nel mazzo (modulo 3^n)

Quindi al passo n-esimo la soluzione è unica sse il mazzo ha non più di 3^n carte.

Oppure come controesempio del fatto che non ne bastano di meno, basta far vedere che la carta 1 e la carta 3^m + 1 hanno la stessa "orbita" nei mazzetti se m<n è il numero di iterazioni.

Per la 2 ci sto pensando...

[fph]

Bastano log_3 n "arrotondato per eccesso" iterazioni:

ok!

[moebius]

Vedi se ti piace questa per la 2:
Nel caso di interi distinti ogni confronto può avere 2 risposte: < o > rispettivamente se il primo numero è minore del secondo o viceversa. Quindi le informazioni disponibili dopo k confronti non sono più di 2^k.
D'altra parte, avendo n numeri è possibile porli in n! configurazioni; tali configurazioni sono in bigezione con i possibili ordini su questi n numeri.
Poichè il nostro algoritmo deve fornire una risposta per ognuno degli n! ordini che si possano presentare, nella migliore delle ipotesi:
2^k = n! (il numero degli stati possibile eguaglia quello di output)
Prendendo il log_2 di ambo i membri si ha la tesi.
Vale la pena osservare che 2^k era il massimo di informazioni ricavabili dal confronto e quindi k=log_2 (n!) è il minimo di confronti necessario per ordinare la n-upla.