0

Here's the full problem:

We have 20 coins, 1 of which is counterfeit (too light). Determine the minimum number of weighings to find the counterfeit coin.

Okay so is used the formula $$h=\left \lceil{\log_ml}\right \rceil,$$ with $m=3$ and $l=20$. I have $m=3$ because my tree ends up having 1,2,3 against 7,8,9, 10 against 11, and 12,13,14 against 18,19,20. I also have $l=20$ so of course signify my coins. This leads to $$h=\left \lceil{\log_3 20}\right \rceil = \left \lceil{2.73}\right \rceil$$ $$\implies h=3.$$

Setting up my tree, it didn't look like this was the minimum amount of weighing. I produced a tree of height 3, but I found that 10 against 11 ended up at level 2 of my tree. Does this mean that we need a minimum of 2 weighings?

Sorry if this was put in a confusing manner. I've been awfully confused with this problem.

user30625
  • 707

2 Answers2

1

I think in 3 weighings the faulty coin can always be found out. Two seems improbable. first weighing of 7 coins each, second weighing of 3 (if one of the set of seven is faulty) or 2 coins (if both the sets of 7 coins are proper), and a final weighing of individual coins.

tpb261
  • 802
1

The question is asking for the minimum number of weighings needed to guarantee finding the counterfeit, not the minimum in which you might possibly find the counterfeit. That means if you pay for weighings in advance, how many do you need to pay for to guarantee you'll find the counterfeit without running out? You might find it in 2, but you need to be ready to do 3.

user2357112
  • 2,401