Hur många vägar
Hej.
"Hur många vägar måste dras om 6 städer ska ha direktförbindelse med varandra?"
I boken står det "antalet slutna resvägar mellan n hörn där alla hörn har förbindelse med varandra är (n-1)!"
Svaret på frågan är att det är 15 vägar.
Går man efter vad boken säger blir det alltså 5*4*3*2*1= 120.
Jag förstår inte att det är en skillnad i frågan och formuleringen i boken.
Antalet ”slutna resvägar”, 120 stycken, är de olika sätt man köra en rundtur och besöka samtliga städer en gång.
Du kan rita upp det ganska lätt på papper.
Rita sex prickar som är städerna. Dra raka streck mellan alla prickar. Strecken är vägarna som det frågas efter.
Okej, jo, men det går inte att härleda någon generell formel för det?
sictransit skrev:Antalet ”slutna resvägar”, 120 stycken, är de olika sätt man köra en rundtur och besöka samtliga städer en gång.
Ifrån olika startpunkter och sedan olika ordning ifrån varje startpunkt också? Och det är okej att överlappa en stad flera gånger osv? Det vill säga att om man börjar från stad 1, åker till stad 2, sedan ligger stad 3 "bakom" stad 1, så man måste åka tillbaka och korsa startpunkten en gång?
Dkcre skrev:Okej, jo, men det går inte att härleda någon generell formel för det?
Jo, det går att resonera sig fram till att antalet vägar är 5+4+3+2+1, t.ex. på följande sätt:
Börja i första hörnet och dra en väg till alla andra hörn. Det blir 5 vägar. Nu är första hörnet "klart" och ska inte ha några fler vägar till/från sig.
Börja sedan i andra hörnet och dra en väg till alla resterande hörn. Det blir 4 vägar. Nu är andra hörnet "klart" och ska inte ha några fler vägar till/från sig.
Börja sedan i tredje hörnet och dra en väg till alla resterande hörn. Det blir 3 vägar. Nu är tredje hörnet "klart" och ska inte ha några fler vägar till/från sig.
Börja sedan i fjärde hörnet och dra en väg till alla resterande hörn. Det blir 2 vägar. Nu är fjärde hörnet "klart" och ska inte ha några fler vägar till/från sig.
Börja sedan i femte hörnet och dra en väg till det enda resterande hörnet. Det blir 1 väg Nu är femte hörnet "klart" och ska inte ha några fler vägar till/från sig.
Från det sjätte hörnet finns inga nya vägar att dra eftersom alla andra fem hörn redan är "klara:".
Totala antalet vägar är 5+4+3+2+1 = 15.
======
Metoden kan även användas i andra sammanhang, t.ex. vid frågor som
- "Hur många handskakningar blir det om alla 20 gästerna på festen ska hälsa på varandra en gång?"
- "Hur många matcher ska spelas om alla möter alla 2 gånger då fotbollsserien innehåller 10 lag?"
Dkcre skrev:sictransit skrev:Antalet ”slutna resvägar”, 120 stycken, är de olika sätt man köra en rundtur och besöka samtliga städer en gång.
Ifrån olika startpunkter och sedan olika ordning ifrån varje startpunkt också? Och det är okej att överlappa en stad flera gånger osv? Det vill säga att om man börjar från stad 1, åker till stad 2, sedan ligger stad 3 "bakom" stad 1, så man måste åka tillbaka och korsa startpunkten en gång?
Sex olika startpunkter. Alla städer skall besökas exakt en gång. Sedan tillbaka till startpunkten så att det blir en rundtur, en ”sluten resväg”. Eftersom alla städer är förbundna med varandra finns inget behov av att besöka en stad fler än en gång.
Du kan ju rita upp en enklare graf med tre städer. Då har du tre startpunkter och två vägar ut från varje stad. Till sist skall du tillbaka till utgångspunkten. Dit finns en väg: 3!=3*2*1=6.
Okej tack 🙂
