I ponti di Konigsberg

Giochini matematici elementari ma non olimpici.
Rispondi
Giuseppe R
Messaggi: 571
Iscritto il: 22 mar 2008, 12:04
Località: A casa sua

I ponti di Konigsberg

Messaggio da Giuseppe R » 30 lug 2009, 10:44

Dimostrare che il problema dei ponti di Konigsberg non ha soluzioni.

Per chi non lo sapesse, bisogna attraversare tutti i ponti una e una sola volta passando per tutte le zone dell'isola e tornando al punto di partenza.
http://it.wikipedia.org/wiki/File:7_bridges.svg

Mi chiedevo se c'è una soluzione che non riguarda la teoria dei grafi, ma non l'ho trovata. Voi che dite?
Esistono 10 tipi di persone: quelli che capiscono i numeri binari e quelli che non li capiscono.
"Il principio dei cassetti è quando hai n cassetti e n+1 piccioni: quindi ci sarà almeno un cassetto con 2 o più piccioni..." cit.

Avatar utente
Ani-sama
Messaggi: 418
Iscritto il: 19 feb 2006, 21:38
Località: Hasselt
Contatta:

Messaggio da Ani-sama » 30 lug 2009, 11:06

Onestamente mi stupirebbe una soluzione che non passasse per la teoria dei grafi, ma per il semplice fatto che non mi viene in mente proprio nessun altro framework nel quale impostare il problema... può darsi che sia ignoranza mia, comunque!

La soluzione che fa uso della teoria dei grafi, in ogni caso, è una conseguenza diretta delle più basilari proprietà dei grafi euleriani. :)
...

Avatar utente
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 30 lug 2009, 12:56

Non appena dai al problema un senso matematico, ovvero lo modellizzi nei modi più ovvi, lo riduci ad un problema su grafi o qualcosa di banalmente equivalente.
Inoltre, essendo un problema per sua natura finito, nel senso che per la sua soluzione sufficie l'esame di un numero finito (e piuttosto piccolo) di elementi, non è necessario ricondurlo al teorema di Eulero, o altre cose molto generali.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 30 lug 2009, 13:07

Ani-sama, sarà anche vero che ogni soluzione passa per la teoria dei grafi, ma la soluzione la si può spiegare anche ad un beduino che di matematica non sa niente...

Ci sono quattro isole. Escluse la partenza e l'arrivo, restano almeno due isole, consideriamone una. La prima volta che ci passo, ci entro camminando per un ponte. Poi dovrò uscire per un altro ponte. C'è un terzo ponte da percorrere che dà su quell'isola, però dopo che ci sono entrato, non potrò più uscire, perchè ora ho già usato tutti i ponti! Ma quell'isola l'ho scelta in modo che non fosse la fine del mio percorso! Quindi fare il percorso completo è impossibile.

Rispondi