37. Giochi del 28 marzo 2022 – Kaliningrad e le passeggiate di Eulero

I giochi del Lunedì di Prisma del 28 marzo 2022 a cura di Fabio Ciuffoli

Kaliningrad è oggi una exclave Russa, situata in posizione strategica sul Mar Baltico, tra Polonia e Lituania. Königsberg, questo era il nome dell’antica città della Prussia Orientale, è legata alla storia della matematica per il “Problema dei Sette Ponti” che, nel Settecento, ispirò Eulero per una prima formulazione della Teoria dei Grafi. Oggi proponiamo cinque giochi sulla Teoria dei Grafi. Invitiamo i lettori a presentarci osservazioni e proposte di soluzione nello spazio riservato ai commenti. Domani alle ore 17.00 pubblicheremo le soluzioni con dimostrazione.

Kaliningrad e le passeggiate di Eulero

1. I sette ponti. Il fiume Pregel, che attraversa la città di Königsberg, crea due isole unite alla terraferma per mezzo di sei ponti, mentre un ponte unisce tra loro le due isole, come illustrato in figura. Il problema, che ha stimolato la curiosità degli abitanti durante le passeggiate domenicali, riguarda proprio i suoi sette ponti.È possibile trovare un percorso a piedi per la città in modo da attraversare una e una sola volta tutti e sette i ponti?

2. La busta da lettera. Sapreste disegnare il grafo qui sotto, senza mai staccare la penna dal foglio e percorrendo ogni segmento una sola volta?

3. Il rettangolo con le diagonali. È possibile disegnare un rettangolo e le sue diagonali con un solo tratto di penna percorrendo tutti i segmenti ciascuno una sola volta? (È possibile passare più volte sugli incroci.)

4. Variazioni sui grafi. È possibile disegnare le seguenti figure senza mai staccare la penna dal foglio e senza ripassare su una linea già tracciata? (È possibile passare più volte sugli incroci.)

5. Tre dimensioni: colorare gli spigoli di un ottaedro. È possibile colorare tutti gli spigoli di un ottaedro con un pennarello rosso senza mai staccare la punta e senza ripassare su uno spigolo già colorato? Quale percorso deve seguire la punta del pennarello? (È possibile passare più volte sui vertici.)

Aggiornamento per le soluiozni click qui

I cinque problemi sono diffusamente presenti sul web. Abbiamo tratto la grafica e parte del testo dall’ottimo sito Base Cinque Appunti di Matematica Ricreativa.