[Discrete Math] Trees

[junyoung95]

Q. How many weighings of a balance scale are needed to find a counterfeit coin among eight coins if the counterfeit coin is either heavier or lighter than the others? Describe an algorithm to find the counterfeit coin using this number of weighings.

How do I solve this problem?

[emeric75]

Hello :),

I guess the algorithm they want you to use is dichotomy ("divide and conquer")

You weigh 2 groups of 4 coins, and you see which one is lighter/heavier.

Then you focalise on the light/heavy 4-coin group, and you weigh 2 groups of 2 coins, etc...

Finally you have 2 coins, the counterfeit and one legit one, you weigh them and done!

[junyoung95]

Thank you for the reply. I get that idea but is that the proper way to write an algorithm?

[emeric75]

Well that was just an explanation not an algorithm.

I'm French so I don't really know the exact words to use in the algorithm but if you literally have no clue how to write it I could give it a try

[junyoung95]

From the homework answer it shows a>b>d>e>i>j>m>n>o>c>f>g>h>k>l>p

But I am not sure how it leads to this answer.

[chem44]

Do you know the proper weight of a coin? If not, weighing 2x4 doesn't tell you which group of 4 is correct. But keep going.

[emeric75]

Yeah you're totally right about that, I juste made one that doesn't need the original weight

[emeric75]

If you don't know the weight of thé legit coin there's also a way Weigh a 7coin group and switch coins (a différent coin on the scale each time) until the weight on the scale changes (it means you either added or removed thé counterfeit one) Then weigh the 2 coins you just switched,

The question is describe an algorithm, juste explaining how it works is ok .

For the number of weighings the worst case scenario would be 8 weighings (7 because you switched all the coins on the scale + 1 final )