Om duer og middag
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
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.
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).
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).
-
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
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.
Løsninga er sjølsagt helt korrekt. Den nye oppgava var presis min oppfølger også, ikke verst.