|
|
Back to UserFriendly Strip Comments Index
|
attn william bashless (long) | by gibuu | 2004-12-30 12:16:08 |
|
Question about finding the solution. | by Tars_Tarkas | 2004-12-30 12:38:24 |
| Interestingly enough... (extension) |
by williamashbless |
2004-12-30 12:55:01 |
...one extension to this puzzle is to say "What is the minimum number of weighings for n coins?"
Turns out that since this is the smallest number of weighings for 12 coins (I wonder how you'd prove that? But I'm assured it's true), you can prove the minimum number for any number of coins larger than that. I invite you to prove it based on the assumption you can do 12 coins in 3.
As for a search, I once ran into a puzzle on the TopCoder programming competition website which was basically to ask you whether two sets of coins, and a weighing result was consistent with previous weighing results. Basically, a balanced scale locks in known good coins, whereas a tipped scale gives hints as to possible weights of some coins, and locks others down to either heavier or lighter or good. (See if you can figure out the rules!)
Similar techniques could be used to search for the minimum number of weighings.
I'll ponder this.
For a brute force approach you could do a depth-first recursive search based on the current state of your knowledge about the coins, and trying every possible weighing combination, and seeing what the shortest number of weighings to a solution is on future recursions as well as the weighings that accomplished it. You'd stop recursing when there was no possible further weighing that gained you more information that was still consistent with previous weighings.
Eventually you'd come out of all levels of recursion knowing the specific arrangement of coins at each level that causes the least weighings that ends in a specific coin being locked in as bad (with all others locked in as good).
|
|
[ Reply ] |
|
I did figure out the part with the sets... | by Tars_Tarkas | 2004-12-30 13:12:30 |
|
Thoughts. | by williamashbless | 2004-12-30 13:28:36 |
|
I think I would | by gibuu | 2004-12-30 15:27:55 |
|
I like trees :) | by Tars_Tarkas | 2006-11-19 12:55:59 |
|
Annotation: | by Tars_Tarkas | 2004-12-30 16:07:37 |
|
thoughts on a tree | by gibuu | 2004-12-30 17:01:55 |
|
Trees, Trees everywhere | by Tars_Tarkas | 2006-11-19 12:55:59 |
|
|
[Todays Cartoon Discussion]
[News Index]
|
|
