Il problema dei ponti di Konigsberg – “È una mia vecchia massima che, quando si è escluso l’impossibile, ciò che rimane, per quanto improbabile, deve essere necessariamente la verità”. Con queste parole, il mitico Sherlock Holmes spiega il suo metodo deduttivo, metodo che assomiglia tanto ad una delle tecniche dimostrative più efficaci ed eleganti nelle mani di un matematico: la dimostrazione per assurdo.
Si tratta di una tecnica “indiretta” che consiste nel supporre falsa la proposizione che si vuole dimostrare e nel far vedere che ciò conduce ad una contraddizione. L’assurdo, a questo punto, è dipeso dalla negazione della tesi che, quindi, non può che essere vera.
Ad esempio, il grande Eulero, nel 1736, risolse il cosiddetto “problema dei ponti di Konigsberg” con un bellissimo ragionamento per assurdo. All’epoca Konigsberg era una città della Prussia orientale, divisa dal fiume Pregel in quattro parti collegate da sette ponti (si veda lo schema in figura).
Il problema che gli abitanti di Konigsberg si ponevano era il seguente: è possibile passeggiare per la città in modo da attraversare ogni ponte una e una sola volta? Senza prendere in esame tutti gli itinerari possibili (compito noiosissimo e poco elegante), Eulero dimostrò che la risposta al problema era negativa con una straordinaria “reductio ad absurdum”.
Supponiamo che una tale passeggiata esista davvero per cui partendo da una delle quattro regioni, A, B, C o D, giungiamo ad una di queste (magari la medesima) dopo aver attraversato una sola volta tutti e sette i ponti. Chiaramente ci sono almeno due regioni in cui la passeggiata non può né iniziare né terminare. Bene, prendetene una.
Dal momento che il numero di volte in cui ci arriviamo è uguale al numero di volte in cui la abbandoniamo e poiché attraversiamo ogni ponte una volta sola, ne consegue che il numero di ponti che conducono a tale regione deve essere necessariamente pari.
Ora se osservate la piantina di Konigsberg, vi accorgete che nessuna delle quattro regioni soddisfa questa proprietà: cinque ponti conducono all’isola A, tre ponti alle altre regioni B, C e D. Ergo, non è possibile fare questa particolare passeggiata.