@Gupta: Given the balance scale and only the eight coins, with no knowledge of the values of their weights, here is an algorithm, probably not optimal, to label each coin x, y, a, or b, with three x's, three y's, one a, and one b. 1. Weigh the coins pairwise, c1 vs c2, then min(c1,c2) vs c3, etc., to find the lightest coin and note whether it occurs only once or three times. If the lightest coin occurs three times, label those coins x and set them aside. If it occurs once, label it a and set it aside. This takes 7 weighings. 2a. If there are seven coins remaining after step 1 (we labeled a), the heavier coin in the last weighing in step 1 is the second lightest of the eight coins. Compare the other six coins to find the lightest and note whether it occurs once or twice. If it occurs twice, label those two coins and the second-lightest from step 1 as x. If it occurs once, label that coin b. This takes 5 weighings. 2b. If there are five coins remaining after step 1 (we have labeled x), repeat the process to find the lightest of them and note whether it occurs one or three times. If the lightest coin occurs three times, label them y and set them aside. If it occurs once, label that coin a. and set them aside. This takes 4 weighings. 3a. If there are six coins remaining after step 2 (we have labeled a and b), then the heaver coin in the last weighing of step 2 is the third-lightest of the eight coins. Compare it with any four of the remaining coins. If it matches 2 of them, label those three coins x. If it matches only 1 of them, label those two coins and the one that was unweighed in this step as x.Label the remaining coins y. This takes 4 weighings. 3b. If there are four coins remaining after step 2 (we have labeled x and a), find the lightest of them and note whether the lightest occurs one or three times.Label the set of three coins y and the single coin b. This takes 3 weighings. 3c. If there are two coins remaining after step 2 (we have labeled x and y), label one of the remaining coins a and the other b. This takes no weighings. This solves the problem in at most 7 + 5 + 4 = 16 weighings. Dave
On Tuesday, July 10, 2012 9:30:31 PM UTC-5, payal gupta wrote: > @ Dave sir > the balance considered here is simple balance scale incapable of > giving any numeric reading and the we are unaware of any relationship > between x,y,a,b or any kind denominations prioirity in terms of > weights... > @navin.. > "3 of them weigh x" means 3 of the coins individually weigh x gms,it > isnt the cumulative sum of the coins as u considered ,thats what i got > from the question.. > Correct me if i'm wrong. > Could it be done it done in lesser than 8 weighings?? > > Regards, > PAYAL GUPTA. > > On 7/10/12, Dave <dave_and_da...@juno.com> wrote: > > @Gupta: You haven't defined the problem sufficiently. > > > > What type of scale do we have, a balance scale or one that gives a > numeric > > reading? > > > > Do we know x, y, a, and b, or are you just saying that one set of three > > coins weigh the same, another set of three also weigh the same but have > > different weight that the first set, and the remaining two weigh > different > > amounts than each other and the two sets? > > > > Is there any known relationship between x, y, a, and b? We can assume > > without loss of generality that x < y and a < b, but what about the > > relationships between x and a, x and b, y and a, and y and b? Knowing > more > > will allow a solution with fewer weighings than knowing less. > > > > Dave > > > > On Tuesday, July 10, 2012 12:33:47 AM UTC-5, payal gupta wrote: > > > >> You have 8 coins. 3 of them weigh x units, 3 y units, 1 a units and 1 b > >> units. They are all mixed and look identical. What are the minimum no > of > >> weighings reqd to seperate the for types of coins??? > >> > > > > -- > > You received this message because you are subscribed to the Google > Groups > > "Algorithm Geeks" group. > > To view this discussion on the web visit > > https://groups.google.com/d/msg/algogeeks/-/c41Sw3CqNz4J. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/1iUGyrlu90AJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
