Berekenen van aantal noodzakelijke wegingen bij x ballen

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer

Bericht 03-12-'06, 23:40

Veertje

Gebruikersavatar
Berichten: 6.716

Berekenen van aantal noodzakelijke wegingen bij x ballen

In het raadsel topic van het WSF cafe had ik het volgende raadsel geplaatst:

We hebben een balans en 8 lottoballen genummerd 1 t/m 8 waarvan er 1 anders is dan de andere 7. Hij weegt meer of minder. Na hoeveel keren wegen kun je bepalen welke bal het is, en of hij lichter of zwaarder is? Het antwoord is 3, gegeven door Johan2 als volgt:
1e: Links: 1, 2, 3 Rechts 4, 5, 6.  

L=R => 7 of 8 is lichter of zwaarder, wat eenvoudig in 2 keer is te wegen.  

Links is zwaarder => 1 of 2 of 3 is zwaarder, of 4 of 5 of 6 is lichter.  

2e: Links 1, 4. Rechts 2, 5.  

L=R=> 3 is zwaarder of 6 is lichter, wat valt te weten door 3 of 6 te vergelijken met een "normale" bal als b.v. 7 (=3e).  

Links is zwaarder => 1 is zwaarder of 5 is lichter, wat weer door vergelijking van één van beide met een "normale" bal valt uit te maken.  

3 maal dus.
Als je hetzelfde met 10 ballen probeert te doen lukt dat pas met 4 keer wegen. Met 6 ballen moet het nog steeds in 3 keer, met 4 ballen kan het in 2 keer, met 2 ballen lukt het helemaal niet.

Nu vroeg ik me af of er hier een wiskundige formule voor te bedenken is waarbij je bij een x aantal ballen kunt uitrekenen hoe vaak je moet wegen om de gezochte bal te vinden (en te bepalen of hij lichter of zwaarder is).
I am not young enough to know everything - Oscar Wilde
Omhoog

Bericht 03-12-'06, 23:43

eendavid

Gebruikersavatar
Berichten: 3.751

Re: Berekenen van aantal noodzakelijke wegingen bij x ballen

ik ga me niet wagen aan het antwoord, interessante vraag.

wel een methode om het bij 10 ballen in 3 keer te doen

L:1,2,3 R:4,5,6

*stel verschillend =>gebruik voorgaande methode

*stel gelijk

L:7 R:8

**stel verschillend => L:7 R:1, als verschillend: antwoord = 7, als gelijk: antwoord =8

**stel gelijk => L:9 R:7, als verschillend: antwoord = 9, als gelijk: antwoord = 10
Omhoog

Bericht 03-12-'06, 23:44

TD

Gebruikersavatar
Berichten: 24.578

Re: Berekenen van aantal noodzakelijke wegingen bij x ballen

Zie onder andere dit document (pdf) voor muntjes ipv ballen [rr]
"Malgré moi, l'infini me tourmente." (Alfred de Musset)
Omhoog

Bericht 04-12-'06, 00:07

Veertje

Gebruikersavatar
Berichten: 6.716

Re: Berekenen van aantal noodzakelijke wegingen bij x ballen

eendavid schreef:ik ga me niet wagen aan het antwoord, interessante vraag.

wel een methode om het bij 10 ballen in 3 keer te doen

L:1,2,3    R:4,5,6

*stel verschillend =>gebruik voorgaande methode

*stel gelijk

L:7          R:8

**stel verschillend => L:7  R:1, als verschillend: antwoord = 7, als gelijk: antwoord =8

**stel gelijk => L:9  R:7, als verschillend: antwoord = 9, als gelijk: antwoord = 10
Ja maar, in dat laatste geval weet je dan niet of bal 10 lichter of zwaarder is want die is niet gewogen. [rr]
I am not young enough to know everything - Oscar Wilde
Omhoog

Bericht 04-12-'06, 00:09

Rogier

Gebruikersavatar
Berichten: 5.679

Re: Berekenen van aantal noodzakelijke wegingen bij x ballen

Veertje schreef:Als je hetzelfde met 10 ballen probeert te doen lukt dat pas met 4 keer wegen. Met 6 ballen moet het nog steeds in 3 keer, met 4 ballen kan het in 2 keer, met 2 ballen lukt het helemaal niet.

Nu vroeg ik me af of er hier een wiskundige formule voor te bedenken is waarbij je bij een x aantal ballen kunt uitrekenen hoe vaak je moet wegen om de gezochte bal te vinden.
Een exacte formule lijkt me lastig, maar het minimale aantal beurten is in ieder geval log(2x)/log(3) afgerond naar boven. Soms nog een beurt extra.

(misschien is het log(2x+2)/log(3), ben er nog niet helemaal uit)

Je kunt dat als volgt beredeneren: met x ballen zijn er 2x mogelijkheden: x omdat je x ballen hebt, en maal 2 omdat de afwijkende bal lichter of zwaarder kan zijn. Dus met 12 ballen zijn er 24 mogelijkheden. Als je gaat wegen met zo'n balans zijn er 3 uitkomsten: links is lichter dan rechts, links is zwaarder dan rechts, of links en rechts zijn even zwaar. Door je wegingen slim te verdelen kun je daarmee de mogelijkheden steeds in 3'en verdelen. Anders gezegd: met één weegbeurt kun je maximaal 3 situaties onderscheiden, met twee wegingen 9, met drie 27, en met n maximaal 3n.

24 situaties (12 ballen) zijn dus theoretisch allemaal te onderscheiden binnen 3 wegingen. 26 (13 ballen) ook nog. 28 (14 ballen) niet meer. Alleen nu wil het geval dat je 13 ballen niet na 1 weegbeurt kunt splitsen in 3 situaties met ieder max 9 mogelijkheden, dus voor 13 ballen heb je toch 4 beurten nodig. 12 ballen kan wel in 3.
In theory, there's no difference between theory and practice. In practice, there is.
Omhoog

Bericht 04-12-'06, 00:21

eendavid

Gebruikersavatar
Berichten: 3.751

Re: Berekenen van aantal noodzakelijke wegingen bij x ballen

Ja maar, in dat laatste geval weet je dan niet of bal 10 lichter of zwaarder is want die is niet gewogen.   [rr]


ik zou mij eens moeten leren concentreren hier op dit wiskundeforum :?:
Omhoog

Bericht 04-12-'06, 01:57

phi hung

Gebruikersavatar
Berichten: 284

Re: Berekenen van aantal noodzakelijke wegingen bij x ballen

Als je hetzelfde met 10 ballen probeert te doen lukt dat pas met 4 keer wegen.
Met 12 ballen kan het in drie keer:

Klik hier
met 2 ballen lukt het helemaal niet.
Met twee ballen hoef je niet te wegen.
Omhoog

Bericht 04-12-'06, 08:19

Veertje

Gebruikersavatar
Berichten: 6.716

Re: Berekenen van aantal noodzakelijke wegingen bij x ballen

Veertje schreef:Als je hetzelfde met 10 ballen probeert te doen lukt dat pas met 4 keer wegen.
Met 12 ballen kan het in drie keer:

Klik hier
Verhip, en ik had nog wel gezocht voordat ik het raadsel uberhaupt postte. Mmm, volgende keer toch wat handigere zoekopdracht formuleren.

Maar Math oplossing was niet helemaal juist zoals je zelf al zei (C4!). Die van TD klopt wel helemaal.
met 2 ballen lukt het helemaal niet.
Met twee ballen hoef je niet te wegen.
Je hebt natuurlijk helemaal gelijk! [rr] En Johan2 wees me erop dat je met 4 ballen nog steeds 3 wegingen nodig hebt.
I am not young enough to know everything - Oscar Wilde
Omhoog

Bericht 04-12-'06, 11:50

PeterPan

Re: Berekenen van aantal noodzakelijke wegingen bij x ballen

k wegingen zijn noodzakelijk als voor het aantal munten X geldt \(\frac{3^{k-1}-3}{2} < X \leq \frac{3^{k}-3}{2}\)

Zie http://links.jstor.org/sici?sici=0002-9890...B2-B&size=LARGE

Dus voor 39 munten heb je slechts 4 wegingen nodig.
Omhoog

Bericht 04-12-'06, 12:04

phi hung

Gebruikersavatar
Berichten: 284

Re: Berekenen van aantal noodzakelijke wegingen bij x ballen

Dus voor 39 munten heb je slechts 4 wegingen nodig.
Dat is als je een extra munt hebt.
Omhoog

Bericht 04-12-'06, 12:12

PeterPan

Re: Berekenen van aantal noodzakelijke wegingen bij x ballen

PeterPan schreef:Dus voor 39 munten heb je slechts 4 wegingen nodig.
Dat is als je een extra munt hebt.
Nee, zonder extra munt.
Omhoog

Bericht 04-12-'06, 13:42

Rogier

Gebruikersavatar
Berichten: 5.679

Re: Berekenen van aantal noodzakelijke wegingen bij x ballen

phi hung schreef:
PeterPan schreef:Dus voor 39 munten heb je slechts 4 wegingen nodig.
Dat is als je een extra munt hebt.
Nee, zonder extra munt.
Hoe doe je dat dan?

Volgens mij kan dat niet hoor. Als je er eerst 13 tegen 13 weegt, en ze zijn even zwaar, hou je nog 13 munten en 3 beurten over, dat is te weinig. Als je er 14 tegen 14 weegt, en ze zijn niet even zwaar, hou je nog 28 mogelijkheden en eveneens 3 beurten over, dat lijkt me ook te weinig.
In theory, there's no difference between theory and practice. In practice, there is.
Omhoog
Reageer

Terug naar “Wiskunde”