Come semplificare un problema matematico
Sto leggendo The puzzler’s dilemma. Tra i problemi che Derrick Niederman presenta che n’è uno tratto dalla William Lowell Putnam Examination del 1978:
Scegliete 20 numeri dall’insieme {1, 4, 7, … 97, 100}. Mostrate che ce ne devono essere due distinti la cui somma è 104.
Niederman passa a raccontare come risolvere il problema: se volete provarci da soli, smettete di leggere e prendete carta e penna. Sappiate però che secondo Niederman chi ha preparato il problema, in un raro momento di generosità, ha lasciato un numero in più nell’insieme: anche se ne scegliamo solo 19 è sempre possibile trovarne due distinti la cui somma è 104. Il punto è che secondo me la sua dimostrazione si può semplificare, pur rimanendo con la stessa struttura, e penso che possa essere interessante vedere come si può trattare un problema del genere.
Chi ha un po’ di esperienza di questo tipo di problemi ha immediatamente pensato che la soluzione si otterrà probabilmente per mezzo del principio dei cassetti. Se non ne avete mai sentito parlare, è quello che afferma che se ho quattro cassetti e ci voglio mettere dentro cinque maglioni ci sarà almeno un cassetto con due maglioni. Notate che non è detto che tutti i cassetti debbano avere almeno un maglione: ma anche se ce l’avessero resterebbe sempre l’ultimo cassetto. E in effetti la dimostrazione si fa così. Ma quello che ho trovato interessante è appunto semplificare il problema iniziale per arrivare più in fretta alla soluzione.
Come prima cosa, togliamo un’unità a tutti gli elementi dell’insieme. Una qualunque coppia avrà dunque due unità in meno: il problema diventa dunque “Scegliete 20 numeri dall’insieme {0, 3, 6, … 96, 99}. Mostrate che ce ne devono essere due distinti la cui somma è 102.” Ora tutti i numeri presenti sono multipli di tre; possiamo dunque dividerli per 3 e arrivare a “Scegliete 20 numeri dall’insieme {0, 1, 2, … 32, 33}. Mostrate che ce ne devono essere due distinti la cui somma è 34.” A questo punto dovrebbe semplice accorgerci che possiamo usare il trucco del piccolo Gauss: mettendo da parte 0 e 17, possiamo accoppiare gli altri come {1,33}, {2,32}, … {16,18}. Abbiamo dunque sedici coppie da cui possiamo scegliere al massimo un elemento, altrimenti abbiamo una somma pari a 34, e due elementi spaiati. Il principio dei cassetti ci dice che al diciannovesimo elemento al massimo avremo per forza due numeri la cui somma è 34.
C’è una differenza nel risolvere il problema semplificato rispetto a quello originale? Tecnicamente no. Possiamo mettere da parte 1 e 52, unire assieme {4,100}, {7,97}, … {49,55}, e fare esattamente lo stesso ragionamento. Però – almeno dal mio punto di vista – la formulazione modificata è più facile da “vedere”. Se consideriamo il fatto che molti problemi matematici dati alle competizioni sono dei travestimenti di altri problemi, direi che imparare a vedere se e come si può cambiare la formulazione di un problema paga spesso…
Leave a comment