Skal ha eksamen i diskret matte på onsdag, og sitt no og løyser gamle eksamensoppgåver, men kjem ikkje fram til rett framgangsmåte i fylgjande oppgåve:
---
En gruppe på n studenter deltar i en sjakkturnering der alle skal spille nøyaktig ett parti mot hver av de andre. Vinneren av partiet får ett poeng, mens taperen får null poeng. Ender partiet med remis (uavgjort), kåres spilleren med de svarte brikkene til vinner, og får således poenget. Rekkefølgen som partiene skal spilles i avgjøres med loddtrekning. Bare ett parti spilles om gangen.
a) Er det mulig at det på et punkt i turneringen ikke finnes to spillere som har samlet like mange poeng? Gi et eksempel, eller bevis at det er umulig. Forklar eventuelt hvilket prinsipp som ligger til grunn for beviset.
---
Har funne ut at det ER mulig, med å sjå på eksempelet n=3, der det etter 3 parti er mogleg at ein har vunne 2, ein har vunne 1, og ein har vunne 0 parti.
Men noko seier meg at ein meir elegant teknikk/eksempel kan brukast til å bevise det, som ikkje berre gjeld for 3. T.d duehol-prinsippet har streifa meg, sidan det måtte gå an å berre ha ein spelar i kvart hol, der kvart hol representerte ein poengsum. Men....korleis?
Takkar for innspel.
Kva framgangsmåte?
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
http://ringheimsauto.1go.dk
Fri musikk for bilstereo!
Fri musikk for bilstereo!
-
Solar Plexsus
- Over-Guru
- Innlegg: 1685
- Registrert: 03/10-2005 12:09
Etter hvert spilte sjakkparti blir det delt ut 0 poeng til taperen og 1 poeng til vinneren. Dette betyr at det samlede antall poeng hver deltager har underveis i turneringen, alltid er et heltall mellom 0 og n-1. Videre er den summen av de poengene som deltagerne har etter turneringen er avsluttet, lik C(n-1,2) = n(n - 1)/2. La oss nå anta at følgende påstand er sann:
(1) På et punkt i turneringen har deltagerne ulik poengsum.
Siden det bare er n mulige poengsummer som skal fordeles på n deltagere, må deltagerne på nevnte punkt i turneringen ha samlet hhv. 0, 1, 2, ..., n-1 poeng. Altså er deltagernes samlede poengssum lik 0 + 1 + 2 + ... + (n - 1) = n(n - 1)/2. M.a.o. er turneringen ferdigspilt. Dermed kan vi konkludere med at påstand (1) kun kan være sann dersom turneringen er avsluttet.
Personlig anser jeg at formuleringen "et punkt i turneringen" utelukker at situasjonen beskrevet i (1) oppstår etter at turneringen er ferdigspilt. Følgelig vil jeg konkludere med at påstand (1) er usann.
(1) På et punkt i turneringen har deltagerne ulik poengsum.
Siden det bare er n mulige poengsummer som skal fordeles på n deltagere, må deltagerne på nevnte punkt i turneringen ha samlet hhv. 0, 1, 2, ..., n-1 poeng. Altså er deltagernes samlede poengssum lik 0 + 1 + 2 + ... + (n - 1) = n(n - 1)/2. M.a.o. er turneringen ferdigspilt. Dermed kan vi konkludere med at påstand (1) kun kan være sann dersom turneringen er avsluttet.
Personlig anser jeg at formuleringen "et punkt i turneringen" utelukker at situasjonen beskrevet i (1) oppstår etter at turneringen er ferdigspilt. Følgelig vil jeg konkludere med at påstand (1) er usann.
-
Gjest
Takk for godt svar!
Det stemmer og med eksperimentet mitt med 3 spelarar, dei kan berre ha ulike poengsummar når turneringa er ferdig.
Det stemmer og med eksperimentet mitt med 3 spelarar, dei kan berre ha ulike poengsummar når turneringa er ferdig.