Batterie scariche

Con un problema di questo tipo la prima cosa che viene in mente di provare è dividere le pile in gruppetti e provarle in questo modo. Numeriamo le pile 12345678 e dividiamole in quattro gruppi: 12, 34, 56, 78. Se il walkie-talkie non si accende mai vuol dire che una pila per gruppo funziona e l'altra no; scegliamo due gruppi, per esempio i primi due, e proviamo tutte le combinazioni 13, 14, 23, 24. Una di queste deve per forza essere quella con entrambe le pile funzionanti; quindi servono al più otto tentativi.
Che succede se proviamo a dividere le pile in due gruppi di quattro? Preso un gruppo si fanno i sei test possibili 12, 13, 14, 23, 24, 34. Se il walkie-talkie non si accende, i casi sono due: o avevamo preso tutte le pile non funzionanti, e quindi basta prenderne due delle altre, oppure nel gruppo c'è una sola pila funzionante; se siamo sfortunati e la coppia 56 non accende il walkie-talkie, sicuramente lo farà la coppia 78. Di nuovo abbiamo al massimo otto tentativi.
Ma nessuno ci obbliga a dividere le pile in gruppi uguali! Dividiamo le pile come 123, 456, 78 e testiamo i sei casi con i primi due gruppi: 12, 13, 23, 45, 46, 56. Se il walkie-talkie non si accende, ciascun gruppo ha almeno due pile che non funzionano; ma le pile non funzionanti sono quattro, quindi i gruppi hanno esattamente due pile non funzionanti e le pile 78 accenderanno il walkie-talkie. Bastano insomma sette tentativi

Un'ultima parola

Ci si può chiedere se si può fare di meglio. La risposta è negativa: lo si può dimostrare con la teoria dei grafi. Questa dimostrazione è di Bogumił Kamiński. Indichiamo le pile come vertici di un grafo e i test con un arco che connette due pile; dimostriamo per assurdo che se ci sono sei archi è sempre possibile trovare un sottografo con quattro vertici senza nessun arco tra due di essi. Supponiamo che ci sia al massimo un insieme di tre vertici 123 senza nessun arco tra di loro. Ciascuno dei vertici da 4 a 8 deve essere pertanto connesso a uno di quei tre vertici; abbiamo così usato cinque dei sei archi a disposizione e ce ne rimane solo uno. Esso non può connettere uno dei vertici da 4 a 8 a uno di quelli da 1 a 3, perché altrimenti i cinque vertici da 4 a 8 formerebbero un sottografo senza alcun arco. Ma se l'arco connette per esempio 4 con 5, il quartetto 5678 non avrà comunque archi che connettono due suoi vertici, contro l'ipotesi di partenza.