Calzini

[axpgn]

Il sindaco di Castelrotto di Sopra ha dieci paia di calzini, che variano in dieci diverse sfumature di colore, dal grigio medio (1) al nero (10).
Quando li ha indossati tutti, li lava e li asciuga tutti insieme; purtroppo nella lavanderia la luce è scarsa e là tutti i calzini paiono neri, perciò vengono appaiati a caso.
Un paio di calzini è inaccettabile da indossare se la differenza di colore tra i due calzini è maggiore di una sfumatura.

Qual è la probabilità che i calzini vengano appaiati in modo tale che tutte le dieci coppie siano accettabili?


Cordialmente, Alex

[Quinzio]

Ci provo..

$F_{n+1}/{n!} $

dove $F_n$ e' l'ennesimo numero di Fibonacci.

Con $n=10$,

$F_{n+1}/{n!} = 89/3628800$

[axpgn]

No.

Perché questa risposta?

[Quinzio]

"axpgn":No.

Perché questa risposta?

Ad esempio:
3 paia di calzini, sfumature da 1 a 3, differenza massima 1.

Al denominatore c'e' $3!$, su questo dovremmo essere d'accordo, direi.
Al numeratore i casi accettabili sono:
a) 123
b) 132
c) 213
I numeri scritti sono il secondo elemento di ogni paio di ognuna delle 3 coppie.
Il primo elemento di ogni paio e' in ordine numerico 123.
Ad es. il c) va visto come: (1,2)-(2,1)-(3,3)

$F_{3+1} = 3$

e $F_{3+1}/{3!} = 3/6 $

I casi accettabili per $n=4$ sono $5$
1234
1243
1324
2134
2143

e $F_{4+1} = 5$.

Il numero di casi accettabili segue la sequenza di Fib. 0 1 1 2 3 5 8 13 21 34 55 89 ...

Mi sembra che sia tutto a posto, non so dove sia l'inghippo.

[axpgn]

@Quinzio

I casi accettabili sono di più.
Per esempio, con tre paia di calzini hai i seguenti accoppiamenti:

$1a1b-2a2b-3a3b$
$1a2a-1b2b-3a3b$
$1a2b-1b2a-3a3b$
$1a1b-2a3a-2b3b$
$1a1b-2a3b-2b3a$

[Quinzio]

@Alex

Non riesco a capire cosa sono quei $b$ e $a$ che hai messo nelle coppie.
Da quello che avevo capito abbiamo 3 paia di calzini (nell'esempio $n=3$).
I calzini in fila li rappresentiamo con 6 cifre, ad es: 112233

Poi i calzini escono dalla lavatrice in ordine casuale.
Vengono presi e ne vengono fatte 3 coppie.
Ad es. escono in questa sequenza.
123132
Vengono fatte le coppie 12 - 31 - 32.
Questa accoppiata non e' accettabile perche' la coppia 31 differisce di 2.
A questo punto, cosa possono essere $a$ e $b$ ?

[axpgn]

I calzini sono due per ogni paio: $a$ e $b$

[Quinzio]

Eh.... mi vien dire: e quindi ?
Sono 2 ma sono indistinguibili.

[axpgn]

Hai un paio di calzini:
Prendi un calzino e lo appai con l'altro.
Un solo caso ed è accettabile.

Hai due paia di calzini:
Prendi un calzino, lo puoi appaiare con l'altro dello stesso colore oppure con uno dell'altro colore oppure con l'altro dell'altro colore.
Tre casi tutti e tre accettabili (l'altro paio viene sempre accettabile)
Già qui con Fibonacci non ci siamo.

Hai tre paia di calzini:
Per semplicità ma senza perdere di generalità, supponiamo di prendere un calzino dal colore più scuro (se vuoi puoi rifare lo stesso ragionamento partendo dal colore che vuoi).
Il calzino dal colore 1 lo puoi appaiare con l'altro dello stesso colore oppure con uno del colore 2 oppure con l'altro del colore 2 e basta; hai tre casi accettabili ma nel primo caso le altre due paia possono essere appaiate in tre casi (come dimostrato prima) portando il totale dei casi accettabili a 5.

And so on ...

[Quinzio]

Il problema e' a monte:

I calzini dello stesso colore sono indistinguibili.
Quindi non c'e' un calzino di un colore e "l'altro" dello stesso colore.
Ci sono 2 calzini per ogni colore, uguali.

In vita mia non mi sono mai messo un paio di calze dicendo questo e' il destro e questo e' il sinistro.
In qualunque negozio i calzini sono venduti a paia, e i due pezzi del paio sono identici.

[axpgn]

Ci riprovo ...

Metti due paia di calzini in lavatrice: in totale ci sono 4 calzini in lavatrice.
Ne prendi uno: adesso hai 3 (tre) MODI per scegliere il secondo, NON solo DUE.

[Quinzio]

Va bene Alex, d'accordo.
Vai avanti. Come si conclude il calcolo ?
Io ho il sospetto che alla fine, anche considerando i due calzini dello stesso colore come "diversi", il risultato alla fine sia lo stesso, che e' quello che ho dato.
Se consideri i due calzini dello stesso paio come distinti avrai che il numeratore e il denominatore della frazione Fib(n+1)/n! vengono moltiplicati per uno stesso fattore e quindi il risultato finale non cambia.
In tutto questo resta inteso che il confronto del colore viene fatto solo sulla base del colore.
Ad es il paio 3a4b e' accettabile, cosi' come il paio 3b4a e 3b4b, ecc...
Il testo del problema parla solo di colori.
E' secondo me e' corretto cosi'. L'esempio dei calzini ricorre spesso nell'immaginario dei problemi di combinatoria come coppia di oggetti non distinguibili.
Anche Bertrand Russell, per spiegare l'assioma della scelta, ricorre all'esempio dei calzini come paio di oggetti non distinguibili, al contrario delle scarpe che sono destra e sinistra.
The Axiom of Choice is necessary to select a set from an infinite number of pairs of socks, but not an infinite number of pairs of shoes.
 Bertrand Russell

Comunque, Russell a parte, andiamo avanti, abbiamo i calzini 1a e 1b.
Non so, come va a finire ?

[axpgn]

Stiamo parlando di probabilità e mi pare che tu non stia utilizzando nel modo giusto il concetto di indistinguibilità.
Per esempio se metto due palline bianche in un urna con alcune palline nere e poi ne estraggo una bianca, la probabilità di estrarne un'altra bianca dipende da quante nere ci sono; eppure sono indistinguibili!
Tornando ai calzini, ne metto in lavatrice tre paia di tre gradazioni diverse (6 oggetti: 1a, 1b, 2a, 2b, 3a, 3b).
Per semplicità ma senza perdere di generalità (provare per credere) supponiamo che il primo calzino estratto sia 1a; i 5 rimasti possono essere estratti in 120 modi diversi (permutazioni di 5 oggetti).
Delle 120 combinazioni di tre paia che si formano, 40 combinazioni sono accettabili (ovvero non contengono coppie 1-3), le altre 80 non lo sono.
Probabilità $1/3$

[buggy4]

$p=\frac{187}{3628800 }$?

[axpgn]

No.

[Quinzio]

"axpgn":Stiamo parlando di probabilità e mi pare che tu non stia utilizzando nel modo giusto il concetto di indistinguibilità.

A me invece sembra di prendere la situazioni piu' generica possibile, ovvero partendo dalle coppie gia' formate.
Quello che fai tu e' aggiungere un processo, quello di formazione delle coppie, che non e' richiesto e di cui non si sa nulla.

Oppure ad esempio, invece che di calzini si potrebbe parlare di un iper-cubo 10D, e le 20 facce 9D, prese a due a due opposte, sono le coppie.
Ad ogni faccia 9D viene associata una sfumatura e si guarda quanti cubi sono accettabili.
In questo caso non c'e' nessun processo di formazione delle coppie, i cubi nascono gia' formati, non c'e una faccia A e una faccia B.
Un cubo che si puo' ottenere da un altro cubo per rotazione o simmetria, e' di fatto lo stesso cubo.

[axpgn]

Per me sei partito per la tangente, diventi sempre più complicato

Metti i sei calzini in lavatrice (1a, 1b, 2a, 2b 3a, 3b).
Supponiamo tu estragga il calzino 1a; in lavatrice rimangono i calzini 1b, 2a, 2b, 3a, 3b; ora sarà pure vero che i calzini del colore 3 sono indistinguibili ma la probabilità di estrarre un calzino di colore 3 è DOPPIA di quella di estrarre un calzino di colore 1.
O non sei d'accordo?
Quindi la probabilità di avere una coppia 1-3 [non accettabile] è doppia rispetto a quella di averne una 1-1 [accettabile].
Non ti pare?

[size=85][Per il calcolo esatto occorre considerare i calzini di colore 2 ma era solo per esemplificare][/size]

[axpgn]

"Quinzio":Quello che fai tu e' aggiungere un processo, quello di formazione delle coppie, che non e' richiesto e di cui non si sa nulla.

Questo mi pare uno sbaglio grossolano: il cuore di questo problema consiste proprio nell'APPAIARE CALZINI e mi dici che non c'entra nulla e non è richiesto?

[axpgn]

Soluzione:

La probabilità è $683/(19*17*15*...*3)~~10^(-6)$

Per semplicità ma senza perdere di generalità supponiamo di iniziare ad appaiare i calzini partendo dal più scuro.
Supponiamo di avere $n$ paia di calzini e siano $f(n)$ i possibili modi di appaiarli in modo accettabile.
Pe $n<=2$ ogni accoppiamento è accettabile e quindi $f(1)=1, f(2)=3$
Per $n>2$, consideriamo un calzino del paio $n$ (quello più scuro).
Esso deve essere appaiato o con il suo compagno o con un calzino del paio $n-1$.
Se viene appaiato col suo compagno, rimangono $f(n-1)$ modi accettabili per appaiare i restanti $n-1$.
Se viene appaiato con un calzino della coppia $n-1$, il suo compagno deve essere appaiato con l'altro calzino $n-1$, per cui rimangono $n-2$ paia da accoppiare in $f(n-2)$ modi.
Dato che ci sono due modi per fare ciò si arriva alla conclusione che, per $n>2$, si ha $f(n)=f(n-1)+2f(n-2)$
Risolvendo la ricorrenza si giunge a $f(n)=(2^(n+1)+(-1)^n)/3$
In particolare $f(10)=683$.

Al denominatore i possibili accoppiamenti.
Un calzino può essere accoppiati agli altri $19$; un calzino dei rimanenti $18$ può essere accoppiato in $17$ modi e così via ...

Cordialmente, Alex