Sjoerd Job schreef:Als we niet weten of het om zwaarder of lichter gaat wordt het lastig.
In de oorspronkelijke vraag ging het over foutief bolletje maar zei niets erover dat het foutief zwaarder of lichter dan de anderen was.Echt lastig!
Het zelfde vraag voor 12 bolletjes in 3 keer lukt het wel.Ook hier weten we niet of het foutief zwaarder of lichter is.
1-2-3-4_______5-6-7-8_______9-10-11-12
Stap1: We nemen twee groepen ervan om te vergelijken, nl.
1-2-3-4_____5-6-7-8
Er zijn er 2 mogelijkheden:Of ze gelijk zijn of ongelijk.(Notatie G:Gelijk, OG:Ongelijk)
Als ze G zijn , is het gemakkelijk te bepalen.Ik neem aan dat ze OG zijn van elkaar ( voor het moelijk)
In dit geval hebben we er weer ook 2 mogelijkheden: één groep is zwaarder ,andere lichter.(Notatie Z:Zwaar, L:Licht, N:Normaal)
Z={1,2,3,4}
L={5,6,7,8}
N={9,10,11,12}
Stap2:We regelen nieuwe groepen van bovenstaande groepen
Z,Z,Z,L,L----L,L------N,N,N,N,Z
1,2,3,5,6----7,8-----9,10,11,12,4
we vergelijken nu: 1,2,3,5,6------9,10,11,12,4
Er zijn er weer 2 mogelijkheden:G of OG
Als ze gelijk zijn aan elkaar is het gemakkelijk om te bepalen welk foutief is.Voor het moeilijke geval kies ik voor OG:
Deze keer hebben wij er weer 2 mogelijkheden:Z en L
a)Z={1,2,3,5,6} en L={9,10,11,12,4}
In dit geval 4=N (4 was een element van Z maar hier L, dus hij kan geen element van L zijn, indien L=N is kan het wel, en hierdoor {5,6,7,8}=L=N en foutief zit nu in {1,2,3}, als stap3 vergelijken we 2 willekeurige bolletjes ervan en bepalen foutief)
b)L={1,2,3,5,6} en Z={9,10,11,12,4}
In dit geval N={1,2,3,9,10,11,12} , foutief is binnen {5,6,4}
als stap3 vergelijken we 5 en 6 met elkaar:
weer 2 mogelijkheden:G en OG
als het G is, foutief is 4, als het OG is is het lichtere foutief.
Ik heb een beetje verkoort anders zou het heel lang duren om alle mogelijkheden te vertonen.
De vraag is:"Wat is algemene regel (of algoritme) om sortgelijke problemen te benaderen "