15 personer rundt et bord

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.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

15 personer setter seg ned ved et sirkelformet bord. Når alle har satt seg oppdager de at alle setene er merket med navnekort, men ingen sitter på den plassen de skal sitte ifølge navnekortene. Vis at bordet kan roteres slik at minst to personer samtidig sitter ved sine egne navnekort.
Emilga
Riemann
Riemann
Innlegg: 1552
Registrert: 20/12-2006 19:21
Sted: NTNU

Vi observerer at det finnes 14 unike rotasjoner av bordet (med klokken), dersom vi sammenligner bordets sluttposisjon med startposisjonen: $R_1, R_2, \ldots , R_{14}$ (Vi roterer bordet ett sete; to seter; tre seter; ...; 14 seter.)

Siden hver person sitter maks 14 seter (mot klokken) fra sin egen navnelapp ved start (og ingen sitter nøyaktig på den), vil hver person ha en foretrukket rotasjon $r \in \{R_1, R_2, \ldots , R_{14} \}$ som plasserer dem på sin egen navnelapp.

Siden det er 15 personer, og maks 14 forskjellige rotasjoner, må det nødvendigvis være minst to personer som foretrekker samme rotasjon. (Dueboksprinsippet.)
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Selvsagt helt riktig. Oppgaven er opprinnelig fra Loren C. Larsons bok Problem-Solving Through problems (1983) (for øvrig en fin bok i problemløsning). Ser nå at Zeitz har en mer generell versjon av problemet i Art and craft...
Svar