Da qualche giorno è stato pubblicato sul portale del Ministero dell’Istruzione, dell’Università e della Ricerca un simulatore delle prove che i candidati dovranno sostenere nel prossimo concorso per professori.
Fra le varie domande, che spaziano dai quesiti di logica a quelli di ortografia, ce n’è una che ha solleticato maggiormente la mia curiosità.
Si tratta del non nuovissimo problema delle pesate; sostanzialmente nella cinquantina di test presenti sul sito, ognuno composto da 50 domande da risolvere in cinquanta minuti al massimo, viene riproposto puntualmente in ogni serie, ogni volta con un numero diverso di oggetti.
In cosa consiste il problema? La sua formulazione tipo è: date N palle, tutte indistinguibili ed uguali, a parte una più pesante delle altre, ed una bilancia a due piatti, quante pesate minime sono necessarie per individuare la palla più pesante?
Il problema è interessante perché è possibile generalizzare la soluzione rispetto al numero delle palle, e anche fare ulteriori osservazioni a margine.
Innanzitutto, come spesso si usa in matematica, iniziamo a considerare i casi “banali”:
per N=1, non c’è niente da pesare, quindi il numero di pesate è zero;
per N=2, chiaramente, è necessaria una pesata;
per N=3, inizia ad apparire la struttura di base dell’intero ragionamento, la cui dimostrazione sarà per induzione; mettiamo una palla su ciascun piatto e ne lasciamo una fuori: se la bilancia si inclinerà, abbiamo trovato la palla più pesante, altrimenti quella lasciata fuori sarà quella cercata; in sostanza, è necessaria una pesata;
per N=4, mettiamo due palle su ciascun piatto, uno dei due si inclinerà, scartiamo le palle dell’altro piatto e ricadiamo nel caso delle due palle già risolto; due pesate, dunque;
da N=5 a N=8 sono necessarie due pesate; la logica è una via di mezzo tra l’approccio di N=3 e N=4: metto due palle su ciascun piatto, se uno dei due si abbassa, ricado nel caso N=2 ed ho un’altra pesata da fare, altrimenti la palla più pesante sta nel gruppo non pesato di 1,2,3 palle a seconda che N sia uguale a 5,6,8, e ricado comunque in un caso per cui è necessaria una sola pesata;
Per N=9, attenzione: potrei (sbagliando strategia) disporre 4 palle su ciascun piatto, ma così facendo rischierei quasi sicuramente di fare 3 pesate, mentre ne sono sufficienti 2: faccio tre gruppi di palle da tre ciascuno, ne confronto due sulla bilancia, il terzo fuori: con una pesata isolo un gruppo da tre, e dunque ho bisogno di una sola ulteriore pesata per identificare la palla più pesante.
Per N=10, siamo costretti ad ammettere che non possiamo escludere che possano essere necessarie 3 pesate: purtroppo dovremo comunque suddividere le 10 palle in gruppi di cui uno superiore a 3 e dunque con un numero necessario di pesate maggiore di 2.
Se si aumenta il numero di gruppi di suddivisione per ridurre il numero di pesate necessarie per ogni gruppetto, il numero di pesate complessivo non tende a diminuire.
Riassumendo, abbiamo il seguente schema:
|
N |
Gruppo 1 |
Gruppo 2 |
Gruppo 3 |
Pesate |
|
1 |
1 |
0 |
0 |
0 |
|
2 |
1 |
1 |
0 |
1 |
|
3 |
1 |
1 |
1 |
1 |
|
4 |
2 |
1 |
1 |
2 |
|
5 |
2 |
2 |
1 |
2 |
|
6 |
2 |
2 |
2 |
2 |
|
7 |
3 |
2 |
2 |
2 |
|
8 |
3 |
3 |
2 |
2 |
|
9 |
3 |
3 |
3 |
2 |
|
10 |
4 |
3 |
3 |
3 |
Sembra dunque che il numero di pesate necessarie non aumenti di pari passo con il crescere del numero di palle. In termini matematici, le due grandezze non sono legate da una proporzionalità con andamento lineare.
Questa tabella può ulteriormente essere riassunta come:
|
Da N= |
A N= |
Pesate |
|
2 (30+1) |
3 (31) |
1 |
|
4 (31+1) |
9 (32) |
2 |
|
10 (32+1) |
? |
3 |
La casella con il segno “?” è a questo punto facilmente desumibile: è 33, cioè 27; fino a 27 palle sono necessarie al più 3 pesate per trovare quella più pesante; se intuitivamente ci pare poco credibile, non abbiamo altro da fare che effettuare delle prove, ma la matematica ci mette a disposizione degli strumenti molto più potenti come l’induzione: ipotizziamo dunque che per tutti gli interi fino ad N, con N > 3, per N palle di cui una più pesante delle altre, per individuare quest’ultima siano necessarie m pesate dove m è espresso come il numero che soddisfa la condizione: 3m-1+1 ≤ N ≤ 3m (se M = 3m , allora m=log3M ) e cerchiamo di dimostrare che sia vero che, per ogni M tale che 3m+1 ≤ M ≤ 3m+1 , siano sufficienti al più m+1 pesate. Ma questo è banalmente verificato se applichiamo lo stesso procedimento sopra descritto, ossia formiamo tre gruppi di palle, ognuno dei quali avrà un numero di elementi compreso tra 3m-1+1 e 3m , due dei quali con lo stesso numero, ossia [M/3], dove […] rappresenta la parte intera . Con la prima pesata dunque decideremo in quale gruppo è contenuta la palla più pesante e per quel gruppo vale che il numero di pesate necessario è al più m, e quindi in totale m+1 pesate.
Un fatto interessante è notare che questa struttura di “triplicità” è indotta dal fatto che le nostre bilance hanno due piatti, ma potremmo ipotizzare, anche solo idealmente, delle bilance a tre, quattro,…, P piatti, e a questo punto la regola diventa più genericamente che, data una bilancia a P piatti ed un insieme di N palle (con N ≥ P ≥ 2) di cui una più pesante delle altre, il numero di pesate m da effettuare per determinare quale sia la palla più pesante è dato dall’esponente tale che (P+1)m-1+1 ≤ N ≤ (P+1)m .
E se le palle più pesanti delle altre fossero due? E se fossero Q, con Q < [N/2] ?