Springen naar inhoud

Berekenen van aantal noodzakelijke wegingen bij x ballen


  • Log in om te kunnen reageren

#1

Veertje

    Veertje


  • >5k berichten
  • 6713 berichten
  • VIP

Geplaatst op 03 december 2006 - 23:40

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

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

#2

eendavid

    eendavid


  • >1k berichten
  • 3751 berichten
  • VIP

Geplaatst op 03 december 2006 - 23:43

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

#3

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 03 december 2006 - 23:44

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

#4

Veertje

    Veertje


  • >5k berichten
  • 6713 berichten
  • VIP

Geplaatst op 04 december 2006 - 00:07

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

#5

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 04 december 2006 - 00:09

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.

#6

eendavid

    eendavid


  • >1k berichten
  • 3751 berichten
  • VIP

Geplaatst op 04 december 2006 - 00:21

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 :?:

#7

phi hung

    phi hung


  • >250 berichten
  • 284 berichten
  • Ervaren gebruiker

Geplaatst op 04 december 2006 - 01:57

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.

#8

Veertje

    Veertje


  • >5k berichten
  • 6713 berichten
  • VIP

Geplaatst op 04 december 2006 - 08:19

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

#9

*_gast_PeterPan_*

  • Gast

Geplaatst op 04 december 2006 - 11:50

k wegingen zijn noodzakelijk als voor het aantal munten X geldt LaTeX

Zie http://links.jstor.o...B2-B&size=LARGE

Dus voor 39 munten heb je slechts 4 wegingen nodig.

#10

phi hung

    phi hung


  • >250 berichten
  • 284 berichten
  • Ervaren gebruiker

Geplaatst op 04 december 2006 - 12:04

Dus voor 39 munten heb je slechts 4 wegingen nodig.

Dat is als je een extra munt hebt.

#11

*_gast_PeterPan_*

  • Gast

Geplaatst op 04 december 2006 - 12:12

Dus voor 39 munten heb je slechts 4 wegingen nodig.

Dat is als je een extra munt hebt.

Nee, zonder extra munt.

#12

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 04 december 2006 - 13:42

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.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures