Side 1 av 1

15 personer rundt et bord

InnleggSkrevet: 07/12-2017 22:42
Gustav
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.

Re: 15 personer rundt et bord

InnleggSkrevet: 07/12-2017 23:34
Emilga
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.)

Re: 15 personer rundt et bord

InnleggSkrevet: 08/12-2017 11:49
Gustav
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...