Om duer og middag

[mrcreosote]

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.

[arildno]

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.

[sEirik]

ja, duetullprinsippet høres bra ut. Prinsippet som sier at "duehullprinsippet" er et tullete navn på et slikt prinsipp.

[daofeishi]

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

[mrcreosote]

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.

[daofeishi]

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