a) I løpet av de 6 første ukene på skolen sendte Børre ut minst ett resume hver dag, men aldri flere enn 60 totalt. Vis at det er en periode med etterfølgende dager hvor han sender ut 23 resumér.
b) Hvor mange ganger må vi kaste en terning for å få samme score
1: minst to ganger
2: minst tre ganger
3: minst n ganger når n [tex] \geq [/tex] 4?
Pigeonhole principle
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
- Over-Guru
- Innlegg: 1685
- Registrert: 03/10-2005 12:09
a) La x[sub]i[/sub] være antall resyme Børre har sendt ut tilsammen fra starten av denne 6 ukers perioden til slutten av dag i. Ettersom Børre sender minst et resyme hver dag og maksimalt tilsammen 60 i løpet av de 42 dagene, blir
(1) 1 ≤ x[sub]1[/sub] < x[sub]2[/sub] < ... < x[sub]42[/sub] ≤ 60.
Herav følger at
(2) x[sub]1[/sub] + 23 < x[sub]2[/sub] + 23 < ... < x[sub]42[/sub] + 23 ≤ 83.
Nå har vi 42 ulike naturlige tall x[sub]1[/sub], x[sub]2[/sub], ... , x[sub]42[/sub] i (1) og 42 ulike naturlige tall x[sub]1[/sub] + 23, x[sub]2[/sub] + 23, ... , x[sub]42[/sub] + 23 i (2). Disse 84 naturlige tallene er alle ≤ 83, så iht. skuffeprinsippet finnes det to heltall 1 ≤ m < n ≤ 42 slik at x[sub]m[/sub] = x[sub]n[/sub]+ 23, dvs. at x[sub]m[/sub] - x[sub]n[/sub] = 23. M.a.o. har Børre fra starten av dag n+1 tll slutten av dag m sendt ut akkurat 23 resymeer.
b) La A(n) være antall ganger du må kaste en terning for å være sikker på å få samme score n ganger. Det er 6 ulike scorer (1,2,3,4,5,6). Du kan kaste 6(n - 1) ganger og få n - 1 hver av de 6 ulike scorene. Kaster du derimot 6(n - 1) + 1 ganger, må en score forekomme minst [6(n - 1) + 1] / 6 = n - 1 + 1/6 > n - 1 ganger ifølge skuffeprinsippet. Dermed kan vi konkludere med at A(n) = 6n - 5.
(1) 1 ≤ x[sub]1[/sub] < x[sub]2[/sub] < ... < x[sub]42[/sub] ≤ 60.
Herav følger at
(2) x[sub]1[/sub] + 23 < x[sub]2[/sub] + 23 < ... < x[sub]42[/sub] + 23 ≤ 83.
Nå har vi 42 ulike naturlige tall x[sub]1[/sub], x[sub]2[/sub], ... , x[sub]42[/sub] i (1) og 42 ulike naturlige tall x[sub]1[/sub] + 23, x[sub]2[/sub] + 23, ... , x[sub]42[/sub] + 23 i (2). Disse 84 naturlige tallene er alle ≤ 83, så iht. skuffeprinsippet finnes det to heltall 1 ≤ m < n ≤ 42 slik at x[sub]m[/sub] = x[sub]n[/sub]+ 23, dvs. at x[sub]m[/sub] - x[sub]n[/sub] = 23. M.a.o. har Børre fra starten av dag n+1 tll slutten av dag m sendt ut akkurat 23 resymeer.
b) La A(n) være antall ganger du må kaste en terning for å være sikker på å få samme score n ganger. Det er 6 ulike scorer (1,2,3,4,5,6). Du kan kaste 6(n - 1) ganger og få n - 1 hver av de 6 ulike scorene. Kaster du derimot 6(n - 1) + 1 ganger, må en score forekomme minst [6(n - 1) + 1] / 6 = n - 1 + 1/6 > n - 1 ganger ifølge skuffeprinsippet. Dermed kan vi konkludere med at A(n) = 6n - 5.