Skillnad mellan versioner av "Det specifika tunnelbaneproblemet"
Eric (diskussion | bidrag) m |
Schreib (diskussion | bidrag) |
||
| (4 mellanliggande versioner av 2 användare visas inte) | |||
| Rad 1: | Rad 1: | ||
| − | '''Det specifika tunnelbaneproblemet''' är en enklare variant av Niklas den yngres [[Det generella tunnelbaneproblemet|generella tunnelbaneproblem]]. | + | '''Det specifika tunnelbaneproblemet''' är en enklare variant av Niklas den yngres [[Det generella tunnelbaneproblemet|generella tunnelbaneproblem]]. Problemet är reproducerat nedan. |
| − | == | + | == Problemet == |
| − | + | Problemet behandlar fallet när vi endast har en ringlinje och ska visa att för ett givet antal passagerar per dag kommer minst två alltid att åka exakt samma färdväg där en resa definieras som en förflyttning mellan två skilda noder som aldrig passerar noder mer än en gång. | |
| + | == Lösningar == | ||
| + | En lösning är närmst trivial då vi börjar med att inse att det totala antalet resor är <math>4 {n \choose 2} </math> för <math>n \in \mathbb{N}</math> eftersom om vi väljer en nod <math>\displaystyle A</math> och en nod <math>\displaystyle B</math> kan vi åka i två riktningar ifrån <math>\displaystyle A</math> till <math>\displaystyle B</math> och i två riktningar från <math>\displaystyle B</math> till <math>\displaystyle A</math>. Därefter kontrollerar man bara gentemot antalet passagerare som är givna och använder [[Dirichlets lådprincip]] och är sedan färdig. | ||
==Se även== | ==Se även== | ||
Nuvarande version från 18 oktober 2010 kl. 05.46
Det specifika tunnelbaneproblemet är en enklare variant av Niklas den yngres generella tunnelbaneproblem. Problemet är reproducerat nedan.
Problemet
Problemet behandlar fallet när vi endast har en ringlinje och ska visa att för ett givet antal passagerar per dag kommer minst två alltid att åka exakt samma färdväg där en resa definieras som en förflyttning mellan två skilda noder som aldrig passerar noder mer än en gång.
Lösningar
En lösning är närmst trivial då vi börjar med att inse att det totala antalet resor är [math]4 {n \choose 2} [/math] för [math]n \in \mathbb{N}[/math] eftersom om vi väljer en nod [math]\displaystyle A[/math] och en nod [math]\displaystyle B[/math] kan vi åka i två riktningar ifrån [math]\displaystyle A[/math] till [math]\displaystyle B[/math] och i två riktningar från [math]\displaystyle B[/math] till [math]\displaystyle A[/math]. Därefter kontrollerar man bara gentemot antalet passagerare som är givna och använder Dirichlets lådprincip och är sedan färdig.
