Re: [algogeeks] Re: seperate diff types of coins
@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.
[algogeeks] Re: seperate diff types of coins
@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.
Re: [algogeeks] Re: seperate diff types of coins
@ 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 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.
Re: [algogeeks] Re: seperate diff types of coins
@payal: In this case too i think minimum number of weighing required is 3. Slightly change in my previous solution. x1+x2+x3 = 3x and y1+y2+y3 = 3y. On Wed, Jul 11, 2012 at 8:00 AM, payal gupta gpt.pa...@gmail.com 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 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 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.
