matematikk.net

Inspirert av en viss Randall Munroe har jeg denne oppgaven:

Som alle gutter vet, skal man stille seg lengst unna alle andre når man er på do, og man kan ikke stille seg ved siden av noen andre. Hvis man antar at [tex]n[/tex] personer går en etter en inn på en do med [tex]n[/tex] pissoarer, hvor stor del av dem blir brukt, hvis alle følger dassreglene, og ingen blir ferdig?

Edit: Første personen stiller seg ytterst.

Eksempelbilder, lånt av XKCD: (Numrene viser hvem som går inn først)


[tex]\frac35[/tex] blir brukt.


[tex]\frac37[/tex] blir brukt.


[tex]\frac48[/tex] blir brukt.

Leter du etter maksimalt antall som kan gå på do gitt [tex]n[/tex] urinaler, eller minimum antall personer ?

Maksimalt blir selvfølgelig [tex][\frac{n}{2}][/tex]

Minimalt er jeg usikker på men, antar

[tex][\frac{n}{3}][/tex]

skyt meg om det er feil

Ikke helt. Først går en person 1 inn. Han stiller seg ved en av urinalene nærmest veggene. Så går person 2 inn. Han stiller seg ved det urinalet som er så langt unna person 1 som mulig - dvs det nærmest den andre veggen. Så kommer person 3 inn. Han stiller seg så langt unna både 1 og 2 som mulig. Person 4 kommer så inn, og stiller seg så langt unna de tre andre som mulig. Så fortsetter dette til alle [tex]n[/tex] er kommet inn. Det er ikke lov å stille seg ved siden av en annen person. Samtidig må man hele tiden maksimere avstanden til sine naboer. (Litt usikker på hvordan denne optimaliseringen finner sted - trådstarter skal selvfølgelig få definere sin egen oppgave, men gutteintuisjon tilsier at han ønsker å maksimere avstanden til sin nærmeste nabo.) Om man ikke har noen mulige urinaler å bruke må man ganske enkelt late som man ikke ønsket noe annet enn å vaske hendene sine og deretter forlate urinalene. Samtidig vil ingen av de [tex]n[/tex] personene forlate urinalene før alle har vært inne og 'prøvd seg'. Spørsmålet er så hvor mange av urinalene som blir brukt.

EDIT: Jeg leste 'pissoar' som 'urinal'. Ordene er dog like nok til at jeg ikke kommer til å redigere posten min.

Jeg leter etter hvor mange som blir brukt, hvis alle følger reglene. (Lengst unna alle andre, den første stiller seg ytterst, kan ikke stå ved siden av noen andre.)

Eksempel for 8:
1. Stiller seg på #1
2. Stiller seg på #8
3. Stiller seg på #4 (eller #5)
4. Stiller seg på #6 (eller #3)

Og da er det ikke plass til flere.
Svaret er altså [tex]f(8) = \frac48[/tex]

Funksjonen du leter etter vil bli noe slikt som [tex]f(n) = \frac?n[/tex]

Nok et eksempel på hvor nyttig matematikk faktisk kan være i praktiske sammenhenger.

Kom fram til at antall pissoarer som blir brukt er:

[tex]P_n=2+a_{n-2}[/tex], hvor [tex]{a_n}[/tex] er definert ved at [tex]a_{2n-1}=2a_{n-1}+1[/tex], og [tex]a_{2n}=a_n+a_{n-1}+1[/tex], og [tex]a_1=a_2=0[/tex], og [tex]P_1=P_2=1[/tex].

Prøv gjerne å finne et uttrykk for [tex]a_n[/tex].

Jeg tror [tex]P_n=n-2^{1+\lfloor \log_2(\frac{n-2}{3}) \rfloor }[/tex] dersom [tex]n < 2^{2+\lfloor \log_2(\frac{n-2}{3}) \rfloor }[/tex],

og [tex]P_n=1+2^{1+\lfloor \log_2(\frac{n-2}{3}) \rfloor }[/tex], dersom [tex]n \geq 2^{2+\lfloor \log_2(\frac{n-2}{3}) \rfloor }[/tex],


men kan ikke bevise det. Det stemmer i hvert fall for n fra 3 og opp til 30 000. Jeg tviler på at det skulle bli aktuelt å bruke formelen for n større enn 30 000 uansett.

Ut ifra formelen ser vi at [tex]P_n[/tex] øker i takt med [tex]\frac{1}{3}n[/tex] og [tex]\frac{1}{2}n[/tex] respektivt. Det vil si at ca mellom [tex]\frac{1}{2}[/tex] og [tex]\frac{1}{3}[/tex] av plassene vil bli tatt, i alle fall for store n.

Ligner litt på svaret her:

http://blag.xkcd.com/2009/09/02/urinal- ... erability/

Formelen kan forresten bevises ved induksjon med utgangspunkt i de rekursive formlene for [tex]P_n[/tex].

Synes denne oppgaven var utrolig morsom og den viser hvordan matematikk kan brukes på dagligdagse problemer ved å innføre enkle regler.
Men hvordan regnet du ut formelen? Hvordan tenker man for å løse slike problemer?

[tex]a_n[/tex] hadde ikke et åpenbart mønster, så en datamaskin var til stor hjelp. Det man oppdager er at [tex]a_n[/tex] følger et litt spesielt system. Kall en "blokk" for alle tallene fra og med [tex]3 \cdot 2^k[/tex] og til men ikke med [tex]3 \cdot 2^{k+1}[/tex]. Når [tex]n = 3 \cdot 2^k[/tex] øker den med 1 per n opp til [tex]n=2^{k+2}[/tex], hvor den stopper å stige til den treffer neste blokk. Dette kan man lage en formel ut av, ved å dele opp hver blokk hvor den stiger og hvor den ikke gjør det. Dette er jo ikke et bevis for formelen, men ved å bruke de rekursive formlene kan man lage seg et induksjonsbevis.