Om duer og middag

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Om duer og middag

Innlegg mrcreosote » 26/09-2007 19:32

I en forsamling av et visst antall duer, minst 2, er det nødvendigvis sånn at hvert par av to duer enten har spist middag sammen eller ikke. Vis at uansett åssen denne forsamlinga er vil vi kunne finne to duer som har spist middag med like mange.
mrcreosote offline
Guru
Guru
Brukerens avatar
Innlegg: 1995
Registrert: 10/10-2006 19:58

Innlegg arildno » 26/09-2007 21:33

Umiddelbart virker det som man skal bruke duetull-prinsippet, eller på fint, the pigeon hole principle.

Eller noe sånt.

Får grupble litt videre.
arildno offline
Abel
Abel
Innlegg: 684
Registrert: 17/03-2007 17:19

Innlegg sEirik » 26/09-2007 21:34

ja, duetullprinsippet høres bra ut. Prinsippet som sier at "duehullprinsippet" er et tullete navn på et slikt prinsipp. :wink:
sEirik offline
Guru
Guru
Brukerens avatar
Innlegg: 1551
Registrert: 12/06-2006 20:30
Bosted: Oslo

Innlegg daofeishi » 27/09-2007 03:26

LA oss si vi har d duer. Konstruer middagsgrafen M der hver due er en node, og nodene deler en kant dersom duene har spist middag sammen. Da er antall middager en due har spist gitt ved nodens grad. Det finnes maksimum (d-1) ulike grader. Dette fordi det ikke samtidig kan finnes en node ved grad 0 og en ved grad (d-1). Vi har da d noder og (d-1) mulige grader. Ved duehullprinsippet betyr det at det må finnes minst 2 noder med samme grad, og vi er ferdige.

Eller i klartekst:
Tenk på hvor mange middager en due kan ha spist - det finnes (d-1) andre duer. Hvis det eksisterer en due som har spist (d-1) middager, kan det ikke finnes en due som har spist 0 middager, og omvendt. Dermed finnes det maksimum (d-1) mulige "middagstall". Men det finnes d duer! Du skal da fordele maksimum (d-1) ulike middagstall blant d duer, og det betyr at det må finnes minst to duer med samme middagstall.


Oppfølgeroppgave: Vis at i en gruppe på 6 personer finnes det enten 3 personer som kjenner hverandre innbyrdes, eller 3 som ikke gjør det (eller begge deler).
daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Innlegg mrcreosote » 27/09-2007 07:13

Hvis jeg googler "middagsgrafen" får jeg ingen treff; gratulerer med nytt ord!

Løsninga er sjølsagt helt korrekt. Den nye oppgava var presis min oppfølger også, ikke verst.
mrcreosote offline
Guru
Guru
Brukerens avatar
Innlegg: 1995
Registrert: 10/10-2006 19:58

Innlegg daofeishi » 27/09-2007 12:10

Det må jeg si, ikke finnes ordet i Tanums store rettskrivningsordbok heller. Kanskje dette er en sak for suppe... nei språkrådet?

Og ellers - hurra for grafteori :)
daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 21 gjester