in reply to Re^9: Odd Ball Challenge
in thread Odd Ball Challenge

zby,
The challenge is to write a program for finding the right series of steps. I guess what you are saying is where do I draw the lines between what I "know" and what I let the program figure out on its own.

For instance, it is pointless to weigh groups that have an unequal number of balls since it will not lead to any useful information. Is it ok to add that logic?

I guess I just don't know how to answer that. The two solutions I know that work require dividing the 12 balls into 3 groups of 4. I wouldn't want a program that didn't consider other sizes unless there was some mathematical way of knowing that no other group/sizes were possible. I however wouldn't think anything of a solution that didn't consider groups of unequal number of balls since they would never be expected to balance.

Sorry I can't give an exhaustive list of things that are ok and not ok. I am not interested in a translation of a known solution to code though.

Cheers - L~R

Replies are listed 'Best First'.
Re^11: Odd Ball Challenge
by hv (Prior) on Jun 24, 2005 at 17:00 UTC

    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

[reply]
      I think problem statement is more confused than that. Reading between the lines, I think the challenge maybe boils down to something like...
      1. We're given a set of axioms
      2. We're told a particular statement is true
      3. Find a set of inference rules which can provide a proof of #2, starting with the axioms
      Thoughts? Anyone?
[reply]
        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]

In Section Meditations