It was one approach I tried to finding a solution.
The other was to try and draw a tree and see if I can have a decision tree where each non-leaf node was a weighing and each leaf was a coin.
Now if I could've constructed a tree with twelve leaves and maximum height 3 (counting the root as 1) I'd have had the solution.
I figured that each weighing would have 3 possible outcomes (and thus each node (at most) 3 childnodes). These being equality, one side lighter(<) or one side heavier(>). The problem is that equality didn't give me enough information in some cases and in others the < and the > were just two sides of the same coin ;).
When I then tried to combine the stuff about sets of coins with the tree model, I couldn't really keep track of everything. So I thought, why not write a program to do it for me.
The problem is, how do you know there's no more information to be gained, or seen another way, how do know you took every information you could get from each weighing (and the preceeding ones) (which, I gather is exactly the solution to finding the solution in the 12 coins problem).
Also, if you can prove that the minimum number of weighings is some number, you haven't neccessarily found that solution...
Difficult this is, confused am I.
Also I think brute force might be the only way to go. Kinda like the traveling salesman or the 0,1 knapsack problems, though these at least have rather good solutions.
Or even the problem about the minimum colours needed to color vertices in a graph. That kind of problem seemed to me to be similar to the coins problem, but I couldn't figure out how to map the one onto the other...
--
Tars Tarkas, confused. |
