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?
Laatste berichten
-
16:45
wig 8
-
15:56
Programmeren met vectoren 6
-
14:53
Straatklok loopt 5 minuten voor 12
-
23:12
speciale rel. theorie 10
-
22:36
Gravity and gravitation 4
-
22:24
[scheikunde] vraag Chemie - wat is de oplossing? 10
-
19:47
Bruine vlekken op treinaanwijzerbord 10
-
19:44
Vogels in de stad zijn goede klussers 2
-
19:12
Rood laserlicht 3
-
17:30
Herleiden afmetingen vanaf een foto 21
-
25 apr
[wiskunde] Prijs Product per KG; Alternatief Inzicht 3
-
25 apr
do-re-mi-fa-so vliegtuigen 9
-
25 apr
geen minkowski-ruimte toch? Doe ik dit nou fout? 17
-
25 apr
[natuurkunde] kroon van koning op Syracuse 10
-
25 apr
2013 – Augustus Vraag 3 3
-
24 apr
Vraag 2009 Juli Vraag 5 5
-
24 apr
positie 2
-
24 apr
Schroefdraad berekening 8
-
24 apr
[scheikunde] Kan chloorgas de geleiding van elektriciteit belemmeren? 9
-
23 apr
Weerfrustratie 9
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
Duivenhokprincipe
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
-
- Berichten: 7.068
Re: Duivenhokprincipe
Ik heb ernstig het vermoeden dat je de vraag verkeerd hebt gegeven. Kun je de exacte vraag eens overtypen?
-
- Pluimdrager
- Berichten: 10.058
Re: Duivenhokprincipe
Hoeveel zakken krijgt ieder? Let op er zijn meer mogelijkheden.
-
- Berichten: 2.906
Re: Duivenhokprincipe
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.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!!)
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }
-
- Berichten: 9
Re: Duivenhokprincipe
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 kilos 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.
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 kilos 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.
-
- Berichten: 7.068
Re: Duivenhokprincipe
Kijk dat is een vraag die beduidend anders is dan de vraag uit je eerste post...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.
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.
-
- Berichten: 9
Re: Duivenhokprincipe
@ 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?
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?
-
- Berichten: 7.068
Re: Duivenhokprincipe
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.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?
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.En waarom kan 1 zak maximaal 10 verschillende mogelijkheden qua gewicht hebben?
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.
-
- Berichten: 9
Re: Duivenhokprincipe
Dankje, volgens mij snap ik het.
Is het dan waar dat bij 3 zakken de mogelijkheden 10*9*8/3 zijn?
Is het dan waar dat bij 3 zakken de mogelijkheden 10*9*8/3 zijn?
-
- Berichten: 7.068
Re: Duivenhokprincipe
Nee, want er zijn meer dan 2 mogelijkheden om 3 elementen te ordenen.Is het dan waar dat bij 3 zakken de mogelijkheden 10*9*8/2 zijn?
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!)
