Understanding Strategy:Minimum number of weighing to find the faulty bag

Question

If Mr M buys $n$ bags of sands, each weighing a unit each except one bag. What is the minimum number of weighing is required to determine the faulty bag when:

1. a two pan balance is used?

2. a spring balance is used?

In my module they have given some sort shortcut to evaluate the result which is for $n$ bags: In first case if $3^a \lt n \lt 3^{a+1}$, then the minimum number of weighing required is $a+1$. In the second case, we need $2^a \lt n \lt 2^{a+1}$ which gives the minimum of $a+1$ weighing. However I couldn't follow up this approach.

Could anybody explain this approach to me?Also,in absence of the information about whether the faulty bag is heavy or lighter than the other ones,how exactly could I pin-point the faulty bag?

Answer 1

For a two pan balance, you can split the bags into three batches, A, B, and C. You weigh batch A against B (which had better have the same number of bags in them). If they balance, the faulty bag is in batch C. Are told whether the faulty bag is heavy or light? If so, you know which of A or B it is in. So one weighing decreases the group of possible bags by a factor 3.

If a spring balance is used, you can put half the bags on the scale at one time. If the result is an exact number of pounds, the faulty one is not on the scale. If the result is not an exact number of pounds, the faulty one is on the scale. The number of possible bags decreases by a factor of 2.

Addition: With 8, weigh A1, A2, A3 vs B1, B2, B3. If they balance, all six are good, so weigh A1 vs C1, then A1 vs C2 and you know which is wrong and how. If they don't balance, say the A's outweigh the B's. Weigh A1, B1 against A2, B2. If they balance, weigh A3 against C1 and you know the answer. If not, assume A1, B1 is heavy. Then either A1 is heavy or B2 is light. Weigh A1 against C1. In all cases we find the bad bag and know whether it is heavy or light in three weighings. You can actually do better: see the 12 coins problem for 12 coins in three weighings.

Answer 2

The problem is not very well posed, I think.

The minimum number of weighings you would need to discover the faulty bag in the first case is 2: pick two bags at random and compare them. If you happen to "hit" on the faulty bag, they will not balance; then weigh the first of the two bags against one of the bags that you haven't weighted before. If they balance, the faulty bag is the second bag you picked; if they don't balance, then the first bag is the faulty one.

Likewise, you would need a minimum of one weighing with a spring loaded scale to determine a faulty bag: pick a bag at random, and weigh it. If the weight is not exactly 1 pound, then that's the faulty bag, and you're done.

Of course, the problem is that these methods are not guaranteed to find the faulty bag in "small" number of steps; the second method would require at best 1 weighing, at worst $n-1$ weighings, and the expected number of weighings is probably somewhere near $\lceil\frac{n-1}{2}\rceil$. Rather, the problem is asking you for a systematic method which will determine the faulty bag and which is, in some sense, "optimal" (probably relative to the expected number of weighings), and asking you what is the "best case scenario" in those algorithms. But you probably don't have the tools necessary to determine what method is "optimal", which makes the question rather ill-posed in my opinion.

That said, Ross's answer is probably the intended solution: if $3^a \lt n\leq 3^{a+1}$, divide the sacks into three piles with $3^{a}$, $3^{a}$, and $n-2\times 3^a$ sacks each, and weight the first two. In the best case scenario, they balance and you can eliminate all those bags, leaving you with $3^{a-1} \lt n-2\times 3^a \leq 3^a$ bags to consider. Lather, rinse, and repeat. The "bad" case occurs if the bags don't balance, because then you will need extra weighings to determine the faulty bag (but once you determine if it is heavy or light, you will be able to determine which third of the sacks has the faulty bag in each subsequent step). In the best-case-throughout scenario, the bags balance in each step, so you always eliminate two-thirds of the bags in each step. Since $3^a\lt n\leq 3^{a+1}$, it will take you $a+1$ weighings to find the faulty bag.

How do we determine if the faulty bag is light or heavy? Suppose that somewhere along the line (but not at the first weighing), the bunch in pan A does not balance with the bunch in pan B. Because every bag you've set aside so far is known to be "good", you have enough known-to-be-good bags to compare against the bunch in pan A. Compare them. If they balance, then the faulty bag is in the bunch that was in pan B, and it is heavy if pan B was heavier than pan A, and lighter if pan A was heavier than pan B. Now proceed with the bunch in pan B as before, but now you know whether the faulty bag is heavy or light, so at each subsequent weighing you know exactly which third contains the faulty bag. If the bunch in A does not balance with the known-to-be-good bags, then you know A contains the faulty bag, and you know that it is light if bunch A is lighter, heavy if bunch A is heavy.

This will work always, unless you are at your first weighing, and the bunch of "set-aside" bags is insufficient to compare with all of bunch A or bunch B. In that case, take half (or as near to one half as you can) the sacks in A, and move them "out"; take one half of the sacks in B, and move them to pan A; and then take enough known-to-be-good sacks from bunch C, and place them in B. Three things can happen: (i) the pans are balanced now; then the faulty bag is in the bunch of sacks from A you took out, and you know if it is heavy or light (depending on whether A was heavier than B or lighter than B, respectively); proceed as before. (ii) The pans are unbalanced as they were before; then the faulty bag is in the bunch of sacks from A and B that you did not move; you still don't know if the faulty bag is heavy or light (you'll have to figure it out later), but you know which third of the sacks to proceed with for the next step. Or (iii) The pans are unbalanced, but in the opposite way than they were before; this can only happen if the faulty sack is among the bunch of sacks you moved from B to A; and this will tell you if it is heavy or light.

Once you know if the faulty sack is heavy or light, at each stage you only need one weighing to know which third contains the faulty sack.

In the second case, with $2^a \lt n \leq 2^{a+1}$, you divide the bags into a bunch with $2^a$ bags and one with $n-2^a\leq 2^a$ bags. Weight the first: if the result is $2^a$ units, these are all "good bags", and the bad bag is in the second pile. If the result is not $2^a$ units, then the bad bag is in this bunch. Eliminate the bags that we know are "good", lather, rinse, and repeat. It will take you $a+1$ steps to find the faulty bag, since each step eliminates about half the remaining bags.