Petita investigació sobre figures d’un sol traç
| Índex | ||
| Introducció | Practiquem | Es poden fer o no |
| El problema dels ponts | Problemes i cuirositats | Descarregar pdf |
| Introducció |
¿A qui no li han proposat alguna vegada repetir un dibuix amb la restricció de “no aixecar el llapis del paper i no repassar dues vegades per la mateixa línia”? Però, es pot dibuixar qualsevol figura amb aquestes condicions? Si no és així, com podem saber quines d’aquestes figures són possibles i quines no?
L’estrella de cinc puntes o pentagrama és una de les figures més conegudes que es poden dibuixar d’un sol traç. Fins i tot, la podem envoltar amb un pentàgon.
És important que, abans de començar a provar amb figures més complicades, fixem un sistema per anotar les solucions. Un dels molts possibles és marcar els punts d’inici i final i no superposar les línies en els vèrtexs de les figures perquè es vegi bé el recorregut.
| Practiquem una mica |
No hi ha res com començar a practicar per familiaritzar-se amb un problema. Aquí tens unes quantes figures que es poden dibuixar d’un sol traç.
| Es poden fer o no? |
Investiguem ara quines són les condicions perquè una figura es pugui fer d’un sol traç. Per fer-ho treballarem amb set figures senzilles diferents.
- Podràs obrir un formulari per a cadascuna de les figures.
- Respondrem les mateixes preguntes per a cada punt de la figura
- Primer hem de fixar-nos si la quantitat de línies que coincideixen en el punt és parell o senar. A continuació tens un exemple de recompte.
- La segona pregunta ens demana si la figura es pot fer d’un sol traç o no.
- La tercera demana, en cas que s’hagi pogut fer, a quin punt s’ha acabat.
- Després d’Enviar podràs comprovar les respostes.
- En conjunt es tracta d’omplir una taula com la següent.
| Figura | Punts | Línies | Es pot fer? | On s’acaba? |
 Enllaç al formulari |
A | 1 (senar) | Sí | A |
| B | ||||
| C | 2 (parell) | No | ——- | |
| D | ||||
 Enllaç al formulari |
A | |||
| B | ||||
| C | ||||
| D | ||||
| E | ||||
| A | ||||
| B | ||||
| C | ||||
| D | ||||
| E | ||||
 Enllaç al formulari |
A | |||
| B | ||||
| C | ||||
| D | ||||
 Enllaç al formulari |
A | |||
| B | ||||
| C | ||||
| D | ||||
| E | ||||
 Enllaç al formulari |
A | |||
| B | ||||
| C | ||||
| D | ||||
| E | ||||
 Enllaç al formulari |
A | |||
| B | ||||
| C | ||||
| D | ||||
| E | ||||
| F |
Quan hagis estudiat les set figures pots veure en aquest enllaç una taula resum per poder extreure’n conclusions sobre quines condicions ha de complir la figura perquè es pugui dibuixar d’un sol traç.
En general, es pot observar que:
- Si tots els punts de les figures són parells (hi arriben dues, quatre, sis… línies) sempre es pot fer la figura d’un sol traç. Es comença i s’acaba al mateix punt. És indiferent per quin punt comencem.
- Si hi ha dos i només dos punts senars, la figura es pot traçar de forma contínua. S’ha de començar per un dels punts senars i acabarem a l’altre.
- Si hi ha més de dos punts senars, la figura no es pot fer d’un sol traç.
Si vols pots aplicar aquestes conclusions a noves figures per saber si són possibles de dibuixar o no.
Enllaç al formulari sobre aquestes figures
| El problema dels ponts de Köningsberg |
La ciutat de Köningsberg (l’actual Kaliningrad a Rússia) està travessada pel riu Pregel que l’illa Kneiphof divideix en dues branques. Al segle XVIII hi havia set ponts que connectaven les dues ribes amb les illes existents al riu. S’explica que els seus habitants intentaven, sense gaire èxit, trobar un itinerari de passejada que passés una sola vegada per cada pont.
Els habitants de Köninsberg van tenir la sort que l’any 1736 un dels seus habitants més il·lustres, el matemàtic suís Leonhard Euler, s’interessés pel problema dels ponts i iniciés una investigació com la que has pogut fer abans sobre les figures d’un sol traç. Si vols pots intentar buscar l’itinerari.
Leonhard Euler va transformar el mapa del riu i els ponts en una figura més senzilla (que anomenem graf) on cada punt representava un tros de terra (riba o illa) i cada línia un pont.
Si la figura obtinguda es podia dibuixar d’un sol traç el recorregut seria possible. En cas contrari no. Euler va investigar i demostrar les condicions perquè una figura es pugui dibuixar o no, i va veure que el cas dels ponts de Köningsberg no tenia solució perquè hi havia més de dos punts senars.
El raonament que va fer va ser, més o menys, el següent:
- A les figures que dibuixem hi ha uns punts en què coincideixen diferents línies (una, dues, tres, quatre, etc.)
- Per dibuixar una figura d’un sol traç a cada punt d’encreuament haurem de poder arribar i també haurem de poder marxar. Això ho haurem de fer les vegades que siguin necessàries: si hi ha 2 línies una vegada (arribar-marxar), si n’hi ha 4 línies dues vegades (arribar-marxar i arribar-marxar), si n’hi ha 6 línies, tres vegades. És important, doncs, que a cada punt hi arribi un nombre parell de línies.
- En conseqüència, si una figura té tots els punts parells es podrà dibuixar sempre d’un sol traç. Podrem començar a qualsevol punt i acabarem, per força, al mateix punt en què hem iniciat el dibuix. Ho podem veure en aquesta animació.
- Si una figura té 2 punts senars també es podrà fer. Una de les línies que “sobra” servirà per iniciar el dibuix (no caldrà “tornar”) i l’altre per acabar-lo (no caldrà “sortir”). Obligatòriament, el punt per iniciar la figura ha de ser un dels senars i l’altre serà el punt final. Podem veure un exemple en aquesta animació.
- Si una figura té més de 2 punts senars serà impossible dibuixar-la d’un sol traç. En algun moment “arribarem” a un punt i no podrem sortir.
- La figura corresponent als ponts de Köningsberg pertany a aquest darrer model: té més de dos punts senars i no es pot dibuixar d’un sol traç: la passejada en les condicions demanades és impossible.
| Problemes i curiositats |
Més figures d’un sol traç
Aquí tens una col·lecció de figures força interessant que es poden dibuixar d’un sol traç.
Curiositats
- Una solució al problema dels ponts de Köningsberg
Si tenim prou energia i paciència és possible resoldre el problema dels ponts de Köningsberg. Només cal que remuntem el riu fins el naixement. D’aquesta manera “convertim” les dues ribes en una de sola i la paritat i senaritat de cada zona de terra varia fent possible la passejada.
- Una altra solució al problema dels ponts
Totes les ciutats del món pateixen grans canvis al llarg de la seva història. Köningsberg, actualment Kaliningrad, també els ha sofert. No sabem si a causa dels bombardejos de la 2a Guerra Mundial o per causa del problema matemàtic que l’ha fet tan famosa, el cas és que ara el plànol és ben diferent i s’ha reduït a 5 la quantitat de ponts.
Ara, que ha canviat el graf, el recorregut passant per tots els ponts sí que és possible.
- La cançó dels ponts
Amb la manera d’abordar el problema dels ponts de Köningsberg Euler va inaugurar una nova i important branca de la matemàtica coneguda com a Teoria de Grafs. Per “commemorar-ho” Bohdan Zelinka (text) i Zdenek Ryjacek (música) van crear aquest “Himne a la Teoria de Grafs” que donem aquí en la seva versió anglesa deguda a Donald A. Preece.
En aquesta adreça podreu accedir a un arxiu d’àudio (en txec) i a un vídeo (sense so) en el que es veu als esforçats intèrprets.
La traducció que ens fa Google de la lletra és la següent:
Set ponts travessen el riu Pregel,
Molts més del que es podria esperar;
Els savis líders de Königsberg estaven encantats
d’haver construït unes estructures tan esplèndides.
Cada vespre, les multituds marxen cap al riu,
La gent caminava desconcertada pels ponts,
Reflexionant sobre un repte que sona senzill
però que els va derrotar i els va deixar desconcertats.
Aquí està el problema; a veure si ho pots resoldre!
Prova-ho a casa amb un tros de paper!
COMENÇANT I ACABAT AL MATEIX LLOC,
CADA TARDE HEU DE TRAVESSAR CADA PONT NOMÉS UNA VEGADA.
Tornada
Tots els gràfics eulerians tenen aquesta restricció:
EL GRAU DE QUALSEVOL PUNT ÉS PARELL.
Aquest és el resultat del gràfic més antic
Que la humanitat ha conegut mai.
Tota la gent de Königsberg estava frenètica!
Tots els seus esforços acabaven en fracàs!
Afortunadament, un matemàtic erudit
Tenia casa seva allà mateix, a la ciutat.
La ment d’Euler estava a l’altura del problema:
“Ah”, va dir, “Estàs obligat a desanimar-te.
Creuant cada pont només una vegada
No es pot fer, de veritat t’ho asseguro”.
Tornada:
Gràfics eulerians…
Les lleis de la natura mai es poden alterar,
No les podríem canviar, encara que ho desitgem.
Tampoc els rius inundats o els grans ponts
Interferir en el progrés científic.
La guerra va portar conflictes i ruïnes al Pregel;
Les bombes van destruir aquests set esplèndids ponts.
El nom i la fama d’Euler, no obstant això,
Ser recordat amb Königsberg’s per sempre.
Tornada:
Gràfics eulerians…
Gràcies a Euler, la teoria dels grafs està prosperant.
Any rere any floreix i floreix,
Fecundant bona part de les matemàtiques
I tan rica en totes les seves aplicacions.
Companys, omplim tots els nostres gots!
Col·legues, aixequem-los ara per brindar
Grandesa i glòria eterna
a la nostra estimada Teoria de Grafs!
Enllaç a la partitura i a l’himne en diferents idiomes
En aquest vídeo podeu escoltar dues versions, l’original en txec) en polac.
I en aquest altre enllaç hi trobareu un vídeo de “l’estrena” de l’himne (no té so fins als 40 segons).
Nous problemes
Molts dels autors clàssics que s’han dedicat a la invenció i “recol·lecció” de problemes d’entreteniment, en algun moment, han recollit algun problema sobre “figures d’un sol traç” o amb qüestions sobre itineraris que hi estan relacionades. Tres dels quatre problemes aquí plantejats són d’ells: H. E. Dudeney (Robin i Marian), E. I. Ignatiev (Els 15 ponts) i Y. I. Perelman (Els ponts de St. Petersburg).
- Robin i Marian
L’equip de rescat de Robin Hood vol buscar la cel·la on el sheriff de Nothingam amaga a la seva estimada Marian. Disposa d’un plànol de les sales del palau però no sap exactament a quina d’elles està l’amagatall secret on tenen tancada a la Marian. Només sap que si comença per una de les sales exteriors i passa una sola vegada i només una per cadascuna de les portes acabarà forçosament a la sala on hi ha la masmorra secreta on l’amaguen. La qüestió és que només ho podrà fer si comença per la sala convenient de les 12 que n’hi ha.
Pots ajudar a en Robin a trobar la sala de l’entrada secreta on amaguen a la Marian?
- Els 15 ponts
Tracta de buscar un itinerari que passi pels 15 ponts.
Pensa que, el més important, és triar a quina zona comences!
- El fantasma del “Palau de les 5 cambres”
El fantasma del “Palau de les 5 cambres” estar condemnat a vagar permanentment fins que trobi un camí per passar per les 5 sales de l’edifici travessant una sola vegada cada paret. pot passar per l’exterior del palau totes les vegades que vulgui. Al dibuix tens un exemple de camí que deixa una paret sense travessar (de color vermell).
És possible fer-ho o està condemnat a vagar eternament?
- Els ponts de Sant Petersburg
Els habitants de St. Petersburg van tenir na sort de la que no van gaudir els de Köningsberg; ells sí que podien fer una passejada passant per cadascun dels seus 17 una sola vegada.
Com ho podien fer?
