matematikk.net

Viser til denne gamle, men veldig gode, posten om problemløsing fra 2007: http://matematikk.net/matteprat/viewtop ... 19&t=15073.

Der er det mange eksempler på bevisoppgaver, men ikke alle er løst enda.Tenkte jeg kunne prøve meg på den første uløste problemstillingen. Finner dere noen feil i argumentasjonen under (er beviset gyldig)?

Problem
Du befinner deg i et rom med 5 andre personer. Bevis at det i dette rommet befinner seg enten 3 personer som kjenner hverandre fra før av eller 3 personer som ikke har møtt hverandre før (eller begge deler).

Løsning
Inklusive meg selv, er det 6 personer i rommet. Jeg gir personene navn 1, 2, 3, 4, 5 og 6. Person 1 har en relasjon til person 2-6; enten som bekjent, eller som en han/hun aldri har møtt. Personene 2-6 er fem personer. De skal fordeles blant to typer relasjoner. Skuffeprinsippet gir da at person 1 enten har minst tre bekjente i rommet, eller minst tre personer han/hun aldri har møtt.

Om jeg tar utgangspunkt i at person 1 har tre bekjente eller tre ikke-bekjente spiller ingen rolle (argumentet blir det samme). Jeg velger derfor å anta at person 1 har tre bekjente i rommet; la oss si at dette er person 2, 3 og 4. Hvis noen av disse tre er bekjente, er problemet løst (da vil tre personer, der personer 1 er den ene, alle kjenne hverandre). Jeg antar derfor at ingen av personene 2, 3 og 4 har møtt hverandre før. Men også da er problemet løst.

Ser bra ut dette!

Flott! Da kan jeg utfordre andre med følgende oppgave fra samme gate:

I et rom er det [tex]n[/tex] personer. Hver person har (akkurat) tre bekjente i rommet. To bekjente har ingen felles bekjent(e). To personer som aldri har møtt hverandre før, har (nøyaktig) én felles bekjent. Bestem [tex]n[/tex].

Siden ingen kom med noen løsning og jeg er utolmodig, tar jeg meg friheten til å gjøre det selv! Påpek gjerne eventuelle feil i min argumentasjon.

Her er det flere måter å argumentere på, naturligvis. I begge løsningene under benyttes grafer fra grafteorien. Noder illustrerer personer, mens kantene illustrerer bekjentskap mellom dem. Da merker vi oss at grafen ikke kan bestå av trekanter, da dette gir to bekjente en felles bekjent. Videre kan grafen heller ikke bestå av firkanter ettersom dette motstrider at to ikke-bekjente har nøyaktig én felle bekjent (de ville fått to). Femkanter går fint. Større mangekanter blir for store og må brytes ned med diagonaler. Følgelig må grafen bestå av femkanter. Det betyr at omkretsen i grafen er [tex]5[/tex]. Samtidig har den en diameter på [tex]k=2[/tex] (dette følger av at to ikke-bekjente har én felles bekjent). Til slutt merker vi oss at grafen er regulær av tredje grad (ettersom alle har nøyaktig tre bekjente i rommet).

Moore-graf
Fra observasjonene over ser vi at omkretsen til grafen (5) kan uttrykkes som [tex]2k+1[/tex]. Dette er en definisjon av Moore-grafer. For slike grafer av grad [tex]d[/tex] med diameter [tex]k[/tex] kan antallet noder, [tex]n[/tex], skrives som [tex]n=1+d\sum_{i=0}^{k-1}(d-1)^i[/tex], hvilket gir

[tex]n=1+3\sum_{i=0}^{2-1}(3-1)^i=1+3 \cdot (2^0+2^1)=1+3 \cdot 3=10[/tex]

Systematisk oppsett
La person 1 være en bekjent av person 2, 3 og 4. Ingen av disse (2, 3, 4) kan være bekjente av hverandre, da dette danner trekanter (med person 1). De må altså ha to bekjente til hver, der ingen er en bekjent av person 1 (det ville dannet firkanter). Vi er nå oppe i [tex]1+3+3 \cdot 2=10[/tex] personer. Grafen ser til nå slik ut (her personene navngitt med bokstaver i stedet for tall):
Så prøver vi oss fram. Vi vet det gjelder å danne femkanter, så vi lar F være en bekjent av J og H. Så lar vi E være en bekjent av G og I. G lar vi også være en bekjent av J. Tilsvarende lar vi H være en bekjent av I. Vi får da grafen under og ser altså at [tex]n=10[/tex] er en gyldig løsning.
Så antar vi at [tex]n>10[/tex]. Dette går ikke; De ti personene (A-J) kan ikke ha flere enn tre bekjente. Samtidig må de eventuelt ekstra personene være en bekjent av minst én av de ti første personene. Selvmotsigelse, altså kan ikke [tex]n>10[/tex]. [tex]n=10[/tex] blir derfor eneste løsning.

PS: Grafen over kalles Petersen-grafen, og kan tegnes som en slags stjerne (google Petersen-grafen).
PS: Noen som har andre beviser/argumenter? Eventuelt presiseringer av de over?[/size]

Det var da voldsomt til hastverk på svarfristen.