This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.

this is what i got couple of weeks ago. Some of you probably know about it. There are 9 rectangles, 8 of which are of same weight and 1 with a different weight. You are given a weight machine(kind of like pendulum) on which you can place the items to pick the one with the odd weight(the one that is not same as 8 others). Give the least number of times before which you can find the item that is different in weight. You can place the items anywhere on the weight measurement(at the center, or on the left, on the right or in all the three places in any combination). I need to be given couple of tips before I could nail it. Dan. [ February 25, 2004: Message edited by: Chris Daniel ]

looks like to me you need 4 times in worst case. there are many ways to do it: put 3 on each side, or 4 at each side, to start with. but the odd one may be heavier or lighter than normal, so it takes more times than you may think. [ February 24, 2004: Message edited by: Ken Smart ]

I'm going to cheat a bit. I already know the solution with 13 balls is 3, so I'm going to say that it can't take more than 3 weighings. It's also going to take at least two weighings, since I can't possible solve the problem in one weighing. The question becomes, can I do it in two? If my first weighing is the maximum possible 4 and 4, I also know from the above mentioned problem that it'll take at least two more weighings to solve the problem. If my first weighing is 2 and 2, then if it comes out even I'm left with 5 squares I know nothing about -- I can't really solve that in one weighing. 1 and 1 is even worse. So if I can do it in two weighings when my first weighing is 3 and 3, then I have a best solution. If not, I know I can always do it in 3 weighings. If I weigh 3v3 and it comes out even, I'm left with 3 squares I know nothing about. Weighing one of them against another doesn't immediately provide an answer since we don't know if the odd one is heavier or lighter. Putting them on the same side of the scale certainly isn't going to help. And so I conclude that the answer is 3 weighings. There's probably a short and pretty solution using information theory, but that's not my department.

It's possible to solve this in one weighing if you're really lucky. Put 4 on the left side of the balance, and 4 on the right. If they balance, the remaining rectagle is the odd one. So in one sense, the least number of weighings to find the odd rectangle is one. However that's not a very good solution - probably what was meant was, find the least number of weighings in which you can guarantee a solution. This, I agree, is three. I already know the solution with 13 balls is 3 It is? I'm familiar with a 12-ball puzzle where you need 3 weighings; I don't see how to do it for 13 balls, unless you know in advance whether the odd ball is heavier or lighter. And if you know that, then you can actually handle 27 balls in 3 weighings. Why stop at 13? Maybe there's something different about the 13-ball problem which I'm missing. [ February 24, 2004: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, Twister

Kishore Dandu
Ranch Hand

Joined: Jul 10, 2001
Posts: 1934

posted

0

Assume it is heavier than the others, tell me what it could be.

I agree with David about 3. The first weighting: 3 vs. 3 If they are equal, the wrong rectangle is among the other 3 and the rest is trivial. If they are not, then we have 3 rect. left that we know are standard. Use them to replace any of the two groups that were weighted. Now if the result is "equal" again, then we have 3 suspicious that were replaced and we know whether one of them is heavier or lighter (depending whether these 3 were lighter or heavier on the last weighting). Weight any two of them, and the problem is solved. I the result is "not equal", then we have the same situation as in the previous case, 3 suspicious rectangles that we know are lighter or heavier, only now they are on the other side of the scales (up or down).

If you know the odd rectangle is heavier than the others, 2 weighings are sufficient. Weigh 3 vs. 3. If one side goes down, one of those 3 is the heavy one. Use the second weighing to weigh 2 or those 3 - either one side goes down, and you know which is heavier, or they balance, and the one you left out is the heaviest. If the first weighing balanced, then you've got 2 remaining rectangles to investigate. Weigh them against each other; the heavier one will be obvious.

2 Weighing is sufficient Group the 9 squares as 3 in a group say A, B and C now Weight A and B. if one of it is hevaier then the odd square is in that only of if they are equal then the odd square is in the third group. No we have found out the odd group. now take two Squares from that group and weigh. if one is heavier then that is the odd square. if they are equal then the third square in the group is the odd one. So 2 weighings is all we require to find it out.

Originally posted by Karthikeyan Rajendraprasad: 2 Weighing is sufficient

Only if you are told in advance whether the odd piece is heavier or lighter than the other pieces. But if you don't know whether the piece is heavier or lighter, then you need a minimum of 3 tries.

Mani
Quaerendo Invenietis

David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365

posted

0

It is? I'm familiar with a 12-ball puzzle where you need 3 weighings; I don't see how to do it for 13 balls, unless you know in advance whether the odd ball is heavier or lighter I originally encountered the 12-ball problem a few years ago and faced the 13 problem just recently in class. Notice that this question asks us to identify the different square but doesn't require us to determine whether it's lighter or heavier. We can only do 12 if we have to figure that out whether it weighs more or less.