Skillnad mellan versioner av "Det specifika tunnelbaneproblemet"

AlefWiki
Hoppa till navigering Hoppa till sök
m (10 versioner)
 
m
Rad 5: Rad 5:
  
 
== Lösningar ==
 
== 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 \isin 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.
+
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 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==

Versionen från 18 oktober 2010 kl. 03.05

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 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

Det generella tunnelbaneproblemet