2 svar
1169 visningar
Hiinz0 behöver inte mer hjälp
Hiinz0 50 – Fd. Medlem
Postad: 14 jun 2017 20:42

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? 

Smaragdalena 80504 – Avstängd
Postad: 14 jun 2017 20:56

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å).

Hiinz0 50 – Fd. Medlem
Postad: 14 jun 2017 20:58
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! :)

Svara
Close