|
|
Re: Please help me with the following question
Posted:
Mar 8, 2013 10:45 AM
|
|
|
|
On Mar 8, 2013, at 8:55 AM, GS Chandy <gs_chandy@yahoo.com> wrote:
> It was successfully done in 3 steps by Joe Niederberger (JN) when he was around 10 years old. And by the underigned when he was 10 or 11 years old. I guarantee you neither JN nor GSC used "binary search" or "exhaustive search" or anything of the sort. Those terms were not even imagined (or imaginable) by either of us at the time. What was actually used was the 'question-asking frame of mind' that is inherent in every real learner.
I am just telling you the strategy I used. I don't know what your strategies were, both of you seem incapable of sharing them. "3 steps" is not a strategy. "Question asking" is not a strategy. Also, I am a software engineer by trade and work with other software engineers and when I use a phrase like "binary search" off the cuff, I do it out of habit because I am used to talking to practiced people. The last thing they would do or have to do is look up definitions in text books or on google. They just connect it to the experience like practiced people do.
The problem BEGGED of a tree approach. After I realized that we did not know the relative weight of the target coin I refactored.
1. Break the coins into 3 groups of 4, A, B, and C.
2. WEIGH A v B, if they are the same then C has the coin, finish off C (trivial).
3. Break the remaining 8 coins into 3 groups of 3, 3 and 2, D, E and F.
4. WEIGH D v E, if they are the same then F has the coin, finish off F (trivial).
5. WEIGH D v {3 coins from C}. If D < C then D has the coin and it is lighter, finish off D in 1 step (trivial). if D = C then E has the coin and it is heavier, finish off E in one step (trivial).
The issue of course is that step 5 requires 2 weighings, so the trick is to figure out how to make the comparison in step 4 and be left with 3 or fewer coins to test. You need step 4 because there is no strategy to insure that you have only 2 coins left, and if you have 3 coins left then you need to know which is heavier or lighter, as in the end of my first solution. I tried to close that gap for a couple of hours, and after looking up the answer, realized that I was pretty close.
If a problem takes me more than 30 minutes to solve, I consider it pretty hard. You said it took you a couple days. Surely, after a couple of days you must have some sort of strategy to share with us? Or was it hit and miss? aka, exhaustive search.
Bob Hansen
|
|
