KOMBINATORIK
Hej!
Jag dessa frågor som jag behöver lite hjälp med. Jag vet att jag ska använda lådprincipen, men vet inte riktigt hur jag ska göra.
(a) Visa att det bland 101 heltal alltid finns två som har differens delbar med 100.
(b) Visa att det för vilka 52 heltal man än tar går att hitta två vars summa eller differens är delbar med 100.
a) Varje tal måste hamna i någon av restklassera 0, 1, 2, ..., 99. Vad händer om du har två stycken i samma restklass?
b) Ungefär samma tankesätt här.
Alltså att jag har 100 lådor och 101 föremål?
Ja, det finns 100 restklasser (lådor) och 101 tal (föremål). Så i någon restklass måste du ju ha två tal, vad gäller för differensen mellan dessa?
Jag ska lösa en liknande uppgift, hur ska man bevisa att bland n heltal finns det 2 tal där differensen delbar med n-1?
Förstår att man ska ta n tal och n-1 lådor.
Det är samma resonemang. Det finns n - 1 stycken restklasser och n stycken heltal, så någon restklass måste innehålla åtminstone två heltal. Differensen mellan dessa heltal måste vara delbar med n - 1.
Stokastisk skrev :Det är samma resonemang. Det finns n - 1 stycken restklasser och n stycken heltal, så någon restklass måste innehålla åtminstone två heltal. Differensen mellan dessa heltal måste vara delbar med n - 1.
Så mycket är jag med, men säg att du har 4 slumpmässigt utvalda heltal, exempelvis:
De slumpmässigt valda talen är: 2,3,7,15.
n = 4
n-1 = 3.
15-3 = 12
12/3 = 4
Jag förstår att det stämmer, men hur kan man redovisa lösningen till exempelvis uppgiften som trådskaparen skrev där talmängden är större? d.v.s. 101 slumpmässigt utvalda tal?
Jag skrev ju en lösning? Eller duger inte den?
Stokastisk skrev :Jag skrev ju en lösning? Eller duger inte den?
Jag förstår inte riktigt din lösning, hur visar du att det finns en restklass där det finns fler än ett tal. Då en "låda" enbart kan innehålla tal av ett värde, eller?
Om du har tre byttor och skall lägga fyra apelsiner i dem, måste det bli monst två apelsiner i minst en bytta. Det kallas duvslagsprincipen. I just den Wikipediaartikeln har de med din uppgift som ett exempel.
Du har n - 1 stycken restklasser, dessa kan du se som lådor.
Du har n stycken heltal, varje sådant heltal måste hamna i någon restklass. Åtminstone två av dessa tal måste hamna i samma restklass enligt lådprincipen.
Differensen mellan de två heltal som hamnade i samma restklass måste vara delbar med n - 1.
Från exemplet du hade
Restklass 0: 3, 15
Restklass 1: 7
Restklass 2: 2
Så vi hittar alltså två heltal, 3 och 15 i restklass 0, därför är differensen mellan dessa två tal delbar med 3.
Okej nu förstår jag, tack för all hjälp och alla svar.
Hej igen!
I uppgift (b) förstår jag inte hur man ska göra, eftersom vi har mindre antal föremål än vad vi har i lådor!!
Vi har då att lådorna är
Restklass 0,
Restklass 1 och restklass 99
Restklass 2 och restklass 98
Restklass 3 och restklass 97
...
Restklass 49 och restklass 51
Restklass 50
Så restklasserna har man alltså grupperat ihop, förutom restklass 50 och restklass 0. Så du måste ha att åtminstone två tal hamnar i någon av dessa lådor, eftersom det finns 51 lådor, vad blir slutsatsen av det?
Men hur ser du att t.ex. restklass 1 och 99 är samma?
Det är något man bara måste lyckas inse att man ska gruppera ihop dem så.
Det blir lämpligt i detta fall eftersom om vi får en i restklass 1 och en i restklass 99 så måste summan av dem vara delbara med 100. Om de i stället är i samma restklass så är differensen delbar med 100.
