Cassaforte

[axpgn]

La serratura di una cassaforte è composta da tre ruote ($A, B, C$) ciascuna delle quali può essere impostata su otto posizioni.
A causa di un difetto del meccanismo, la porta si apre quando due qualsiasi delle ruote si trovano nella posizione corretta.
Quindi ognuno può aprire la cassaforte in $64$ tentativi (per esempio, semplicemente ruotando 8 volte la ruota $B$ per ogni posizione della ruota $A$).
Peraltro la cassaforte può essere aperta in un minor numero di tentativi: qual è il minimo?


Cordialmente, Alex

[utente__medio11]

Le $56$ sequenze $ABC$ che si ottengono assegnando ad $A$ e $B$ le disposizioni semplici $D_(8,2)$ e ponendo $C=B$, dovrebbero essere sufficienti: i casi con $A!=B$ sono ovviamente coperti, mentre per $A=B$ abbiamo i casi $B=C$ e $B!=C=>A!=C$ che sono anch'essi coperti dalle sequenze sopra descritte.

Si può fare di meglio?

[axpgn]

Sì, sì può fare meglio

[utente__medio11]

$32$ tentativi:

122 212 221
133 313 331
411 141 114
444
234 243 324 342 423 432
566 656 665
577 757 775
855 585 558
888
678 687 768 786 867 876

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Se le ruote possono essere impostate su \(n\) posizioni allora my educated guess:
\[ \left \lceil \frac{n^2}{2} \right \rceil \]
da cui con \(n=8\) è \(32\) tentativi necessari.

[axpgn]

Giusto

Ma adesso dimostrate che è il minimo

[utente__medio11]

Non so se vale come dimostrazione, in ogni caso...

Se dividiamo gli $8$ valori possibili in $2$ gruppi, per esempio ${1,2,3,4}$ e ${5,6,7,8}$, almeno una coppia tra $AB$, $BC$ e $AC$ ricadrà nello stesso gruppo, ed è quella che ci limiteremo ad individuare, visto che è sufficiente indovinarne una.

Le coppie di valori possibili per il singolo gruppo sono date dalle $16$ disposizioni con ripetizione $D'_(4,2)$, ognuna delle quali potrà occupare le postazioni $AB$, $BC$ o $AC$. Queste $3*16$ coppie di valori possono essere inserite in $16$ terne come nel caso prima postato:

"utente__medio":122 212 221
133 313 331
411 141 114
444
234 243 324 342 423 432

Per finire, visto che i gruppi sono $2$, le terne da testare saranno nel peggiore dei casi $2*16=32$.

[axpgn]

Quello che hai scritto è il metodo che ho usato per trovare la soluzione ma purtroppo non dimostra che è anche il minimo ...

[utente__medio11]

Non so se è la strada giusta (o la più semplice), ma secondo me basterebbe dimostrare che

"utente__medio":Se dividiamo gli $ 8 $ valori possibili in $ 2 $ gruppi, per esempio $ {1,2,3,4} $ e $ {5,6,7,8} $, almeno una coppia tra $ AB $, $ BC $ e $ AC $ ricadrà nello stesso gruppo, ed è quella che ci limiteremo ad individuare, visto che è sufficiente indovinarne una.

sia l'approccio più "efficiente".
Da qui, in base al resto del mio precedente post, ne conseguirebbe che il minimo numero di tentativi è proprio $32$.
Nel caso ci penso...

[utente__medio11]

Va bene come dimostrazione?

Visto che a noi basta individuare una singola coppia ($AB$, $BC$ o $AC$), e che se dividiamo gli $8$ possibili valori in $m>2$ gruppi non è detto che almeno una delle suddette tre coppie sia costituita da valori appartenenti allo stesso gruppo, il numero minimo di tentativi sarà dato da:

$min(D'_(8-i,2)+D'_(i,2))=min((8-i)^2+i^2) \ \ \ \ \ \ i=0,1,2,3,4$

Da cui si deduce che il minimo è associato appunto a $i=4$.

[axpgn]

Me lo rispieghi che non ho capito?

[utente__medio11]

Domani provo ad argomentare meglio.

[utente__medio11]

Detta $ABC$ la soluzione, con $A$, $B$ e $C$ che possono assumere i valori da $1$ a $8$, a noi basta individuare almeno una delle tre coppie ordinate $AB$, $BC$ e $AC$.

Dividiamo i valori da $1$ a $8$ in $m$ gruppi, e per gli $n$ valori di ciascun gruppo calcoliamo tutte le possibili coppie ordinate, ossia le disposizioni con ripetizione $D'_(n,2)=n^2$, le quali possono essere inserite in altrettante terne in modo che ciascuna disposizione compaia (un'unica volta) in corrispondenza sia di $AB$ sia di $BC$ sia di $AC$:

- per $m=1$ avremo il solo gruppo ${1,2,3,4,5,6,7,8}$, i cui valori determinano $8^2=64$ disposizioni con ripetizione. In questo caso dalle corrispondenti $64$ terne sarà possibile individuare sia $AB$ sia $BC$ sia $AC$;

- per $m=2$ avremo, in funzione della cardinalità, quattro tipologie di coppie di gruppi, i cui $8-i$ e $i$ valori (con $i=1,2,3,4$) determinano $(8-i)^2+i^2$ disposizioni con ripetizione. In questo caso dalle corrispondenti $(8-i)^2+i^2$ terne sarà possibile individuare almeno uno tra $AB$, $BC$ e $AC$ (visto che almeno due tra $A$, $B$ e $C$ ricadranno nello stesso gruppo);

- per $m>2$ è inutile soffermarsi, visto che $A$, $B$ e $C$ potrebbero ricadere in tre gruppi diversi.

Quindi in definitiva il numero minimo di tentativi sarà dato da:

$min((8-i)^2+i^2)=32 \ \ \ \ \ \ \ [i=0,1,2,3,4]$

[axpgn]

Non riesco a starti dietro ... faresti qualche esempio concreto? In $m=2$, per $m=1$ non ci interessa mentre per $m>2$ lo lasciamo per dopo ...

Ho capito cosa intendi con "quattro tipologie di coppie di gruppi" ma poi come passi da coppie a terne?

Ho una dimostrazione (non mia) che prima o poi posterò ma aspetto di capire la tua ...

[utente__medio11]

Per $i=3$ potremo considerare per esempio i seguenti due gruppi:

- ${1,2,3,4,5}$, le cui $25$ disposizioni con ripetizione $D'_(5,2)$ possono essere inserite in altrettante terne (in modo che ciascuna disposizione compaia un'unica volta in corrispondenza sia di $AB$ sia di $BC$ sia di $AC$), per esempio nel seguente modo:

555
133 313 331
411 141 114
322 232 223
244 424 442
345 354 435 453 534 543
125 152 215 251 512 521

- ${6,7,8}$, le cui $9$ disposizioni con ripetizione $D'_(3,2)$ possono essere inserite in altrettante terne, per esempio nel seguente modo:

666 777 888
678 687 768 786 867 876

A questo punto, visto che almeno due tra $A$, $B$ e $C$ ricadranno nello stesso gruppo, i tentativi costituiti dalle suddette $25+9$ terne saranno sicuramente in grado di individuare almeno uno tra $AB$, $BC$ e $AC$.

[axpgn]

Ok, adesso ho capito ...

Un paio di considerazioni ...

- non è detto che si possa sempre trasferire tutte le coppie in altrettante terne dove ognuna compaia una sola volta; detto questo però l'inghippo viene superato dal fatto che hai trovato un esempio che funziona quindi tutto ok.

- per $m>2$ il fatto che possano cadere in gruppi diversi non dimostra l'impossibilità che accada; è una congettura più che plausibile ma, a mio parere, rimane una congettura.

[utente__medio11]

"axpgn":non è detto che si possa sempre trasferire tutte le coppie in altrettante terne dove ognuna compaia una sola volta

Nel senso che andrebbe dimostrato o pensi che non sia sempre possibile farlo?
In ogni caso anche se modificassimo la formula in

$ min((8-i)^2+i^2+x_i) \ \ \ \ \ \ \ [i=0,1,2,3,4] $

ho già mostrato con un esempio pratico che $x_4=0$, e quindi il risultato resterebbe comunque $32$.

"axpgn":per $ m>2 $ il fatto che possano cadere in gruppi diversi non dimostra l'impossibilità che accada; è una congettura più che plausibile ma, a mio parere, rimane una congettura.

Sinceramente non capisco la tua obiezione... per esempio consideriamo il seguente caso per $m=3$:

${1,2} \ \ {3} \ \ {4,5,6,7,8}$

Se $ABC=372$, da nessuna delle $2^2+1^2+5^2$ terne sarà possibile individuare uno tra $AB$, $BC$ e $AC$.

Una soluzione affinché sia valida deve funzionare sempre, quindi mi sembra abbastanza evidente che i casi da prendere in considerazione si limitino a $m=1,2$.

[axpgn]

"utente__medio":Nel senso che andrebbe dimostrato o pensi che non sia sempre possibile farlo?

Penso che non sia sempre possibile farlo in GENERALE, non nel caso specifico, per esempio se i valori fossero $9$ siamo sicuri che sia possibile farlo? $8$ mi pare un valore che si presta bene per questi "giochetti", magari altri no ...

"utente__medio":Se $ ABC=372 $, da nessuna delle $ 2^2+1^2+5^2 $ terne sarà possibile individuare uno tra $ AB $, $ BC $ e $ AC $.

Certo che è così ma è una dimostrazione per casi quindi dovresti provarli TUTTI, non basta uno o qualcuno ...

[axpgn]

Peraltro anche nel caso $m=2$ non si è dimostrato che $32$ è il minimo ma solo (si fa per dire) che $32$ è una soluzione

[utente__medio11]

"axpgn":Penso che non sia sempre possibile farlo in GENERALE, non nel caso specifico, per esempio se i valori fossero $9$ siamo sicuri che sia possibile farlo? $8$ mi pare un valore che si presta bene per questi "giochetti", magari altri no ...

Scusa, ma che c'entra $8$ o $9$ in questo contesto!?
Quello di cui si sta parlando è inserire le coppie ordinate $D'_(n,2)=n^2$ in altrettante terne in modo che ciascuna disposizione compaia (un'unica volta) in corrispondenza sia di $AB$ sia di $BC$ sia di $AC$.
Per quanto mi riguarda penso che ciò possa essere fatto per qualsiasi $n$; non l'ho dimostrato in modo rigoroso, ma mi sono dato un metodo che sembra funzionare.
Per esempio per $n=7$ abbiamo le seguenti $7^2=49$ terne:

123 132 213 231 312 321
345 354 435 453 534 543
567 576 657 675 756 765
246 264 426 462 624 642
147 174 417 471 714 741
155 515 551
116 161 611
225 252 522
277 727 772
366 636 663
337 373 733
444

"axpgn":[quote="utente__medio"]per esempio consideriamo il seguente caso per $ m=3 $:

$ {1,2} \ \ {3} \ \ {4,5,6,7,8} $

Se $ ABC=372 $, da nessuna delle $ 2^2+1^2+5^2 $ terne sarà possibile individuare uno tra $ AB $, $ BC $ e $ AC $.

Una soluzione affinché sia valida deve funzionare sempre, quindi mi sembra abbastanza evidente che i casi da prendere in considerazione si limitino a $ m=1,2 $.

Certo che è così ma è una dimostrazione per casi quindi dovresti provarli TUTTI, non basta uno o qualcuno ...
[/quote]
Continuo a non capire la tua obiezione.
Non c'è niente da provare visto che la sequenza $ABC$ non è nota... semplicemente bisogna limitarsi ai casi $m=1,2$ che funzionano sempre, a prescindere dai valori assunti da $A$, $B$ e $C$.

"axpgn":Peraltro anche nel caso $ m=2 $ non si è dimostrato che $ 32 $ è il minimo ma solo (si fa per dire) che $ 32 $ è una soluzione

Per me la seguente formula

$ min((8-i)^2+i^2) \ \ \ \ \ \ \ [i=1,2,3,4] $

lo dimostra, potresti argomentare il motivo per cui secondo te non lo farebbe?

Inoltre, visto che prima parlavi del caso in cui i valori fossero $9$ invece di $8$, seguendo lo stesso ragionamento si otterrebbe che il minimo numero di tentativi sarebbe

$ min((9-i)^2+i^2)=41 \ \ \ \ \ \ \ [i=0,1,2,3,4] $

[axpgn]

Faccio un passo indietro ...

Assumo di dividere gli otto valori possibili per ogni ruota in due gruppi da quattro numeri ciascuno.
Perché lo faccio? Perché dato che i valori corretti sono tre (uno per ruota), per il principio dei cassetti due di essi o stanno in un gruppo o stanno nell'altro.
Consideriamo il primo gruppo.
Le coppie ordinate con ripetizione che posso formare con quattro numeri sono sedici, ognuna di queste può stare in tre posizioni ($AB, BC, CA$) quindi in totale ho 48 possibilità.
Dato che però posso utilizzare delle terne e in ogni terna ci stanno tre coppie ordinate, teoricamente in sedici terne posso contenere tutte le 48 combinazioni. Questo è possibile ed infatti abbiamo un esempio di ciò.
Se due numeri non stanno nel primo gruppo allora stanno nel secondo quindi con 16+16=32 tentativi è possibile aprire la cassaforte.
Bene, fin qui ci siamo.
Se invece divido gli otto numeri diversamente, per esempio 3 e 5, l'assunto iniziale cade.
E quindi, cosa succede?