ElectroYou

Molti si ricorderanno del famoso problema: data una bilancia a 2 piatti e 12 palline di cui una differente in peso, determinare con massimo 3 pesate qual è la pallina diversa e dire se è più pesante o più leggera delle altre.
Mi sono ora provato nella generalizzazione di questo problema, tentando di trovare la formula o il procedimento con cui, dato un numero di palline qualsiasi, purché maggiore di due, si possa determinare il numero minimo di pesate necessarie all'individuazione della pallina differente.
Il procedimento da me trovato, nella speranza che sia corretto, è stato derivato per via induttiva, ma sembra funzionare (un po' come il metodo delle frecce di riflessione di Feynman, spiegato nel suo libro "QED la strana teoria della luce e della materia", che, a suo dire, non si sa perché, ma funziona, e quindi vale la pena di usarlo).
Prima però di esporre il mio procedimento, penserei che potrebbe essere interessante per alcuni volersi cimentare in una soluzione e confrontarsi poi con me per verificare la correttezza o meno di quanto abbiamo indipendentemente trovato.
Grazie.

L’approccio da me seguito e proposto per la soluzione del problema è il seguente:

caso 1) Il numero minimo di pesate con 3 palline è 2.

caso 2) Da 4 palline fino a 12 il numero minimo di pesate è 3.

caso 3) Da 13 palline fino a 36 il numero minimo di pesate è 4.

caso 4) Da 37 palline fino a 108 il numero minimo di pesate è 5.

Si osservi che il numero massimo di palline in ciascun caso (ad esclusione dei primi due) è il triplo del precedente.
Questo è spiegabile col fatto che, parlando in modo generale, per l’ottimizzazione delle pesate nella soluzione di ciascun caso, il numero massimo di palline relativo a ciascun caso deve essere diviso, alla prima pesata, in 3 gruppi uguali dei quali due vanno posti sui piatti della bilancia, mentre il terzo viene tenuto a parte: aumentando infatti, di caso in caso, di 1 le pesate necessarie all'individuazione della pallina diversa, il gruppo di palline tenuto a parte deve ricadere nel caso precedente perché, qualora i piatti della bilancia, alla prima pesata, rimangano in equilibrio, l'individuazione della pallina differente in tale gruppo tenuto a parte possa essere effettuata con il numero minimo di pesate di pertinenza al suddetto caso precedente.
Ciascuno di questi valori massimi M di palline nei vari casi sopra elencati (escluso il primo) è esprimibile con:



dove x assume, nei casi esaminati escluso il primo, i valori da 1 a 3.

Per tali casi si ipotizza che il numero di pesate minimo P sia dato da: P = 2 + x (cioè dalla somma degli esponenti di 2 e di 3) o se si preferisce:



che può essere giustificata, per lo meno in modo intuitivo, come segue:


costituisce il numero minimo di pesate necessarie nel caso delle 3 palline; questo si giustifica col fatto che con la prima pesata, con la quale due palline sono poste sui piatti della bilancia mentre la terza è tenuta a parte, si determina quale può essere la pallina diversa dalle altre due, e con la seconda se è più pesante o più leggera.
Passando poi al caso 2 delle 12 palline, si avrà una prima suddivisione delle palline in 3 gruppi per riportarci ad una condizione approcciabile come al caso 1 precedente, e quindi risolvibile con lo steso numero minimo di pesate.
Lo stesso discorso vale anche per i casi successivi al secondo, per cui:


costituisce il numero di casi, a partire dal secondo fino a quello considerato, in cui le palline sono state, alla prima pesata di ogni caso, suddivise in 3 gruppi per riportarci alla situazione del caso precedente.

Applicando le formule precedenti al:

caso 5) Da 109 palline fino a 324 il numero minimo di pesate è 6.

Il risultato (con x = 4) è stato verificato come corretto.


Arrivando ora a fornire una soluzione generalizzata al problema, si ha che:

Assegnato un numero qualsiasi di palline Z, per ottenere il numero minimo di pesate P si deve determinare il valore:



e pertanto il relativo numero minimo di pesate sarà:



dove x è il primo intero >= 0 tale per cui M >= Z.

In generale M è il numero massimo di palline cui compete lo stesso numero P di Z.
In particolare per il caso delle 3 palline, in quanto esso stesso è da considerarsi un numero massimo M, si ha che, per x = 0, M = 4 > 3, per cui si ottiene P = 2 + 0 = 2.