Re^11: Odd Ball Challenge

Here's one way to answer it: make the problem more general. Ask for a program that will find the least number of weighings to find the odd ball among n, where n is given as a parameter.

Now I suspect the answer can be reduced to a simple formula, in which case someone might derive the formula and write a program to calculate only that.

If that doesn't fall within the parameters of what you're looking for, you will then need to specify much more clearly what you do and don't want to allow.

I suspect the purpose is to show different people's approaches to solving this sort of thing, and I (and I suspect many of the people that would be interested in this sort of puzzle) would always start off with: "the simplistic approach is to traverse the entire search space, but combinatorial explosion will scupper that pretty quickly; so let's sit down with pencil and paper and see what logic or maths I can apply to reduce that search space". With this approach, finding a formula is an ideal solution: it reduces the search space to one, and so if I found such a formula I'd post just that instead of writing the program at all.

Of course if no-one knows (or can find) a formula, this secondary issue might not arise.

Hugo

Comment on Re^11: Odd Ball Challenge

Replies are listed 'Best First'.
Re^12: Odd Ball Challenge by Anonymous Monk on Jun 24, 2005 at 23:57 UTC
I think problem statement is more confused than that. Reading between the lines, I think the challenge maybe boils down to something like... We're given a set of axioms We're told a particular statement is true Find a set of inference rules which can provide a proof of #2, starting with the axioms Thoughts? Anyone?	[reply]
Re^13: Odd Ball Challenge by QM (Parson) on Jul 14, 2005 at 14:03 UTC
Yes, it makes me think of the 4-color map theorem. It also makes me think of Gödel's theorem. Which leads me to contemplate a theorem generating system that takes a set of axioms, generates all of the theorems in that system, compares them to a list of proven results in various systems, and determines which results can't be proven with those axioms (and the subset that are actually contradicted). -QM -- Quantum Mechanics: The dreams stuff is made of	[reply]