I just wouldn't know how to construct one efficiently for arbitrary numbers of coins. Or rather, I could construct a tree that would then be the minimal tree for that number of coins, which would probably prove how many steps you minimaly need.
However what weighings you'd have to do at each node, I couldn't say...
Here's a quick drawing of the tree I came up with (top). I think it is similar to hadji's solution (attempt). And what I think the tree would have to look like (bottom). (I labeled the coins 1-12 since I have to name them something. ?= means I weigh the left list against the right one).
Though of course in the lower drawing, both branches could look like the left or both like the right branch. From what I gather, it's more probable that they will look different.
I am quite confident though that only two subtrees will be attached to the root node, since in the begining, knowing ">" or "<" won't help you much, though lower down the tree you can use that information. (For this reason weighing 6 against 6 seems, to me, a bad choise for the first weighing).
Oh yea, the ">" case from the root node is of course, except for mirroring, the same as the "<" case. It's just "!=" while remembering which side was lighter/heavier.
--
Tars Tarkas, sleeps all day and hacks all night. |
