Problem med lådprincipen
Hej!
Har lite problem med att förstå den generella lådprincipen som lyder: Om n * k +1 föremål ska placeras i n lådor, så måste minst en låda innehålls k+1 eller fler föremål. Där n och k är heltal.
Jag känner att jag förstår själva definitionen men allt blir ett frågetecken när boken väljer att ta upp följande exempel:
Storstockholm har 1510 000 invånare. Vi antar att en människa har färre än 500 000 hårstrån på huvudet. Visa att åtminstone 4 av dessa invånare har exakt samma antal hårstrån.
Lösning:
Lådor: 500 000 st (0-499 999 hårstrån)
Föremål: 1510 000 sthlmare
Eftersom 1510 000 > 500 000 * 3 + 1 säger lådprincipen att åtminstone en låda innehåller 3+1 föremål. Dvs. minst 4 sthlmare har samma antal hårstrån på huvudet.
Hmm..Jag förstår att man utifrån 1510 000 > 500 000 * 3 + 1 kan säga att minst 3+1=4 (k+1) stockholmare har samma antal hårstrån på huvudet med ovannämnda definition i baktanken men varför just 1510 000 > 500 000 * 3 + 1?
Vad innebär just 500 000 * 3 + 1 i detta sammanhang om nu 1510 000 är föremålen? - vad säger denna del mig? Varför säger man först att 1510 000 är föremålen och skriver 1510 000 > 500 000 * 3 + 1. Hänger inte med riktigt..Enligt definitionen borde ju 500 000 * 3 + 1 betyda att man fördelar 3 sthmlare i 500 000 lådor. Resten 1 borde ju betyda att 1 person blir över som måste placeras i någon av "lådorna" och därmed måste minst 4 stockholmare ha samma antal hårstrån. Om nu det stämmer så borde ju 500 000 * 3 + 1 (jämför med n*k+1 i def.) vara föremålen och inte 1510 000.
Om jag själv löser uppgiften så utgår jag från formeln n*k +1
Föremål: 1510 000 sthlmare (n*k+1)
Lådor = 500 000 st (n)
500 000 * k +1 = 1510 000 k 3 (har förstått det som att man alltid ska avrunda till minsta heltal)
Man får ju då att 1510 000 500 000 * 3 +1.
Nu när jag tänker efter så kanske det bara är så enkelt som att man bara skriver så för att visa minsta antalet personer (k+1 = 4 st), och eftersom det ändå måste vara ett heltal (antal personer) och man vill vara tydlig så skriver man ut 1510 000 > 500 000 * 3 +1? Tänker jag rätt?
Om jag tolkar dig rätt är det så enkelt som du skriver på slutet. Det skulle räcka att det finns 1 500 001 stockholmare för att det skall finnas minst en låda med 4 stockholmare i (men vi kan inte vara säkra på att det finns 5 i någon låda trots att det är nästan 100 000 personer extra, även om det kan vara så).
smaragdalena skrev :Om jag tolkar dig rätt är det så enkelt som du skriver på slutet. Det skulle räcka att det finns 1 500 001 stockholmare för att det skall finnas minst en låda med 4 stockholmare i (men vi kan inte vara säkra på att det finns 5 i någon låda trots att det är nästan 100 000 personer extra, även om det kan vara så).
Så bra förklarat! Tack så mycket! :)