Duvhålsprincipen; oavsett vilken del av en talföljd som väljs kan den delas med talföljdens längd
Frågan lyder:
Jag har försöka att definiera problemet för övnings skull:
Sedan definiera duvhålsprincipen:
- Duvhålsprincipen innebär att om vi har m föremål och ska placera dom i n behållare, där n < m, så kommer det alltid att finnas åtminstone 1 behållare som kommer att innehålla ≥2 objekt.
Efter detta har jag klurat på hur jag kan skriva en förklaring till detta problem. Jag förstår hur det fungerar, men jag vet inte riktigt hur jag ska förklara det. Här är mitt försök:
- För att göra problemet lättare kan vi utföra mod m på alla tal, då detta kommer att lämna oss med alla talens rester som ska summeras till ett tal n som ska att uppfylla n MOD m = 0.
Nu kommer alla tal att vara mindre än m, mellan 0 och m - 1. Här ifrån kan vi dela upp dessa i fall:
1) Minst 1 nolla: Om det finns ett tal som är 0 så kommer det alltid gå att välja i och j till samma tal och på de sättet uppfylla kravet; 0 mod m = 0.
2) Endast 1:or: Om alla tal är 1 så kan man såklart summera hela talföljden och kommer även det uppfylla kravet; m mod m = 0.
3) Total summering är minst m+1 (duvhålsprincipen): Här kommer alltid minst ett tal att vara ≥ 2 (enligt duvhålsprincipen definierad ovan). Det kommer alltså alltid att finnas m st tal att välja på, och varje tal x kommer att ha ett värde 0 < x < m, förutom ett tal x som kommer att ha ett värde 1 < x < m. Detta gör att det alltid kommer att finnas minst ett tal som förekommer 2 gånger.
Ett tal kan byggas upp av tal mindre än sig själv, och kan behöva 2 st av samma tal för att uppnå detta, och enligt det som precis redovisats så kommer det alltid att finnas.
Jag är inte nöjd med denna redovisning då den varken är särskilt matematisk eller tydlig. Skulle någon kunna hjälpa mig med detta, hur skulle du tänka kring denna uppgift och redovisa på ett tydligt vis?
Tack
Jag tycker din lösning är lite obegriplig och misstänker väl att tankegången inte stämmer, hela frasen "Ett tal kan byggas upp av tal mindre än sig själv, och kan behöva 2 st av samma tal för att uppnå detta, och enligt det som precis redovisats så kommer det alltid att finnas" är vag.
Ledning: titta på serier av formen
x_1
x_1+x_2
x_1+x_2+x_3
....
Hmm, sorry men kommer inte framåt. Har suttit nu och klurat på detta men det lossnar inte. Jag har testat några talföljder och som du påpekade känner jag att jag inte förstår varför detta fungerar. Skulle du kunna utveckla lite kring ditt svar?
Jag har även tagit en titt på lösningsförlsaget till denna uppgift men jag blir inte klok på det. Men tänkte iallafall att jag lägger upp den så den också kan ses:
Visa spoiler
Jo alltså lösningsförslaget är precis som jag hade tänkt.
Vi bildar de m summorna
S_1=x_1
S_2=x_1+x_2
...
S_m=x_1+x_2+...+x_m
Om någon av dem ger rest 0 vid division med m så är vi klara.
I annat fall ger två av dem samma rest vid division med m, säg att S_i och S_j ger samma rest där i<j.
Då är S_j-S_i delbar med m och är en summa av det slag vi söker.
Jag noterar nu helt plötsligt att problemet i titeln och problemet i den ursprungliga inte är samma problem.
Är du helt säker på att du förstår problemformuleringen?
Jag förstår inte riktigt lösningsförslaget som är. Låt mig ta ett exempel
5, 13, 30, 1, 4, 28
1) 5 = 52) 5 + 13 = 183) 5 + 13 + 30 = 484) 5 + 13 + 30 + 1 = 495) 5 + 13 + 30 + 1 + 4 = 536) 5 + 13 + 30 + 1 + 4 + 28 = 81
MOD 6
1) 5 = 52) 5 + 1 = 63) 5 + 1 + 0 = 64) 5 + 1 + 0 + 1 = 75) 5 + 1 + 0 + 1 + 4 = 116) 5 + 1 + 0 + 1 + 4 + 4 = 15
Jag förstog uppgiften som att, för vilken talföljd som helst, så kommer summan av siffrorna i minst en sekvens av vara delbar med talförljdens längd. Så här skulle ju ex x1 + ... + x3 vara giltigt, men även x2 + ... + x5. Men när man ställer upp det på detta sätt så börjar man ju alltid på x_1, förstår inte riktigt hur vi går från det till att resonera kring x_i. Förstår du vad jag menar?
Ja men då har du förstått uppgiften rätt.
Jag förstår dock inte vad du vill visa med exemplet.
I ditt exempel är ju både delserie 2) och 3) delbara med 6 så då är vi klara. Vi tittar på ett annat exempel. Säg n=4 och vi serien 1,2,3,5
Vi får
1) 1
2) 1+2=3
3) 1+2+3=6
4) 1+2+3+5=11
Reducerar modulo 4:
1) 1
2) 1+2=3
3) 1+2+3=6=2 mod 4
4) 1+2+3+5=11= 3 mod 4
I det här fallet är ingen av serierna delbara med 4 men då ger duvhålsprincipen att två måste höra till samma restklass modulo 4. I det här fallet är det
2) 1+2 och 4) 1+2+3+5 som båda ger rest 3 vid division med 4.
Men då är differensen mellan 4) och 2) delbar med 4, dvs 3+5, vilket är en delserie av det slag vi söker.
Okej, ja detta var ett bättre exempel. Juste för då om resten är samma för 2 olika tal så vet vi att man kommer att kunna addera n (längden av talföljden) från x_i tills x_j är uppnådd!
Jag ser dock inte sambandet med differensen och beviset.
Om jag ex har denna följd:
2, 2, 4, 3, 2; n = 5
1) 2
2) 2 + 2 = 4
3) 2 + 2 + 4 = 8
4) 2 + 2 + 4 + 3 = 11
5) 2 + 2 + 4 + 3 + 2 = 13
MOD 5 ger resterna:
1) 2
2) 4
3) 3
4) 1
5) 3
I detta fall så ser vi att de två rester som är samma är från sekvens 3) och 5). Om vi tar differensen mellan dessa, 13 - 8 så får vi mycket riktigt 5. Det vi vill visa är i detta exempel att 5 | x_3 + x_4 + x_5, dvs 5 | 8 + 11 + 13 men vi ser att 5 ∤ 32.
Ser du vart det är i min tankegång som jag tar fel?
Nej,
Skillnaden mellan S_3 och S_5 bara två termer x_4+x_5. Vilket är 3+2=5 vilket är delbart med 5.
