Springen naar inhoud

Duivenhokprincipe


  • Log in om te kunnen reageren

#1

Misty_MMS

    Misty_MMS


  • 0 - 25 berichten
  • 9 berichten
  • Gebruiker

Geplaatst op 12 februari 2011 - 09:48

Voor een wiskunde opdracht moet ik het volgende probleem oplossen:

Er moeten zakken met spijkers verdeeld worden over 2 personen. Deze zakken verschillen in gewicht van 1 tot 100 kg. Het is altijd een geheel getal.

Waarom is het zo dat als er 10 willekeurige zakken van 1 tot 100 kg deze altijd in 2 groepen verdeeld kunnen worden met hetzelfde totaalgewicht? (Dit zonder de zakken open te maken!!)

Ze geven de volgende tips:
- op hoeveel manieren kan er een keus uit 10 zakken gemaakt worden?
- som 0 en som 1000 kunnen niet ontstaan.

Weten jullie hoe ik moet beginnen met het duivenhokprincipe zodat ik de eerste tip kan uitvoeren?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 12 februari 2011 - 10:45

Ik heb ernstig het vermoeden dat je de vraag verkeerd hebt gegeven. Kun je de exacte vraag eens overtypen?

#3

Safe

    Safe


  • >5k berichten
  • 9907 berichten
  • Pluimdrager

Geplaatst op 12 februari 2011 - 11:21

Hoeveel zakken krijgt ieder? Let op er zijn meer mogelijkheden.

Veranderd door Safe, 12 februari 2011 - 11:22


#4

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 12 februari 2011 - 13:48

Waarom is het zo dat als er 10 willekeurige zakken van 1 tot 100 kg deze altijd in 2 groepen verdeeld kunnen worden met hetzelfde totaalgewicht? (Dit zonder de zakken open te maken!!)

Dit kan natuurlijk niet. Als het totale gewicht van de 10 zakken een oneven getal is, dan kun je dat nooit over twee personen verdelen. Maar misschien begrijp ik de vraag niet goed, of heb jij de vraag niet goed begrepen.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#5

Misty_MMS

    Misty_MMS


  • 0 - 25 berichten
  • 9 berichten
  • Gebruiker

Geplaatst op 12 februari 2011 - 19:56

Ik zal de exacte vraag even overtypen met de achtergrond informatie bij *:

In dit deel moet beweerd worden waarom we altijd een oplossing* vinden als de gewichten van de zakken gehele getallen uit 1, 2, 3, ..., 100 zijn en er 10 zakken worden gekozen.

Dť tip is natuurlijk: het duivenhokprincipe.
Dat betekent dat je enerzijds moet uitvinden op hoeveel manieren Kobus een keuze uit de zakken kan maken en anderzijds moet kijken hoeveel mogelijke aantallen kilo's hij dan pakt.

- Op hoeveel manieren kan Kobus een keus uit de 10 zakken maken?
- Som 0 kan nooit ontstaan en som 1000 ook niet. Leg dat uit. Welke sommen kunnen eventueel wel ontstaan?

Door gebruik te maken van het duivenhokprincipe en de antwoorden op de twee hierboven gestelde vragen kun je bewijzen dat het Kobus-probleem altijd een oplossing heeft.

- Bewijs dus nu dat bij elk tiental zakken met spijkers (uit 1, 2, 3, ..., 100 kg) er een tweetal groepen te maken is met hetzelfde totaalgewicht.

- op hoeveel

* het probleem:
Het Kobusprobleem. Een eerste verkenning.
Kobus werkt bij een groothandel in ijzerwaren waar zakken spijkers in gehele kiloís worden
verkocht. Op een middag bestellen twee klanten elk een grote lading spijkers. Meer spijkers
dan de ijzerhandel heeft op dat ogenblik. Dus de baas geeft Kobus de opdracht om elke klant
evenveel te verkopen. In het magazijn aangekomen, vindt Kobus tien zakken met verschillend
gewicht, die niet opengemaakt mogen worden.

3.1.1 Zakken sorteren: de eerste stappen
Stel je voor dat de tien zakken de volgende aantallen kilogram spijkers bevatten:
1, 2, 5, 6, 11, 12, 17, 18, 50, 100.
Hoe lost Kobus dan het probleem dan op? Wel, bijvoorbeeld zo:
5 + 6 + 100 = 50 + 18 + 17 + 12 + 11 + 1 + 2.
En dit is niet de enige manier! Het komt echter ook voor dat Kobus een verzameling van tien zakken
vindt die niet te splitsen is in twee groepen met hetzelfde gewicht. Een voorbeeld is eenvoudig te
vinden. Neem bijvoorbeeld 9 zakken van even gewicht en īeīen zak van oneven gewicht:
1, 2, 4, 6, 8, 10, 12, 14, 16, 18
De som van de gewichten van de groep met alleen even gewichten is dan even, terwijl de som van
de groep zakken waar de zak van 1 kilogram bij zit, dan oneven is.
Kobus leert snel en het lukt hem vaak om twee groepen samen te stellen, die hetzelfde gewicht
hebben, maar zīonder de hele voorraad te gebruiken. Dat is niet erg: de baas had namelijk niet
gezegd dat de hele voorraad weg moest.
Bij de aantallen kilogram
A : 2, 7, 13, 35, 41, 59, 72, 81, 95
en bij
B : 1, 5, 11, 23, 35, 48, 65, 69, 83, 97
vinden we bijvoorbeeld de volgende sommen. Bij A:
2 + 7 + 72 = 81
7 + 41 + 59 = 35 + 72
Bij B vinden we bijvoorbeeld:
1 + 11 + 23 = 35

Het is overigens goed om te beseffen dat we, uiteraard, niet twee keer dezelfde zak mogen
gebruiken. Stel je maar voor dat dit het rijtje zakken is:
1, 2, 7, 13, 15, 17, 24, 28, 35, 99
en dat we de volgende gelijkheid vinden:
13 + 15 + 28 = 15 + 17 + 24.
Kobus kan deze oplossing niet gebruiken, want hij kan die ene zak met 15 niet naar twee klanten
sturen. Toch heeft Kobus in dit geval wel een oplossing. Het enige wat hij hoeft te doen is de zak
met 15 weglaten:
13 + 28 = 17 + 24

We kunnen ook kijken naar situaties met andere aantallen zakken dan 10 en een ander maximumgewicht dan 100.
Als ze mogen worden gekozen uit de getallen 1, 2, . . . , 100, dan is het niet moeilijk om een
drietal of een viertal te vinden waarbij geen oplossing kan worden gevonden. Neem bijvoorbeeld
aan dat de zakken zijn: 1,26,60,100. In dit rijtje van vier getallen zijn dus niet twee groepjes te
vinden met dezelfde som. Bij maximumgewicht 100 is het Kobusprobleem voor 4 zakken dus niet
altijd oplosbaar.

#6

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 13 februari 2011 - 01:54

Bewijs dus nu dat bij elk tiental zakken met spijkers (uit 1, 2, 3, ..., 100 kg) er een tweetal groepen te maken is met hetzelfde totaalgewicht.

Kijk dat is een vraag die beduidend anders is dan de vraag uit je eerste post...

Verzin eerst welke gewichten je allemaal kan maken. Je kunt bijvoorbeeld de gewichten 1 kg t/m 100 kg met 1 zak. Je kunt de gewichten 101 kg t/m 199 kg met twee zakken. Vind nu zelf uit wat je allemaal kunt maken. Noteer het aantal verschillende gewichten dat je kunt maken.

Stel nu dat je 10 verschillende gewichten hebt. Hoeveel verschillende combinaties kan je maken met deze gewichten? Met 1 zak kun je maximaal 10 verschillende gewichten hebben. Met 2 zakken heb je maximaal 10*9/2 mogelijkheden (voor de eerst gekozen zak heb je 10 mogelijkheden, voor de tweede 9, maar je moet nog delen door twee want de volgorde van de zakken maakt niet uit: x + y = y + x). Verzin zelf hoeveel mogelijkheden je hebt voor 3 t/m 10 zakken. Tel al deze mogelijkheden op en noteer dit getal.

Vergelijk de twee genoteerde getallen en gebruik het duivenhokprincipe.

#7

Misty_MMS

    Misty_MMS


  • 0 - 25 berichten
  • 9 berichten
  • Gebruiker

Geplaatst op 13 februari 2011 - 12:41

@ EvilBro

Dankje voor je antwoord!

Ik snap alleen niet waarom je met 2 zakken bij 101 kg begint. Ik zou zeggen, met 2 zakken kan het gewicht variŽren van 2 kg tot 199. Waarschijnlijk begin je waar het aantal kilo's met 1 zak eindigt, maar waarom doe je dat?

En waarom kan 1 zak maximaal 10 verschillende mogelijkheden qua gewicht hebben? Er kan een willekeurig getal gekozen worden van 1 tot 100, dan zijn er toch 100 mogelijkheden?

#8

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 13 februari 2011 - 12:59

Ik snap alleen niet waarom je met 2 zakken bij 101 kg begint. Ik zou zeggen, met 2 zakken kan het gewicht variŽren van 2 kg tot 199. Waarschijnlijk begin je waar het aantal kilo's met 1 zak eindigt, maar waarom doe je dat?

Je wilt weten welke gewichten je allemaal kunt maken. Of je, bijvoorbeeld, 50 kg nu maakt met 1 zak, 2 zakken of 10 zakken maakt niet uit. De gewichten 1 t/m 100 had ik al (met 1 zak) dus die heb ik bij twee zakken weggelaten.

En waarom kan 1 zak maximaal 10 verschillende mogelijkheden qua gewicht hebben?

Dit is niet wat ik zei. Je hebt 10 zakken met verschillend gewicht. Met 1 zak uit deze 10 zakken, waarvan de gewichten dus vastliggen, kan je een gewicht bereiken. Voorbeeld: Als ik de zakken heb met 1, 2, 3, 4, 5, 6, 7, 8, 9 en 10 kg kan ik met 1 zak 1, 2, 3, 4, 5, 6, 7, 8, 9 of 10 kg bereiken.

Misschien is het handiger om te beginnen met drie zakken. Hoeveel gewichten kan je bereiken met 1 zak van deze 3 zakken? Het antwoord is maximaal 3. Hoeveel kun je bereiken met 2 zakken? Noem de zakken even a, b en c dan kun je dus de volgende combinaties maken:
a+b
a+c
b+c
Als deze gewichten allemaal verschillend zijn, en bovendien verschillend van gewichten die je eerder al kon bereiken, dan kan je dus drie gewichten bereiken. Je kan met 1 zak of met 2 zakken uit drie dus maximaal 3+3 = 6 gewichten bereiken.
Met 3 uit 3 kun je a+b+c bereiken, dus met 3 zakken kan je maximaal 7 gewichten bereiken.

Hopelijk is het nu duidelijk wat ik bedoel. Nu moet je het i.p.v. 3 zakken met 10 zakken uitvogelen.

#9

Misty_MMS

    Misty_MMS


  • 0 - 25 berichten
  • 9 berichten
  • Gebruiker

Geplaatst op 13 februari 2011 - 13:41

Dankje, volgens mij snap ik het.
Is het dan waar dat bij 3 zakken de mogelijkheden 10*9*8/3 zijn?

Veranderd door Misty_MMS, 13 februari 2011 - 13:46


#10

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 13 februari 2011 - 13:46

Is het dan waar dat bij 3 zakken de mogelijkheden 10*9*8/2 zijn?

Nee, want er zijn meer dan 2 mogelijkheden om 3 elementen te ordenen.

2 elementen: a+b = b+a -> 2 (= 2!)
3 elementen: a+b+c = a+c+b = b+a+c = b+c+a = c+a+b = c+b+a -> 6 (=3!)





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures