Is this possible?

[Imadrongo]

Is 12 not the limit?

I don't see how you solve 15. If you do 5 vs 5 you are left with 5, which cannot be tested in 2 weighs to determine which is the odd one as well as whether it is up or down.

[Laird]

Damn, my Katy-style twelve ball and fifteen ball solutions are flawed. For example, in both of them when the scales tip left -> balanced -> balanced over the three weighings then it's impossible to know whether C is heavier or E is lighter.

Neil, yes I believe you are correct that 12 is the limit but I'm still exploring the possibility of 13. First I want to find a legitimate Katy-style 12-ball solution though.

I think it means your 12-ball solution doesn't work. here's the reason:

if the scales balance out, you have four balls left, and not knowing whether the odd ball is heavier or lighter, you simply cannot figure out which one it is in just two weighings. it's impossible -- because weighing 1 against 1 won't help you if the odd ball is among the other two, and weighing 2 against 2 won't give you enough info to cover all possibilities. Note that all balls known to have normal weight are just filler.

You're forgetting something - we also have the information that the other 8 balls are equal in weight, which information we can make use of and which my solution does. I've just reviewed it and I'm confident that it's valid. Please review the technique that I described in steps 2 and 3.

We can at best acquire one trit of information per weighing, one three-way choice. However, at the end of any sequence of such trifurcated choices, you will end up with two balls, not sure whether one is heavy or the other is light, and the last weighing will be to figure that out. So, the max number of balls we can discern per n weighings is 3^(n-1) -- i.e. in three steps we can discern 9 balls, in 4 steps 27 balls, etc.

I didn't quite follow your reasoning here but in any case I believe it to be flawed because as I wrote above, I've reviewed my original 12-ball solution and still consider it to be valid. But perhaps that paragraph was supposed to be superceded by this one:

But wait! We are wasting information on the last step! Each weighing is a three-way choice! We can always do one more ball!

...which unfortunately again leaves me a little confused. I again didn't follow your reasoning but again I disagree with your conclusion that:

In three weighings, you can do 10 balls

...because as I have now written twice, I believe my 12-ball solution to be valid. But if you can pick a hole in it I'm all ears.

[vicdan]

You're forgetting something - we also have the information that the other 8 balls are equal in weight, which information we can make use of and which my solution does. I've just reviewed it and I'm confident that it's valid. Please review the technique that I described in steps 2 and 3.

Duh, you are right. of course it works.

My bad. What a fucking brain-fart!

Now the question to understand is why, in information-theoretic terms.

I keep trying to formalize this as an information-theoretic problem, and it's incredibly frustrating, because we are dealing with fractional information, and i don't really understand how to handle it. :(

In 2 choices we can distinguish 4 balls. That makes sense on the surface, because that's the information contained in 2 bits, 2^2 -- but the choices aren't binary!

[Laird]

I have a feeling that it's got something to do with this: each weighing has three possible results, and there are two weighings. Three squared is nine. Of those nine possible results, one of them is of no use to us (the option where both weighings are balanced cannot help us work out whether the odd ball out is heavier or lighter). So we are left with eight results. Now we need to not only identify the ball, but whether it is heavier or lighter, which (I guess) accounts for two results each time. So we divide our eight remaining results by two and arrive at four. That's why four balls is the maximum we can work out the odd one out from in two weighings. Does that seem legit to you?

[vicdan]

Actually the option where scales are balances does help. When the scales are unbalanced, we have six possibilities -- A or B or C lighter, D, or E or F heavier (or vice versa). if the scales are balanced, we also have six possibilities -- G or H or I are either lighter or heavier.

We halve the number of balls but also halve our certainty about each one. it balances out. This is why any such weighing must ultimately rely on trifurcated split of the balls, so there will always be a power of 3 involved.

The evil thing is that even though we are looking for a bit (which ball is abnormal) masquerading as a trit (which ball is heavier or lighter), it's encoded as two bits (which ball is abnormal, and in which way).

BTW, whenever you have a useless result, it indicates that we aren't exploiting all the possible information.

I think i figured out what was wrong with my original analysis. The way I saw it, the last two steps had to involve 3 balls -- one step to reduce the info to one trit (either A heavier/B lighter, or A lighter/B heavier, or C lighter or heavier), and one more step to reduce that to one bit. Which is a waste, because in two steps you should be able to encode at least two bits, not one trit... the last step, in merely distinguishing two balls, was under-utilized. This was my "plus one!" idea, but not taken to its proper extent.

Anyway, it looks to me like the last two steps behave as binary choices because there are 8 possibilities in 4 balls (each one being lighter or heavier), but each choice being ternary cuts the uncertainty down three-fold. however, the next power of 3 is nine, and there's no way to have four-and-a-half balls (unless you were willing to have four arbitrary balls, and fifth which could be lighter but not heavier). it is still about the powers of three.

In fact, if i am right, it should be possible to solve a modified four-balls-in-two-steps problem (given 'ballast' normal balls in abundance), such that instead of four balls, we have four-and-a-half (in information-theoretic terms, as i described above) balls. Well, it's not, because of physical balls... because you can't put 'D could be lighter' on one hand of the scales, and 'D could be heavier' on the other. however, you can solve the same problem if it's not four and a half balls, but three balls and three half-balls... e.g. X could be lighter but not heavier, Y could be lighter but not heavier, and Z could be heavier but not lighter.

Then, assuming the normal ballast balls are #, if out first weighting 'AB <=> C#' results in a balances scale, we weigh:

X <=> Y

If left side goes up, it's X... if it goes down, it's Y... and if it stays balanced, it's Z.

So year, we have a ternary choice, but distorted by the fact that you can't treat a single ball as as two balls with only one imbalance possibility each. However, i think that affects the max # of balls only on the last two steps when you get down to individual balls, so the true max # of balls doable in n steps would be 4 * 3^(n-2).

now here's a thing... if we allow the information-theoretic half-balls, we should be able to solve twelve-and-three-halves balls in three steps! because 122 balls encode only 24 possibilities, but 27 possibilities (3^3) can be encoded in three ternary choices!

So twelve balls is the maximum number of real balls you could do, but only because the real world doesn't play nice with information theory. otherwise, it's 13.5 balls you could do in three steps. The point here is that what you are comparing to the power of three is not the number of balls, but the number of possibilities, which is the number of balls *2.

The last point... i am not sure this is the limit, because ultimately we don't actually care if the ball is heavier or lighter, just whether it's different, so there's one half of a bit of decision we might be able to save somewhere.

[Imadrongo]

So year, we have a ternary choice, but distorted by the fact that you can't treat a single ball as as two balls with only one imbalance possibility each. However, i think that affects the max # of balls only on the last two steps when you get down to individual balls, so the true max # of balls doable in n steps would be 4 * 3^(n-2).

I also arrived at this.

Don't really fully understand this though.

The max we can do in 2 steps is 4 balls.
The max in 3 steps is 12 balls.
Why? Because we do 4v4, and the remainder must be done in 2 steps if that balances, hence 4.
The max in 4 steps -- 36 (by that equation)? If 12 vs 12 balances the remaining 12 unknown is the max for 3 steps.

However, if it doesn't balance, say ABCDEFGHIJKL goes down and MNOPQRSTUVWX goes up, can you solve this in 3 steps? I can't see how.

Each ball has 3 states. Limiting a ball to 2 states can't count as half a ball.

If you can solve 36 in 4 steps I am wrong here, but I don't see how you can if step 1 is unbalanced. Using the technique Laird used for 12 balls in his "step 4" you eliminate 2 balls with 1 extra step. For 8 balls, 4v4, this allows you in this case to solve it in the last step. However the most I can do with an extra step is 12 balls, 6v6, not 24.

[vicdan]

So year, we have a ternary choice, but distorted by the fact that you can't treat a single ball as as two balls with only one imbalance possibility each. However, i think that affects the max # of balls only on the last two steps when you get down to individual balls, so the true max # of balls doable in n steps would be 4 * 3^(n-2).

I also arrived at this.

Don't really fully understand this though.

Read my message again. i explained it there. The key is that each ball actually represents two possibilities fused together -- that it is heavier, and that it is lighter. 4*2=8, which is the low approximation of 3^2=9, the number of possibilities we can reduce to 1 in two steps, each step being a ternary choice.

See my point about fractional balls and information-theoretic 'balls' decoupling the fused possibilities from each other (i.e. so that you can put the 'A could be lighter' on the scale, but leave 'A could be heavier' off the scale).

In this manner, you can actually do 4.5 information-theoretic pseudo-balls in 2 weighings, or 13.5 such balls (rather than 12) in 3 weighings. You can't do 13 real balls though, because to make the 13-ball thing work, you would need to split the balls into two 4.5-ball groups and one 4-ball group.

The max we can do in 2 tests is 4 balls.
The max in 3 tests is 12 balls.
Why? Because we do 4v4, and the remainder must be done in 2 balls if that balances, hence 4.
The max in 4 tests -- 36 (by that equation)? If 12 vs 12 balances the remaining 12 unknown is the max for 3 steps.

36 balls represent 72 possibilities, which is the lowball approximation (due to the refusal of balls to behave in neat information-theoretic terms) of 3^4=81. if we were allowed the information-theoretic decoupled balls, then we could distinguish from among 40.5 balls in 4 weighings, not just 36 balls.

36 is the best we can do because of the limitations of physical balls.

Each ball has 3 states. Limiting a ball to 2 states can't count as half a ball.

It's not the two states that matter. Only one state of the whole set can be abnormal -- only one ball can be either heavier or lighter. What you have to look at is the combinatorial number of possible answers, which would always be double the number of balls.

Note that hypothetically, since we are only required to know which ball is abnormal, we shouldn't have to double the number of possibilities; but because any weighing will inevitably give us the 'heavier or lighter' information, we cannot really avoid it. i wonder is some comparable weighing technique could evade this trap though.

If you can solve 36 in 4 steps I am wrong here, but I don't see how you can if step 1 is unbalanced. Using the technique Laird used for 12 balls in his "step 4" you eliminate 2 balls with 1 extra step. For 8 balls, 4v4, this allows you in this case to solve it in the last step. However the most I can do with an extra step is 12 balls, 6v6, not 24.

You can solve 36 in 4 steps. By doing a trifurcated weighing, you cut the number of possible answers three-fold, from 72 to 24. it doesn't matter whether the balls balanced or not. if they balanced, then you have 24 possibilities -- any one of the 12 balls you left off could be either heavier or lighter. if the scale unbalanced, then you have 24 possibilities -- either one of the first 12 balls is lighter, or one of the second 12 balls is heavier.

The key here is to realize that it's not balls you are really eliminating, but ball states. Each ball embodies two states. You can eliminate one possible state without eliminating the ball, i.e. you could know that the ball A could possibly be lighter, but not heavier.

See my example about distinguishing 4.5 balls to better understand what I mean.

[Imadrongo]

You can solve 36 in 4 steps. By doing a trifurcated weighing, you cut the number of possible answers three-fold, from 72 to 24. it doesn't matter whether the balls balanced or not. if they balanced, then you have 24 possibilities -- any one of the 12 balls you left off could be either heavier or lighter. if the scale unbalanced, then you have 24 possibilities -- either one of the first 12 balls is lighter, or one of the second 12 balls is heavier.

Gotta go to class so I just skimmed through your post for now. Have you actually solved this for verification? Could you describe the steps to solve in 3 steps after you know 12 balls are lighter and 12 heavier? Maybe I am just not creative enough, but I tried and couldn't see the solution to this.

[vicdan]

OK. The lighter balls are lowercase, heavier balls uppercase. Ballast balls (i.e. ones known to be normal) don't need their own labels, they are just #.

We have:

abcdefghijjkl

vs.

MNOPQRSTUVWX

1) abcdQRST <=> MNOPefgh

if left side goes up, it's either abcd or MNOP. if right side goes up, it's either QRST or efgh. if they balance, it's either ijkl or UVWX. Since those are equivalent, i will instead use abcd vs. EFGH, to keep trackinn simple.

2) Note that we still have 8 possibilities, but 2 weighings left. We now do:

abF <=> E#c

if they balance, we do 3a. if left side goes up, we do 3b. if left side goes down, we do 3c.

3a) The scales balanced, so the abnormal ball must be it's either d or G or H. We do:

G <=> H

if left goes up, it's H. if right goes up, it's G. if they balance, it's d.

3b) left side went up. This means the culprit is either a or b or E. We do:

a <=> b

if left side goes up, it's a. if right side goes up, it's b. if they balance, it's E.

3c) left side went down. it's either F or c. We do:

c <=> #

if left side goes up, it's c. if it balances, it's F. left side cannot go down.

There. Voila! 12+12 half-balls in 3 steps.

-------------------------------------------------------------------------------------------

The solution to any size such problem is very easy to see once you realize that what we are doing is distinguishing not balls, but possibilities, of which each ball has two. In place of each ball, we are really dealing with two fused information-theoretic half-balls pretending to be a real physical ball.

Note BTW that if we could use the full number of information-theoretic pseudo-balls (i.e. 'lighter' and 'heavier' possibilities decoupled from each other, such as was in effect that case in this analysis), we would never have to use ballast balls. Each ballast ball on the scale is a wasted opportunity to get information, because we know we won't learn anything new about it.

Furthermore, if we have two sets of balls known to be either heavier or lighter (i.e. the IT pseudo-balls), such as in this example, we could do more than 12+12 -- we could in fact do full 27, e.g. 13 possibly-light balls and 14 possibly-heavy balls. We could do:

abcdefghijklm

vs.

NOPQRSTUVWXYZ$

[Imadrongo]

Oh yea.. nice that cleared it all up, I'm too used to thinking in binary rather than ternary.

I'm glad this thread happened.

[Laird]

Nice analysis Vic - it took a couple of readings for me to fully grok it but I tend to think that you've got it right. One nitpick: in one sentence you write of "122 balls" whereas you mean "12 balls" - you might want to fix that typo to save a future reader some confusion.

Oh yea.. nice that cleared it all up, I'm too used to thinking in binary rather than ternary.

Are you a programmer then? I do a bit of coding myself - once upon a time for a living but now more for personal satisfaction.

I'm glad this thread happened.

Likewise, and I'm hoping that it's not over yet... we still don't have a valid Katy-style 12-ball solution. My ten-minute job was a complete mess and I've spent about an hour or two trying to figure out a valid one with no luck so far. I get very close and then realise that there's a flaw with it, fiddle around a bit more, check it and bugger me if there's not another flaw in the tricky little thing. Damn, I wish that Katy could remember hers. I'm so tempted to turn to Google but that would be cheating. I know that one of us can do it.

[vicdan]

12-ball solution is trivial. What do you mean by Katy-style?

[Imadrongo]

I don't think Katy-style is possible for 12 balls.

Basically she figures out a way to do 3 tests and figure out the ball from them regardless of the outcomes, as is shown near the end of page 1 of this thread.

12-ball solution is trivial.

Aren't you just tempted to plug a larger numbers and ask people how to determine one ball out of millions now in a few more balances? lol

[vicdan]

I already can. i gave the formula -- knowing the number of steps allowed, you can accurately determine both the maximum possible number of balls we can distinguish in that number of steps, and the maximum possible number of information-theoretic pseudo-balls.

There's no temptation there. The problem is solved.

[Laird]

I don't think Katy-style is possible for 12 balls.

And I believe that it is, although I haven't quite managed to turn that belief into a proof by actually doing it yet; Katy claims to have done so although she now forgets her solution.

Here's the way that I've started to attack it more formally, although I've struck a point where I need (possibly computational) assistance:

Consider that each set of results from the three weighings must identify one ball in particular. This set of weighings consists of a trinary "number" where the digits are "/" (left side drops), "\" (right side drops) and "-" (balanced). Now we can assign a trinary number to each ball, where the digits from left to right are result-of-first-weighing, result-of-second-weighing and result-of-third-weighing. The results implied by this trinary number have to not only identify the ball, but also whether it is heavier or lighter. This requires that the opposite number not be associated with any other ball. By opposite I mean, that for each digit a forward slash is translated to a backward slash and dashes are left as-is. Because if another ball has the opposite number (set of weighing results) then it is impossible to distinguish for either of those results whether it is the one ball that is heavier or the other ball that is lighter. Once we have assigned a (unique) trinary number to each ball, then we can assign that ball to a particular side of the scales on each weighing based on its digit - for convenience I have taken the convention that the ball would be heavier and thus that a "\" implies "ball on the right side of the scales", a "/" implies "ball on the left side of the scales" and a "-" implies "ball not present in this weighing".

So, for example, if ball D is associated with trinary number "-\/" then we can add it to the (as-yet unpopulated) set of weighings thus:
Weighing 1: (empty so far) vs (empty so far)
Weighing 2: (empty so far) vs D
Weighing 3: D vs (empty so far).

So far so good, but there is a complication. As I explained above, for each ball we have a choice between a number and its opposite number. We have to choose carefully, because we need to end up with an equal number (four) of balls on each side of each weighing. And that is where I am stuck - I can see no definitive algorithm to generate a sane choice other than brute force, and given the number of possibilities this is unfeasible. So I'm thinking perhaps code up a program that uses a genetic algorithm with the fitness selection being based on the sum of the absolute value of the difference between the current number of balls on each of the six sides of the weighings from (the necessary) four. I have the skill to do this but I'm not sure whether I have the motivation. I am a slow coder and (as you can see in some of my earlier posts to this thread) I am quick to jump to logical non sequitors when I am problem-solving, so it would be painful. Furthermore a genetic algorithm isn't guaranteed to converge on the optimum solution anyway, and I don't really know how amenable to such an approach this problem is. Vic, you're a coder and I'm guessing that you're familiar with genetic algorithms - what do you reckon? Or can you see a definitive algorithm? Anyone else please feel free to offer advice too.

Here is the set of numbers and opposites that I have constructed:
A --\ and --/
B -\- and -/-
C -\\ and -//
D -\/ and -/\
E \-- and /--
F \-\ and /-/
G \-/ and /-\
H \\- and //-
I \\\ and ///
J \\/ and //\
K /\- and \/-
L /\/ and \/\
...with an extra one left over and which could be substituted for any of the above: /\\ and \//. You might note that "---" is not an option: this is because, as I wrote in an earlier post and which Vic misinterpreted, it does not provide us with any information about which balls are heavier or lighter.

[vicdan]

The branchless solution algorithm for any number of balls is possible if you can solve it for 4 balls in 2 steps.

Figure out a branchless 2-step solution for 4 balls, and you are golden...

Here it is.

1) AB <=> C#
2) AC <=> ##

Voila! Now you figure out how I know that this guarantees a branchless solution for any # of balls.

BTW, the branchless solution for 4.5 IT pseudo-balls is trivial.

[David Quinn]

Did someone say trivial?

-

[vicdan]

Too trivial for you to bother your immense mind with, dear. Go away.

[Philosophaster]

Did someone say trivial?

-

Hehe.

That's my cue to start the thread I was planning.

[Laird]

The branchless solution algorithm for any number of balls is possible if you can solve it for 4 balls in 2 steps.

Figure out a branchless 2-step solution for 4 balls, and you are golden...

Here it is.

1) AB <=> C#
2) AC <=> ##

I don't understand this. You used # in a previous post to indicate that we already knew that the ball was even. How can we know that in our first weighing though, if we have only four balls to start with? I'm guessing that you're assuming that this is part of a larger series of steps where weighings have already occurred. I don't believe that this is possible simply with four balls to start with. It's possible with three balls though:
A vs B
A vs C

Here we have the trinary numbers:
A heavier: //
A lighter: \\
B heavier: \-
B lighter: /-
C heavier: -\
C lighter: -/

There are no further trinary numbers possible, with the exception of the unusable "--", which is why I assert that a four-ball solution does not exist.

Voila! Now you figure out how I know that this guarantees a branchless solution for any # of balls.

BTW, the branchless solution for 4.5 IT pseudo-balls is trivial.

I'm not even going to try to go for either of these puzzles until I understand your 2-step-4-ball solution.

[Laird]

There are no further trinary numbers possible, with the exception of the unusable "--", which is why I assert that a four-ball solution does not exist.

Duh, sorry, there are of course two further trinary numbers possible: "/\" and "\/", but it's impossible to add these without resulting in an excessive number of balls on either side of the scales on both weighings, which is the real reason why a four-ball solution does not exist.

[vicdan]

I don't understand this. You used # in a previous post to indicate that we already knew that the ball was even. How can we know that in our first weighing, if we have only four balls to start with? I'm guessing that you're assuming that this is part of a larger series of steps where weighings have already occurred.

Right. i should have made that clear. I am assuming the existence of ballast balls -- which is guaranteed in any larger weighing.

I'm not even going to try to go for either of these puzzles until I understand your 2-step-4-ball solution.

There you go. I assume availability of ballast balls for convenience. They will be available n any larger weighing sequence.

[Laird]

I am assuming the existence of ballast balls -- which is guaranteed in any larger weighing.

Ah, but then you are talking about something different to what Neil and I are talking about. We are talking about self-contained branchless weighings, not as part of a larger weighing.

[vicdan]

You are missing the point. You need the ballast balls only for the last stage, for the 4 balls. Any larger number of weighings doesn't need 'em, but will provide ballast for the 4-ball weighing.

As I said, if you figure out how I know that having a branchless 4-ball weighing guarantees branchless weighing of any number of balls*, you will know how to compose such a weighing.

* With one caveat: not all weighings with number of balls below the maximum possible for the given number of steps will work. You can always do the maximum number of balls though (12, 36, etc.)

[Laird]

As I said, if you figure out how I know that having a branchless 4-ball weighing guarantees branchless weighing of any number of balls*, you will know how to compose such a weighing.

I'm still missing your point. Your branchless 4-ball weighing includes ballast balls, so the guarantee for any number of balls presumably likewise requires ballast balls. But we are considering complete branchless solutions (in particular, for 12 balls) where there are no ballast balls to start with. How can your guarantee then apply?