Ieri Youtube mi ha presentato un problema di Google: mi era già capitato in passato di farne uno ma mi era sembrato decisamente più facile. Per risolvere questo invece mi sono dovuto impegnare e, bo, credo mi ci siano volute sulle due ore: non credo che mi sarebbe riuscito risolverlo a un colloquio…
In realtà non sono neppure sicuro di averlo risolto perché non ho guardato il video e non saprei (forse) neppure ritrovarlo perché non è nella cronologia (per quanto con chiavi “google problem seesaw” dovrebbe apparire!).
Il problema è molto semplice: abbiamo 12 persone di cui 11 hanno esattamente lo stesso peso mentre 1 è più pesante o più leggera. Abbiamo a nostra disposizione un “
seesaw” (non so come tradurlo: è quella specie di rozza altalena costituita da un palo con un perno nel mezzo e con i bambini che si siedono alle due estremità e si spingono in aria con le gambe. È insomma una specie di bilancia che confronta due pesi indicando se sono uguali o se uno è più pesante dell’altro) col quale possiamo fare solo 3 pesate.
Il nostro compito è quello di individuare l’individuo dal peso diverso…
Molto tempo l’ho perso pensando a soluzione esotiche: per esempio disponendo le varie persone non all’estremità della leva ma anche a metà e a un terzo, per moltiplicare i pesi e cercare così di ottenere più informazioni da ogni pesata. Ma, pur senza esserne sicuro, credo adesso che fosse un vicolo cieco.
Poi c’è il problema della pesatura iniziale: intuitivamente mi sembrava che per ottenere più informazioni fosse conveniente pesare sempre il maggior numero di persone. Però ci si rende subito conto che pesare 6 persone con 6 persone non ci dice praticamente niente: semplicemente l’altalena (che da adesso chiamerò bilancia perché mi sono abituato a pensarla tale!) penderà da un lato: e allora? Poi provai con 5 persone con 5 persone, escludendone 2…
Poi provai a semplificare il problema facendo finta di sapere che la persona dal peso diverso fosse più pesante.
Però alla fine mi sono convinto che la pesata iniziale, che ci dà più informazioni è quella in cui si dividono le persone in 3 gruppi da 4. 2 vengono confrontati fra loro mentre gli altri 4 restano in “riserva”.
Sul mio quadernino mi sono inventato tutta una simbologia per indicare in maniera chiara e inequivocabile i vari passaggi e poterci così ragionare sopra con più facilità. Qui cercherò di fare qualcosa di analogo e, anzi, di arricchirla…
Pesata 1: Metto 4 elementi sul piatto sinistro, 4 elementi sul destro e 4 non li peso. Al di là delle simmetrie (per semplicità qui e di seguito non ho riproposto le varie simmetrie) ci sono due casi.
a. [4=] ▲ [4=] : [4≈]
b. (4=) <▲> (4≈) : [4=]
Caso a:
a. [4=] ▲ [4=] : [4≈]
Inanzi tutto lasciatemi spiegare la simbologia usata. Le parentesi quadre [] indicano che il loro contenuto è certo. Il triangolo da solo indica che la bilancia è in equilibrio. I numeri indicano il numero di persone. L’uguale indica che sono persone dallo stesso peso il simbolo di “simile”, ≈, dice invece che fra queste c’è la persona dal peso diverso. I due punti sono solo un separatore per distinguere gli elementi significativi non pesati.
In questo caso la bilancia è in equilibrio quindi ho la sicurezza (parentesi quadre) che le 8 persone complessivamente sulla bilancia hanno lo stesso peso e che quella dal peso diverso è nel gruppo delle 4 non pesate.
Pesata 2: dai 4 elementi precedentemente non pesati ne prendo 2 che confronto con 2 che so essere normali. Anche qui ci sono due possibilità.
aa. (2=) ▲ [2=] : (2≈)
ab. (2≈) <▲> [2=] : [2=]
Caso aa: la mia simbologia qui non è accuratissima: ho introdotto le parentesi tonde per distinguere gli elementi che provenivano dal gruppo “incerto” mentre se avessi usato la logica precedente avrei dovuto usare anche qui le parentesi quadre (*1).
Di nuovo la bilancia è in equilibrio quindi l’elemento anomalo è fra i due ancora non pesati…
Pesata 3: prendo 1 dei due elementi ancora non pesati e lo confronto con uno normale. Ci sono altri due casi.
aaa. (1=)▲ [1=] : (1±)
aab. (1±) <▲> [1=] : (1=)
Nel caso aaa la bilancia è in equilibrio questo significa che l’elemento dal peso anomalo è quello che non è mai stato pesato!
Nel caso aab la bilancia pende da un lato è significa che l’elemento sul piatto è quello dal peso anomalo mentre quello mai pesato è uguale agli altri. Nel caso aab la bilancia può pendere sia a sinistra che a destra: nel primo caso l’elemento anomalo sarà più pesante del normale, nel secondo più leggero. Queste banali simmetrie per semplicità non starò a distinguerle…
Caso ab: in questo caso la bilancia non è in equilibrio quindi l’elemento speciale è fra i due sul piatto sinistro.
Pesata 3: per individuare quale dei due elementi è quello anomalo procedo come nel caso precedente.
Caso b.
b. (4=) <▲> (4≈) : [4=]
Questo è il caso più complicato. Di sicuro so che i 4 elementi non pesati sono normali ma non so in quale dei due gruppi da 4 sulla bilancia sia l’elemento speciale: io l’ho indicato sul piatto destro ma in realtà non lo sappiamo.
Pesata 2: 1. dai due piatti estraggo 3 elementi: 2 da un piatto e 1 dall’altro; 2. l’elemento rimasto lo scambio con uno dei 4 dell’altro piatto; 3. aggiungo 3 elementi uguali dai 4 che so essere uguali fra loro in maniera da avere 4 elementi su ogni piatto della bilancia. Ottengo i seguenti casi.
ba. (2=)+(1=)+[1=] ▲ (1=)+[3=] : (3≈)
bb. (2≈)+(1=)+[1=] <▲> (1=)+[3=] : (3=)
Caso ba.
Siccome i piatti della bilancia sono in equilibrio so che l’elemento anomalo è fra i 3 non pesati la seconda volta (di questi due provengono da un piatto e uno dall’altro).
Pesata 3: su un piatto della bilancia metto due elementi: uno dei due tolti da un piatto precedentemente e il secondo dall’altro e li confronto con due elementi uguali.
baa. (1=)+(1=) ▲ [2=] : (1±)
bab. (1±)+(1=) <▲> [2=] : (1=)
Il caso baa è banale: semplicemente l’elemento anomalo è il terzo non pesato.
Il caso bab è il più complicato: l’elemento anomalo è uno dei due sul piatto sinistro (nella mia formula: avremmo potuto fare tutto simmetricamente), ma quale?
In questo caso uno dei due elementi è rimasto nel piatto originario della prima pesata (b. (4=) <▲> (4≈) : [4=]) mentre l’altro si è spostato da un piatto all’altro. A questo punto dobbiamo verificare se l’inclinazione della bilancia è cambiata o se è rimasta la stessa. Se è rimasta la stessa allora significa che l’elemento incerto che abbiamo spostato era normale e quello speciale e quindi l’altro; se la pendenza della bilancia si è invertita allora significa che l’elemento anomalo è quello che si è spostato da un piatto all’altro.
Caso bb.
bb. (2≈)+(1=)+[1=] <▲> (1=)+[3=] : (3=)
I piatti non sono in equilibrio e quindi l’elemento anomalo può essere essere uno dei tre incerti su un piatto oppure l’incerto sull’altro: di nuovo qui la mia simbologia è carente perché mostra l’elemento incerto su un solo piatto (quello a sinistra).
Qui, di nuovo dobbiamo considerare, se l’inclinazione della bilancia o è rimasta costante rispetto alla pesata iniziale.
1. Se l’inclinazione è cambiata allora significa che l’elemento anomalo è uno dei due che ha cambiato piatto. In questo caso con la Pesata 3 pesiamo uno di questi con un elemento normale: se la bilancia è in equilibrio l’elemento anomalo è quello non pesato altrimenti sarà quello sulla bilancia. Nella mia notazione:
(1=) ▲[1=] : (1±)
oppure
(1±) <▲>[1=] : (1=)
2. Se l’inclinazione non è cambiata allora significa che l’elemento anomalo è fra i due incerti che non hanno cambiato posizione (indicati nella formula con (2≈) sul piatto a sinistra). Per individuare quale dei due è quello anomalo si procede come sopra.
Conclusione: quasi quasi vado a vedere qual è la soluzione proposta nel video. Probabilmente avrei potuto forse ottimizzare i casi a. cercando di scambiare fra un piatto e l’altro parte dei vari elementi in maniera da ottenere informazioni anche dall’eventuale cambiamento d’inclinazione della bilancia: ma comunque non ce ne era bisogno dato che comunque bastano 3 pesate...
PS: per curiosità aggiungo la foto della soluzione originale sul mio quadernino!
Come al solito tendo a essere più sintetico quando ragiono per conto mio...
Nota (*1): diciamo che queste simbologie me le invento per me e non per gli altri: automaticamente tengo traccia delle varie eccezioni che mi invento via via che mi rendo conto che mi servano...
Modificato (14/10/2023): Rileggendo mi sono accorto di un errore alla pesata 2 del caso b. Ora non ho voglia di ricoreggere il tutto ma sono convinto di poterci riuscire e che il metodo sia fondamentalmente corretto...
Modificato 14/10/2023: Come “promesso” nell’intervallo di Italia-Malta ho rimesso le mani sul problema: ormai il metodo l’avevo capito ma avevo “impastrocchiato” la seconda pesata del caso b. E da qui riparto…
Caso b.
b. (4=)s <▲> (4≈)d : [4=]
Questo è il caso più complicato. Di sicuro so che i 4 elementi non pesati sono normali ma non so in quale dei due gruppi da 4 sulla bilancia sia l’elemento speciale: io l’ho indicato sul piatto destro ma in realtà non lo sappiamo. Ho aggiunto “s” per “sinistra” e “d” per “destra” in maniera da poter distingure con maggior facilità alla prossima pesata da dove derivano i vari elementi...
Pesata 2: Qui si deve essere astuti: 1. Rimuovo tre elementi incerti, 2 da un piatto e 1 dall’altro; 2. scambio due elementi dal piatto sinistro al destro e viceversa; 3. aggiungo un elemento uguale al piatto rimasto con due soli elementi.
La formula della seconda pesata è questa:
(2=)s + (1=)d ▲ (1=)s + (1=)d + [1=] : (2=)d + (1=)s
La bilancia potrà andare in equilibrio, rimanere sbilanciata com’è oppure invertire il proprio sbilanciamento. Avremo quindi i seguenti 3 casi:
ba. (2=)s + (1=)d ▲ (1=)s + (1=)d + [1=] : (2≈)d + (1≈)s
bb. (2≈)s + (1=)d <▲> (1=)s + (1≈)d + [1=] : (2=)d + (1=)s
bc. (2=)s + (1≈)d <▲> (1≈)s + (1=)d + [1=] : (2=)d + (1=)s
Caso ba.
ba. (2=)s + (1=)d ▲ (1=)s + (1=)d + [1=] : (2≈)d + (1≈)s
I piatti adesso sono in equilibrio quindi l’elemento anomalo deve essere fra i 3 non pesati.
Pesata 3: su un piatto metto un elemento del piatto destro e uno del sinistro, sull’altro due elementi che sappiamo uguali. Ovvero:
(1=)s+(1=)d ▲ [2=] : (1=)d
Qui abbiamo ora due casi:
baa. (1=)s+(1=)d ▲ [2=] : (1±)d
bab. (1≈)s+(1≈)d <▲> [2=] : (1=)d
Nel caso baa l’elemento anomalo sarà banalmente quello non pesato.
Nel caso bab l’elemento anomalo sarà uno dei due sul piatto sinistro (nella mia formula: come al solito non sto a presentare tutte le simmetrie possibili). Per capire quale si deve osservare se il piatto sbilanciato rimane invariato o si inverte (rispetto alla prima pesata): nel primo caso l’elemento anomalo sarà quello che non si è spostato (nell’esempio (1≈)s) altrimenti l’altro (ovvero (1≈)d).
Caso bb.
bb. (2≈)s + (1=)d <▲> (1=)s + (1≈)d + [1=] : (2=)d + (1=)s
Siamo nel caso in cui la bilancia non è in equilibrio ma i piatti sono rimasti al loro posto (non si sono cioè invertiti). Questo significa che l’elemento anomalo deve essere fra quelli che non sono stati spostati rispetto alla prima pesata. Abbiamo quindi un’incertezza fra tre elementi: due originari di un piatto e il terzo dell’altro.
Pesata 3: è identica a quella del caso precedente (vabbè abbiamo (2=)s + (1=)d invece che (2=)d + (1=)s ma il meccanismo non cambia) visto qui sopra.
Caso bc.
bc. (2=)s + (1≈)d <▲> (1≈)s + (1=)d + [1=] : (2=)d + (1=)s
I piatti non sono in equilibrio ma si sono invertiti: questo significa che l’elemento anomalo si è spostato dal piatto sinistro a quello destro o viceversa.
Siccome sono solo due elementi basta confrontare uno di essi con un elemento normale.
Pesata 3:
(1=)s ▲ [1=] : (1=)d
Le possibilità sono due e banali:
bca. (1=)s ▲ [1=] : (1±)d
bcb. (1±)s <▲> [1=] : (1=)d
Nel caso bca l’elemento anomalo è quello non pesato (ovvero (1=)d).
Nel caso bcb l’elemento anomalo è quello pesato (ovvero (1=)s) e in questo caso sapremo anche se è più leggero o pesante di un elemento normale...
Ripropongo alla correzione sul mio quadernino:
Come ho già scritto qualche giorno fa recentemente mi sono completamente bloccato nelle mie letture. Non sono a casa e nell’ambiente rumoroso di città fatico ad ambientarmi: per leggere certi libri ho bisogno di molta concentrazione e il continuo rumore del traffico con l’immancabile motorino su di giri mi distraggono.
