[math-fun] Yet another weighing problem
In the Numberplay blog of the NY Times, they posed the following problem: You have 14 identical appearing coins, 7 of which are heavy (of the same weight), and 7 are light (of the same weight). You can't distinguish them by appearance or feel. You have a special kind of balance available to you: you can insert piles of coins on the left side and the right. The machine will either report that the two piles are equal in weight -- in which case it will return all the coins. If it reports that one side is heavier than the other, it will exact a tribute from the heavy side -- it will take one of the heavy side's coins at random, and return all the rest. The original question is: devise a strategy of weighing which will allow you to always exhibit one of the heavy coins. So the obvious generalization is to consider pairs (m,n) of positive integers with m >= n, which means that you have m coins in total of which n are heavy and m-n are light. For which (m,n) can you devise a strategy as above? Call such pairs (m,n) *feasible*. I would think (is there a simple proof?) that if (m,n) is feasible then so is (m,n+1) (provided n+1 <= m). If so, this would seem to give a sequence for OEIS (which is probably already there). One thing that the original problem didn't ask is -- devise a strategy (which might allow you to use random choice) for which the expected number of weighings is smallest. There are also two alternatives 1) You're allowed to label the individual coins, which are preserved through the weighings. 2) You're not allowed to label. Victor
Neat type of problem! It seems to me the easy reduction is that if you can solve (H heavy, L light) coins, then you can also solve (H+1, L+1): from (H+1, L+1) you can weigh random pairs of single coins against one another until you find two whose weights differ, at which point the scale keeps the heavier of the two, and you can discard the returned lighter one, getting to (H, L). Ah -- if you do the same one-on-one weighings and *don't* throw away the identified light coin, you reduce to (H,L) from (H+1,L), which is what Victor intuited and asked for a proof of. I'm not sure I understand the rules of the "You're not allowed to label" alternative. If I can tell which coins came from the heavier / lighter pan after a weighing, then I can do (2, 2), and therefore (n, n) for n>=2. Rather than minimizing expected number of weighings, I'd like to maximize the number of heavy coins you can exhibit at the end. With (7, 7) you can certainly end up holding one heavy coin, but can you end up with two? Three? --Michael On Sat, Jul 27, 2013 at 10:21 AM, Victor Miller <victorsmiller@gmail.com>wrote:
In the Numberplay blog of the NY Times, they posed the following problem:
You have 14 identical appearing coins, 7 of which are heavy (of the same weight), and 7 are light (of the same weight). You can't distinguish them by appearance or feel. You have a special kind of balance available to you: you can insert piles of coins on the left side and the right. The machine will either report that the two piles are equal in weight -- in which case it will return all the coins. If it reports that one side is heavier than the other, it will exact a tribute from the heavy side -- it will take one of the heavy side's coins at random, and return all the rest.
The original question is: devise a strategy of weighing which will allow you to always exhibit one of the heavy coins.
So the obvious generalization is to consider pairs (m,n) of positive integers with m >= n, which means that you have m coins in total of which n are heavy and m-n are light. For which (m,n) can you devise a strategy as above? Call such pairs (m,n) *feasible*. I would think (is there a simple proof?) that if (m,n) is feasible then so is (m,n+1) (provided n+1 <= m). If so, this would seem to give a sequence for OEIS (which is probably already there).
One thing that the original problem didn't ask is -- devise a strategy (which might allow you to use random choice) for which the expected number of weighings is smallest. There are also two alternatives
1) You're allowed to label the individual coins, which are preserved through the weighings.
2) You're not allowed to label.
Victor _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
My solution of the NYT puzzle was exactly the same as Michael's: Reduce (7,7) to (6,6) … until you get to (2,2), then you have to do a 2 vs. 2 weighing and, if they balance, a 1 vs. 1. I'm still puzzled why the original puzzle asked for (7,7). Maybe Victor was as well, and asked the obvious question: For given L, how small can H be for (H,L) to be feasible? For example, (3,3) is feasible but (2,3) is not. -Veit On Jul 27, 2013, at 8:12 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Neat type of problem!
It seems to me the easy reduction is that if you can solve (H heavy, L light) coins, then you can also solve (H+1, L+1): from (H+1, L+1) you can weigh random pairs of single coins against one another until you find two whose weights differ, at which point the scale keeps the heavier of the two, and you can discard the returned lighter one, getting to (H, L).
Ah -- if you do the same one-on-one weighings and *don't* throw away the identified light coin, you reduce to (H,L) from (H+1,L), which is what Victor intuited and asked for a proof of.
I'm not sure I understand the rules of the "You're not allowed to label" alternative. If I can tell which coins came from the heavier / lighter pan after a weighing, then I can do (2, 2), and therefore (n, n) for n>=2.
Rather than minimizing expected number of weighings, I'd like to maximize the number of heavy coins you can exhibit at the end. With (7, 7) you can certainly end up holding one heavy coin, but can you end up with two? Three?
--Michael
On 7/28/13, Veit Elser <ve10@cornell.edu> wrote:
My solution of the NYT puzzle was exactly the same as Michael's: Reduce (7,7) to (6,6) … until you get to (2,2), then you have to do a 2 vs. 2 weighing and, if they balance, a 1 vs. 1.
I'm still puzzled why the original puzzle asked for (7,7). Maybe Victor was as well, and asked the obvious question: For given L, how small can H be for (H,L) to be feasible? For example, (3,3) is feasible but (2,3) is not.
-Veit
On Jul 27, 2013, at 8:12 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Neat type of problem!
It seems to me the easy reduction is that if you can solve (H heavy, L light) coins, then you can also solve (H+1, L+1): from (H+1, L+1) you can weigh random pairs of single coins against one another until you find two whose weights differ, at which point the scale keeps the heavier of the two, and you can discard the returned lighter one, getting to (H, L).
Ah -- if you do the same one-on-one weighings and *don't* throw away the identified light coin, you reduce to (H,L) from (H+1,L), which is what Victor intuited and asked for a proof of.
I'm not sure I understand the rules of the "You're not allowed to label" alternative. If I can tell which coins came from the heavier / lighter pan after a weighing, then I can do (2, 2), and therefore (n, n) for n>=2.
Rather than minimizing expected number of weighings, I'd like to maximize the number of heavy coins you can exhibit at the end. With (7, 7) you can certainly end up holding one heavy coin, but can you end up with two? Three?
--Michael
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Sun, Jul 28, 2013 at 12:24 AM, Veit Elser <ve10@cornell.edu> wrote:
My solution of the NYT puzzle was exactly the same as Michael's: Reduce (7,7) to (6,6) … until you get to (2,2), then you have to do a 2 vs. 2 weighing and, if they balance, a 1 vs. 1.
Actually my (2,2) solution was "Weigh 2 vs 2 until there's an imbalance", but yours is more efficient, as mine might take three weighings.
I'm still puzzled why the original puzzle asked for (7,7). Maybe Victor was as well, and asked the obvious question: For given L, how small can H be for (H,L) to be feasible? For example, (3,3) is feasible but (2,3) is not.
More natural questions: What's the first feasible (H,L) with L > H? How about with L >= H + k for k=1, 2, 3, ...? Must some (H,L) work for any k? --Michael -- Forewarned is worth an octopus in the bush.
participants (4)
-
Fred Lunnon -
Michael Kleber -
Veit Elser -
Victor Miller