OliForum Matematico

Date n carte se ne facciano 3 mazzetti. Si dica a qualcuno di scegliere una carta e ci si faccia dire solo in che mazzo si trova. Fatto ciò si metta il mazzo contenente la carta tra gli altri due mazzi. Si dispongano nuovamente le carte e si ripeta l'operazione per due altre volte. Dopo che si è saputo per la terza volta in che mazzo si trovi la carta, si può sapere con precisione di che carta si tratti.

Qual è?

...Forse la domanda è "per quali n il gioco riesce?".
Vero?

NO! VOGLIO SAPERE QUALE CARTA IL MIO COMPAGNO HA SCELTO.

Allora chiedilo a lui, invece di sbraitarmi addosso.

Non credo che vi siano altri modi per risolvere il giochino, se le carte sono più di 27. Tu che dici?

Per quello che ho fatto il gioco può uscire per tutti gli n multipli di 3 che siano dispari.

Lo vedo strano, se ho ben capito il testo.

La "vittima" può scegliere una carta qualunque tra $ 3^n $; a questo punto (fissato lo stato iniziale del mazzo di carte) il nostro gioco si "ramifica" a seconda delle risposte che otteniamo: ci sono 3 possibili risposte per ognuna delle tre domande, quini $ 3^3=27 $. Possiamo individuare una carta diversa in ognuno dei 27 "rami" corrispondenti alle diverse risposte ottenute: potrebbero esserci due "set" di risposte ottenute che ci portano alla stessa carta (e quindi /meno/ di 27 carte) ma mai comunque /piu'/ di 27 carte (a meno di rispondere a caso, è impossibile che data la stessa situazione iniziale e le stesse risposte indichiamo di volta in volta due carte diverse).

Quindi le "possibili diverse carte" che riusciamo a indicare come scelte sono 27, meno del numero di possibili scelte di carte che il compagno può fare (se n>27).
In conclusione mi sembra che non si riesca a indovinare sempre la carta scelta.

(Spero che il ragionamento sia spiegato bene, è un po' difficile da formalizzare... )

ciao,

Non ci sono dubbi, è l'asso di coppe!
Scherzi a parte, shuzz intendeva chiedere in quale posizione si trova la carta scelta dall'amico. E questa è, saputo per la terza volta in che mazzo si trova, la carta centrale.
Intuitivamente (non ho compreso a pieno la tua dimostrazione, fph) mi sembra che il gioco riesca per ogni numero n di carte pari ad un potenza di 3, a patto che si possa ripetere l'operazione un numero di volte pari al logaritmo in base 3 di n.
Almeno con il procedimento descritto da shuzz.

A me esce che la carta incriminata è la (n+1)/2 -esima, sempre e ripetendo solo tre volte il procedimento. Le limitazioni di n sono quelle che avevo sopra elencato. Sono sicuro perchè il gioco (ho provato al massimo con 29 carte) esce sempre.

Listen, buddy.
Abbi pazienza, ma come puoi essere sicuro che per ogni n il gioco riesce, se tutto ciò che hai fatto è provarlo fino a n=29?
Seconda cosa: hai detto prima che il gioco riesce per tutti i multipli dispari di 3, ma si dà il caso che 29 non lo sia, e nemmno 28. Bisogna dedurre che i tuoi tentativi si sono fermati in realtà a n=27, caso in cui il gioco riesce ancora?
Ora, se l'argomentazione di fph non ti convince (argomentazione che tra l'altro non fa una piega), per favore metti un po' di buona volontà e guarda tu stesso cosa succede per n>27. Vogliamo scommettere che c'è sempre almeno una scelta della carta che non la manda nel posto prestabilito?

@Singollo: ok, ma shuzz insiste col dire che il procedimento va ripetuto solo 3 volte, e non logaritmo in base 3 di n.

Ok. Facciamo il gioco. Il mazzo all'inizio ha 28 carte, numerate da 1 a 28.
Il mazzetto che contiene la carta scelta da me è sempre il primo. Che carta ho scelto?

@Shuzz
Se non ti fidi, vedila in questo modo; supponiamo per semplicità di notazione n multiplo di 3 (il ragionamento può essere banalmente adattato aggiungendo dove servono le carte mancanti):
passo 1) Stabilisci la posizione della carta nel mazzo (modulo 3)
passo 2) Stabilisci la posizione della carta in un mazzetto di n/3 carte (modulo 3)
passo 3) Stabilisci la posizione della carta in un mazzetto di n/9 carte (modulo 3)

Se l'ultimo mazzetto ha + di tre carte, ovviamente la posizione non è unica...

@Marco:

Che carta ho scelto?

2 di picche

Singollo ha scritto:non ho compreso a pieno la tua dimostrazione, fph

Provo a esplicitare un po' di piu' il ragionamento (che spero sia abbastanza istruttivo):
supponiamo che esista un procedimento (un "algoritmo") per determinare la carta scelta in base alle informazioni che ci passa il nostro amico.
Partiamo da un mazzetto di carte numerate da 1 a n ed eseguiamo il primo passo.
Ora, abbiamo tre possibilita': che il nostro amico risponda "1", "2" o "3". Per ognuna di queste possibilita' eseguiamo una certa operazione (riordinare le carte, ma qui non ci importa qui sapere cosa esattamente) e poi facciamo un altra domanda; di nuovo abbiamo tre sotto-possibilita', per ognuna delle quali facciamo un'operazione e un'altra domanda.
To sum up, le possibili "informazioni" che possiamo ottenere alla fine del processo sono solo le risposte alle possibili domande, che sono 27. Il nostro algoritmo quindi puo' essere formalizzato come una "tabella di risposte" (o, meglio, un "albero"... e qui mi servirebbe un disegno, purtroppo )
cioe' qualcosa del tipo
risposte | carta scelta
1-1-1..............1
1-1-2..............10
1-1-3..............19
1-2-1..............4
.
.
.
3-3-2..............26
3-3-3..............27

(i numeri nella seconda colonna potrebbero essere sbagliati, li ho messi solo per dare un'idea piu' "visibile" del procedimento)

Ora, pero' le possibili "risposte" sono solo 27, mentre il nostro algoritmo dovrebbe prevedere (almeno) una possibile risposta per ognuna delle carte che possiamo scegliere all'inizio, cioè n, se vuole dare la risposta esatta per ogni possibile scelta iniziale della carta da indovinare. Quindi se n>27 abbiamo un assurdo.
In generale quindi si vede che servono almeno $ \log_3 n $ "domande" per avere un algoritmo buono.

Se avete capito questo ragionamento, potete provare a risolvere questo problema: dimostrare che un qualunque algoritmo (per esempio su un computer) per mettere un insieme di n numeri (che supponiamo diversi tra loro) in ordine crescente facendo solo dei confronti tra due numeri ha bisogno di fare almeno log_2 n! =~= n log n confronti.

Spero di essere stato chiaro, anche se temo di no

ciao a tutti,

Chiarissimo.

Errata Corrige

Scusate colpa mia, ho sbagliato a srivere, ho provato fino a 39 carte.

Questo giochetto l'ho dimostrato con le matrici . Provo a scrivrene una per esempio per n=15:
Dopo la prima scelta le carte possibili sono:
No No No
No No X
X X X
X No No
No No No

Dopo la seconda scelta:
No No No
No No No
X X X
No No No
No No No

Con la terza scelta so con certezza la posizione della carta.

Facciamo la stessa cosa per 39 carte, numerate da 1 a 39.
Supponiamo che io scelga la carta 1:
Passo 1) La carta si trova (ovviamente) nel primo mazzetto.
Passo 2) La carta si trova nel mazzo ricomposto nella posizione 14, quindi finisce nel mazzetto 2.
Passo 3) La carta si trova nel mazzo ricomposto nella posizione 15, quindi finisce nel mazzo 3.

Supponiamo che io scelga la carta 28:
Passo 1) La carta si trova nel primo mazzetto.
Passo 2) La carta si trova nel mazzo ricomposto nella posizione 23, quindi finisce nel mazzetto 2.
Passo 3) La carta si trova nel mazzo ricomposto nella posizione 21, quindi finisce nel mazzo 3.

Quale carta ho scelto, la 1 o la 28?