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]

"axpgn":Se invece divido gli otto numeri diversamente, per esempio 3 e 5, l'assunto iniziale cade.

Perché cadrebbe?
Per esempio considerando i due gruppi ${1,2,3,4,5}$ e ${6,7,8}$, anche in questo caso almeno due tra $A$, $B$ e $C$ ricadranno nello stesso gruppo. Quello che cambia è il numero di terne da provare, che in questa circostanza sarebbero $5^2+3^2=34$.

[axpgn]

Vero.

Andiamo avanti ...

Con questo metodo si dimostra che bastano 32 tentativi.
Perché dovrebbe essere il minimo?

Ma assumiamo pure che sia il minimo per QUESTO metodo; mancherebbe ancora la dimostrazione che sia il minimo in assoluto ovvero che non esistano altre strategie risolutive che impieghino meno tentativi.

Che ne pensi?

[utente__medio11]

"axpgn":Perché dovrebbe essere il minimo?

Perché la seguente formula

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

che racchiude tutti i casi possibili, ossia quelli relativi a $m=1,2$, restituisce appunto $32$.

"axpgn":Ma assumiamo pure che sia il minimo per QUESTO metodo; mancherebbe ancora la dimostrazione che sia il minimo in assoluto ovvero che non esistano altre strategie risolutive che impieghino meno tentativi.

Che ne pensi?

Alla fine il problema consiste nell'individuazione delle coppie ordinate $AB$, $BC$ e $AC$, e la suddetta strategia basata sulle disposizioni con ripetizione $D'_(n,2)$ (racchiuse nelle tre possibili "posizioni" in altrettante terne) rappresenta da questo punto di vista un limite invalicabile, nel senso che l'elenco dei casi possibili è quello, e di sicuro non si può fare di meglio.
Visto poi che $A$, $B$ e $C$ possono assumere qualsiasi valore da $1$ a $8$, le terne da provare devono comunque contenere tutti i valori ${1,2,3,4,5,6,7,8}$, e l'unico margine di azione, l'unico elemento di variabilità che possiamo introdurre, è quello di non considerare i valori tutti insieme, ed è qui che subentra il numero di gruppi $m$ (di cui peraltro sono stati discussi tutti i possibili valori $>0$ da esso assumibili).

[Studente Anonimo]

"axpgn":Vero.

Andiamo avanti ...

Con questo metodo si dimostra che bastano 32 tentativi.
Perché dovrebbe essere il minimo?

Ma assumiamo pure che sia il minimo per QUESTO metodo; mancherebbe ancora la dimostrazione che sia il minimo in assoluto ovvero che non esistano altre strategie risolutive che impieghino meno tentativi.

Che ne pensi?

Perché...

...stai partizionando \(n\) in due parti \(n_1\) e \(n_2\) (i.e. le due cardinalità di \( n_1= \left| \{1,\ldots,k_1\} \right| \) e \(n_2=\left| \{k_1 +1,\ldots ,n \} \right| \) ) e in modo tale che \(n_1^2 + n_2^2 \) sia minimale, ovvero l'ipotenusa su un triangolo rettangolo di cateti di lunghezza \(n_1\) e \(n_2\) è minimale, i.e. di ipotenusa \( \sqrt{ \left \lceil \frac{n^2}{2} \right \rceil } \).

Non si può far di meglio per il seguente motivo. Considera un reticolo cubico \(C_n\) con \( n^3 \) vertici in \( \mathbb{Z}^3\). Ora considera \(D_n \subseteq C_n \) essere un sottoinsieme di vertici del reticolo \(C_n\) tale che per ogni punto del reticolo \((a,b,c) \in C_n\) esiste \( (x,y,z) \in D_n \) tale che \( (x,y,z) \) e \( (a,b,c) \) differiscono di al più una coordinata. In altre parole abbiamo che \( (a,b,c) \) sta su almeno uno delle seguenti rette: \( (\cdot, y,z), (x,\cdot, z) , (x,y,\cdot) \). Un insieme con questa proprietà diciamo che è un insieme retta-dominante per \(C_n\). E' chiaro che l'insieme (o gli insiemi) \(D_n\) retta-dominante con cardinalità minimale corrisponde al nostro minimo. Per ogni insieme retta-dominante \( D_n \) di cardinalità minimale abbiamo che esiste una partizione \( \{1,\ldots,n\} = A_1 \cup A_2 \), con \(A_1 \cap A_2 = \emptyset \), e tale che \( n_1^2 + n_2^2 = \left| D_n \right| \), dove \( n_1 = \left|A_1 \right| \) e \( n_2 = \left| A_2 \right| \).
Wlog consideriamo la proiezione \( \pi_z\), dimenticando la coordinata \(z\), sul piano \(Oxy\) (se quanto segue non vale per \(Oxy\) allora vale per \(Oxz\) con \( \pi_y\) oppure per \(Oyz\) con \(\pi_x\)).

siccome \(D_n\) è un insieme retta-dominante abbiamo che esiste una partizione \( \{1,\ldots,n\} = A_1 \cup A_2\) con \( A_1 \cap A_2 = \emptyset \) tale che \( \pi_z( D_n) = A_1 \times A_1 \cup A_2 \times A_2 \) e poiché è di cardinalità minimale risulta che che ogni fibra (non vuota) contiene un solo punto (i.e. per ogni \((x,y) \in \pi_z(D_n) \) abbiamo che \( \pi_z^{-1}(x,y) \) è un insieme di un solo punto). Questo dimostra che se \(D_n\) è di cardinalità minimale abbiamo che \(n_1^2 + n_2^2 = \left| D_n \right| \) e questo implica che \( \left| D_n \right| = \left \lceil \frac{n^2}{2} \right \rceil \).

Edit: Esempio

Prendiamo \(n=3\). Consideriamo \(D_3=\{ (1,1,1),(3,3,1),(2,2,2),(3,1,3),(1,3,3) \} \). Possiamo considerare qualunque proiezione \( \pi_z, \pi_x, \pi_y \) e otteniamo che \( \pi(D_3)= \{ 1,3\} \times \{1,3\} \cup \{2 \} \times \{2\} \). Se invece considerassimo \(D_3=\{ (2,2,1),(1,1,2),(3,3,2),(3,1,3),(1,3,3) \} \). Allora non potremmo usare le proiezioni \( \pi_x\) e \( \pi_y\) ma soltanto \( \pi_z\) e otterremmo comunque che \( \pi_z(D_3)=\{ 1,3\} \times \{1,3\} \cup \{2 \} \times \{2\} \). Inoltre ogni fibra chiaramente contiene un solo punto.


Prendiamo \(n=4\). Consideriamo \( D_4 = \{ (2,2,1),(3,3,1),(3,2,2),(2,3,2),(1,1,3),(4,4,3),(4,1,4),(1,4,4) \} \). Consideriamo la proiezione \[ \pi_z(D_4)= \{ (2,2),(3,3),(3,2),(2,3),(1,1),(4,4),(4,1),(1,4) \} = \{1,4\} \times \{1,4\} \cup \{2,3\} \times \{2,3\} \]
Inoltre per ogni punto nella proiezione abbiamo un solo punto nella fibra, ad esempio \( \pi_z^{-1}(1,1)=\{(1,1,3) \} \).

Prendiamo \(n=8\). Consideriamo \(D_8\) come nel esempio di utente_medio:

"utente__medio":$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

Allora \( \pi_z(D_8)= \{1,2,3,4\} \times \{1,2,3,4\} \cup \{5,6,7,8\} \times \{ 5,6,7,8\} \) e ogni fibra che contiene un solo punto

[axpgn]

Ok, grazie a tutti

La mia dimostrazione, più terra terra

Per stabilire che 32 è il minimo, dobbiamo dimostrare che, indipendentemente dai 31 tentativi che si possono fare, c'è almeno una combinazione (a, b, c) che è stata completamente persa.
A tal fine, teniamo traccia dei nostri tentativi in un tabella 8 x 8, inserendo il numero c della prova (a, b, c) nella cella con le coordinate (a, b), cioè nella riga A e nella colonna B.
Pertanto, se la cella nella riga 2 e nella colonna 5 contiene il numero 6, significa che uno dei nostri tentativi è stata la combinazione (2,5,6).
Supponiamo quindi di aver registrato 31 prove nella tabella, uno di questi casi accade.

* supponiamo che una riga o una colonna contenga esattamente due voci; per esempio, la riga 3 contenga solo 4 e 7 nelle colonne 2 e 5.
Ora, ognuna di queste 6 colonne non può avere 5 voci, perché ciò ne richiederebbe $6 * 5 = 30$ e ci sono solo altri 29; ne consegue, quindi, che una di queste colonne ne contiene solo 4.
Supponiamo che la colonna 7 contenga solo 8, 1, 3, 5.
Complessivamente, quindi, le voci della riga 3 e della colonna 7 rappresentano solo 6 degli 8 numeri (1,2,3,4,5,6, 7,8); il numero 6 (e 2) non ricorre in nessun punto della riga 3 o della colonna 7.
Pertanto, se la combinazione corretta è (3,7,6), il nostro procedimento l'avrebbe mancata completamente:
-- se avessimo provato una qualsiasi combinazione (3,7, c), allora il numero c sarebbe stato inserito nella cella (3, 7); ma la cella (3, 7) è vuota;
- se fosse stato provato uno qualsiasi (3, b, 6), allora 6 sarebbe stato inserito da qualche parte nella riga 3 (nella colonna B), ma non è così;
- se uno qualsiasi (a, 7, 6) fosse stato testato, allora 6 si sarebbe dovuto trovare da qualche parte nella colonna 7, cosa che non è.

** Supponiamo che la riga 1 contenga 3 voci nelle colonne 1, 2 e 3.
Se ognuna di queste colonne 1, 2, 3 dovesse contenere esattamente una o esattamente due voci, saremmo nel caso precedente.
Supponiamo, quindi, che ciascuna di queste colonne abbia almeno 3 voci, per un totale di almeno 9 voci in queste colonne nel loro complesso.
Le altre 5 colonne, quindi, non possono avere ciascuna fino a 5 voci, poiché in esse sono registrati solo 22 o meno entrate.
Quindi uno di queste altre colonne devono avere 4 o meno voci e la nostra conclusione segue come sopra.