CareerCup

@ mAn1Ac
25 should be divided into 9, 9 and 7. If you are taken 25 balls. I think its a typo. you write 3 there.

oh ya .. sorry for that .. its 7

I don't understand why you think it's important to get powers of three. Why not just divide the balls in 3 groups as evenly as possible?

ya u can do that also but the thing is with ur approach u will need more number of iterations .. while with my approach iteration will be less but no. of groups will increase a bit .. so finally i think both approach will give nearly same number hits required .. so it depends on where u want to compromise ..
also i haven't checked both approaches ... i am just thinking this must be whats going on .. if someone actually checked with both approaches please comment .. :)

Splitting the balls as evenly as possible, like I recommend, will minimize the worst-case number of times you have to use the balance. You can see that this is true because in the worst case, the largest group is the group the light ball is in. So you want the largest group to be as small as possible.

Interesting conversation really.

Suppose we have 624 balls. I am comparing two methods given by @mAn1Ac and @eugene.yarovoi

First consider @mAn1Ac 's comment.
According to him - "divide into 3 groups such that at least two groups contain elements to certain power of 3 which is nearest to the total number of elements" (some modification by me)
So 624 is divided into 243-243-138

If odd ball(considering only one ball is lighter than other) present in 138 group. Again 138->(27+27+74), Considering 27 group contains lighter ball 27->(9+9+9).. And so on.
So in this sequence 624->138->27->9->3 overall 5 comparisons. So my point is there is slight chance that we can minimize the total number of comparisons by doing this. Otherwise this can always be done in ceil(log_3_(n)) comparisons.

But if we use @eugene.yarovoi 's proposal we will surely lead with ceil(log_3_(n)) comparisons. Because all the balls are evenly distributed in all three groups.
So 624(208+208+208)->208(69+69+70)->69(23+23+23)->23(7+8+8)->7(3+3+2)->3(1+1+1) Overall 6 comparisons.

My algorithm is designed to minimize the number of worst-case comparisons. It's not designed to minimize average case. Still, even if we're talking about the average case, I want to cast some doubt on the notion that it's by any means clear that any of these round-to-a-power-of-3 algorithms are better than even splitting.

First of all, the assertion that my algo always uses ceil(log_3_(n)) steps is inaccurate. How about a case like 250? I would split into 83 + 83 + 84. Then 83 -> 27 + 28 + 28, and then 27 is solved in 3 weightings. So then 250 is solved in 5 weightings (if I get lucky), and you can't really say it's always ceil(log_3_(n)), since that would be 6.

In fact, I'd like to note that the probability of my algo solving 250 in 5 steps is quite high. The probability of getting 83 in the first step is almost 2/3, and the probability of getting 27 is almost 1/3 in the next step. But if I get 28, the probability is still almost 2/3 that I get 9 next and still solve 28 in 3 steps. From these considerations, a lower bound on the probability that I solve 83 in 4 steps is something slightly less than 7/9 (but that's just a lower bound). And if I get 84 in the first step, that's 28 + 28 + 28, so still something like a 2/3 chance there. So overall there's at least (it's actually higher) a 2/3*1/3 + 2/3*1/3 + 7/9 * 1/3 = 19/27 chance I solve in 5 steps. The expectation's even better than that actually. Evaluating all possible paths by computer gives an expectation of 5.112 (log_3_250 is ~5.026)

And what's the interpretation of the other algorithm for a case like 250? Is it 243 + 3 + 4? Is it 81 + 81 + 88? I take it that it's more 81 + 81 + 88? So let's look at the fundamental difference between 81 + 81+ 88 and 83 + 83 + 84. In maniac's scheme, we're making sure 2 of the 3 cases can't take longer than 5 comparisons, but increasing the chance that the remaining 1 case takes 6 steps (though it could still take 5). With my algo, we've simply redistributing these probabilities a little: we're allowing all 3 cases to possibly take 6 steps, but with lower probability that each case will take 6 steps than the probability that the 88 case would. It strikes me that it is by no means easy to determine, simply by looking at the problem, which redistribution of the probabilities has a lower expected runtime. On one hand, the marginal rate of growth of log_3_x is smaller for 88 than for 84; on the other hand, when you have 81 + 81 + 88, your probability of ending up in the 88 group is actually higher than 1/3 (88/250)!

I suspect -- though I have not determined -- that it probably is the case that my algorithm performs worse in the average case, but for reasons entirely different than mentioned so far. The problem is the fact that n = 2 is a special case in this problem. n = 2 still requires 1 comparison, and not log_3_2 comparisons, due to the nature of this problem. My algorithm doesn't take this into account. 7 is stupidly split into 3 + 2 + 2, whereas 3 + 3 + 1 is much better. 2s should always be converted to 3s and 1s where possible. Using powers of three like that helps avoid some of the n = 2 corner cases once the input gets small, and this helps increase the chances that small cases will perform well, and since every big case eventually degenerates to a small case, this helps the big cases too.

My conjecture is that if my algorithm were to be supplemented with special treatment for certain special cases, it could outperform both maniac's algorithm and my original algorithm. I don't have any solid evidence for this conjecture, however.

Very very good conversation. This will help a lot. Thanks.

I'd like you to answer my question, though, if you can: "And what's the interpretation of the other algorithm for a case like 250? Is it 243 + 3 + 4? Is it 81 + 81 + 88? "

What's the rule you're using, so I can accurately put it into the computer program?

It is 81+81+88

divide into 3 groups such that at least two groups contain elements to certain power of 3 which is nearest to the total number of elements.
If it is not possible to divide in such order then atleast one group should contain elements to certain power of 3.

@ eugene.yarovoi .. first of all awesome analysis !! thanks :)
secondly coming to ur question .. according to my original algo. 243+3+4 will be taken which will give worst result .. so what i m suggesting is we can decide some threshold value and if the difference between the given number and closest power of 3 is less than that threshold then we'll go with ur algo. otherwise we'll go with mine for one iteration .. then for next iteration we can check once again ... i thought of this because ur algo. is giving best result with worst case and mine with average case .. so by combining both we can get the best result for every value of n ..
for threshold i am thinking it should be something like next lower power of three .. i am not sure though ... so if u can try to come up with some expression for threshold which will give best results, it would be great .. i'll also try ..
by using this method the time complexity of algo will definitely increase a bit because at every step some extra computations will be done but we are also getting best results for each value of n ...
also we need to do this comparison at each iteration because i am thinking that on an average the worst case also will eventually convert to the average case .. obviously u can always come up with some value of n which always gives worst case but it might not happen that often ..

@Psycho ya ur modification in algo. is better than original .. but this is not the one which i gave .. thanks :)
@ eugene.yarovoi try with the modified one .. and also try with the threshold i suggested .. see if there is any improvement .. i'll post some test input against which u can check the algos.

I do want to note that in any event all of these are within 1 comparison or so of each other, so the differences are very small

I want a general idea. "The given quoted question is just an example". The basic question is all about general idea or formula!

If you have 1 ball, you've found your answer. Otherwise, divide into 3 groups as evenly as possible. When you do that, either 2 or all 3 of the groups will be equal in size. Take two equal groups and weigh them. If one is lighter, recursively repeat this algorithm with just the lighter group. If the groups are equal in weight, the lighter ball is in the group that you didn't put on the balance, so repeat this algorithm with just the group not on the balance.