|
||
Title: 5 coins and 5 weighings Post by Altamira_64 on Jan 13th, 2012, 12:51pm We have 5 coins of identical shape and volume, but with different weights, 10, 20, 30 40 and 50 grams. How can we determine the weight of each coin by using a balance scale and only in 5 weighings? Just to clarify that we are not looking for the exact weight of each, but want to sort them by order of weight. |
||
Title: Re: 5 coins and 5 weighings Post by towr on Jan 14th, 2012, 5:28am I could do it in seven, I think. But that's with limiting weighing to one coin/ball against another. I don't readily see how to improve that by weighing more of them at the same time. If push came to shove, it'd be easy enough to have a computer do a brute force search for the answer, though. But 5 weighings is not a lot; there are 120 different orders for 5 coins, and distinguishing between them requires 7 bits of information; that's close to the maximum you can get from 5 weighings. |
||
Title: Re: 5 coins and 5 weighings Post by SWF on Jan 14th, 2012, 7:35am on 01/13/12 at 12:51:25, Altamira_64 wrote:
You ask to determine the weight of balls, but only give information pertaining to coins. :-/ I would try starting with 2 vs. 2. That way there are 3 possible results for the first weighing. |
||
Title: Re: 5 coins and 5 weighings Post by Grimbal on Jan 16th, 2012, 8:19am I think I wouldn't even need a scale to order the coins/balls by weight. |
||
Title: Re: 5 coins and 5 weighings Post by Altamira_64 on Jan 17th, 2012, 12:50pm First of all, I made a mistake and was referring to balls instead of coins. I also changed the wording to make a clarification. See above. |
||
Title: Re: 5 coins and 5 weighings Post by Altamira_64 on Jan 19th, 2012, 11:14am How come? on 01/16/12 at 08:19:11, Grimbal wrote:
|
||
Title: Re: 5 coins and 5 weighings Post by towr on Jan 19th, 2012, 11:35am Drop them in water. The faster they sink, the heavier (higher density) they must be. But that's not in the spirit of the problem.. |
||
Title: Re: 5 coins and 5 weighings Post by aicoped on Jan 21st, 2012, 8:00am I don't see an elegant way to solve it, but I brute force was able to prove it possible if the first weighing of 2v2 was equal. I imagine similar logic could be used if side a weighed more or less than b but I ran out of time. |
||
Title: Re: 5 coins and 5 weighings Post by towr on Jan 21st, 2012, 10:45am So far I know that you can't do it with five pre-picked weighings; if it's possible at all, you'll need to make different choices depending on the results of earlier weighings. (Perhaps not surprising; but it is the easiest case to test.) [edit]I've found a solution, but it's not pretty. I've also ruled out solutions starting with something other than starting with 2vs2 [/edit] |
||
Title: Re: 5 coins and 5 weighings Post by aicoped on Jan 21st, 2012, 3:23pm yes I agree. I was forced to do a ton of if then in my one case i solved for, and I stopped figuring the rest could be solved as well. |
||
Title: Re: 5 coins and 5 weighings Post by Altamira_64 on Jan 22nd, 2012, 1:09am I started by weighing 2 vs 2, but we have 15 different possibilities: 1st plate 2nd plate 10+20=30, 30+40=70 10+20=30, 30+50=80 10+20=30, 40+50=90 10+30=40, 20+40=60 10+30=40, 20+50=70 10+30=40, 40+50=90 10+40=50, 20+30=50 10+40=50, 20+50=70 10+40=50, 30+50=80 20+30=50, 10+50=60 20+30=50, 40+50=90 10+50=60, 20+40=60 10+50=60, 30+40=70 20+40=60, 30+50=80 30+40=70, 20+50=70 In cases 7, 12 and 15 the scale balances, but then what? |
||
Title: Re: 5 coins and 5 weighings Post by towr on Jan 22nd, 2012, 1:59am If the a,b equal c,d, then in my solution the next weighing is (Note that if they're not equal, you can transform the < case to the > case by swapping the names for a,b and c,d; so there are ways to simplify the solution. I haven't really explored that yet, because my solution is not in a very useful format.) [edit]Attached somewhat cleaned up solution. Read "00112=" as first two balls in left pan (0), next two in right pan (1), last ball not on the scales (2), result of weighing: equal.[/edit] |
||
Title: Re: 5 coins and 5 weighings Post by Altamira_64 on Jan 29th, 2012, 2:56am I don't quite understand your solution, although I trust it is correct! In some cases (the "=" cases), you have 3 zeroes or 3 aces. How is this possible? on 01/22/12 at 01:59:21, towr wrote:
|
||
Title: Re: 5 coins and 5 weighings Post by towr on Jan 29th, 2012, 7:38am I don't see any cases with three 0's or three 1's that have = as a result; that would have been a problem if it occurred since it's impossible. Maybe it'll be clearer if I translate the solution to a more legible format, but that's a lot of work, so it may take a while. |
||
Title: Re: 5 coins and 5 weighings Post by towr on Jan 29th, 2012, 11:04am I've attached a cleanup version of the solution I found. I also put in a few simplifications. There are probably simpler solutions, because my program simply stopped at the first one, rather than looking for the simplest one. Starting with AB vs CD followed by AC vs BD allows a bit more simplification, for starters. |
||
Title: Re: 5 coins and 5 weighings Post by rmsgrey on Jan 30th, 2012, 9:24am on 01/22/12 at 01:59:21, towr wrote:
How do you weigh c on both sides at once? And how do you get any useful information out of proving that c has a positive weight? Or is this an obvious typo? |
||
Title: Re: 5 coins and 5 weighings Post by towr on Jan 30th, 2012, 10:08am It's an obvious typo. Should be a,b,c vs d,e. And I see I made a similar mistake in my last attachment. |
||
Title: Re: 5 coins and 5 weighings Post by Altamira_64 on Jan 30th, 2012, 12:44pm Great job towr! However, I have a question: As far as I can tell, all possible combinations of 3 coins vs 2 are 10 (10 20 30 vs 40 50 etc). In all of these cases, we can have either < or >. We cannot have "=" with the given numbers 10, 20, 30, 40 and 50. In your solution, you have two cases where you consider the "=" result. One of them results to 43125 (which does not correspond to the A+C+D vs B+E) and the other is the "=" after the 4th weighing (A+B+D vs C+E), which results to either "=" or "<", and the "=" then results to A+C+E vs B+D, giving us either 34521 or 25341. |
||
Title: Re: 5 coins and 5 weighings Post by towr on Jan 30th, 2012, 1:20pm Yup, those are another two errors that snuck in when I translated the output of my program into a more readable format. I've fixed them in the pdf now. There might be more errors in that image, though; so when in doubt check the original list. |
||
Title: Re: 5 coins and 5 weighings Post by Altamira_64 on Feb 1st, 2012, 9:28am Nice solution! I wish I had your patience! I gave up after the first weighing! Thanks! |
||
Title: Re: 5 coins and 5 weighings Post by Grimbal on Feb 2nd, 2012, 9:10am Computers are very patient. |
||
Title: Re: 5 coins and 5 weighings Post by brac37 on Apr 20th, 2012, 1:36pm Just a stupid question. If the weights are 10, 20, 30,40, 50, then you do not need a balance scale to order them. Can you also order them in five weightings if you only know that the weights are an arithmetical progression. In that case, each weighting must have the same number of coins on each scale. Probably not, but maybe it can be done in six weightings. |
||
Title: Re: 5 coins and 5 weighings Post by towr on May 26th, 2012, 3:32am on 04/20/12 at 13:36:35, brac37 wrote:
|
||
Title: Re: 5 coins and 5 weighings Post by jousha22 on Oct 20th, 2013, 11:42pm While you have a balance scale and 16 coins, 2 of which are counterfeit. The counterfeits weigh the same as each other, but this time you don't know whether they're light or heavy. Can you determine the counterfeits (as well as their comparative weight) in 5 weighings? |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |