Solve this if you can !

[Commander]

There are 39 perfectly Spherical Metal Balls IDENTICAL to one another in Shape , Color and Weight.

 

Except that just one of these Balls is DEFECTIVE and has a DIFFERENT WEIGHT compared to the Rest of the Balls.

 

We don’t know whether this Defective Balls is HEAVIER or LIGHTER in Weight.

 

We also don’t know which is this Ball out of the 39.

 

We have Only a SIMPLE BLALANCE and nothing else to use [No Weight Units etc]

 

 

Some of these Balls can by weighed in the scale against each other and any Inference taken counts for one Weighing !

 

In how many weighings can you detect the Defective Ball and what is the Procedure ?

 

Remember, you need to also find whether that Defective Ball is Lighter or Heavier than the others within the same number of Weighings !!

[imatfaal]

 

 

make four groups of nine [1,2,3,4] and one group of three [5]

1. weigh 1v2

2. weigh 3v4

you get one of five scenarios

1=2 AND 3=4

1<2 AND 3=4 , 1>2 AND 3=4

1=2 AND 3<4, 1=2 AND 3>4

so treating each in turn

 

1=2 AND 3=4

misweight must be in [5]

call the balls in [5] a b and c. choose three from [1] and call them d e and f

3. a+b+c v d+e+f

4. a+b v d+e

5. a v d

So weighing 3 will tell you whether misweight is heavier or lighter (as d e f are correct)

weighing 4 will tell you if misweight is c or not

weighing 5 will tell you if misweight is a or b

 

 

1<2 AND 3=4

One group is heavier that other three - in this case 2.

3. weigh 2 v 3

can give two answers

if 2=3 misweight is light and is in 1

if 2>3 misweight is heavy and is in 2

so you now have 9 [A,C,..I] suspect balls and know whether misweight is light or heavy

4. A+B+C+D v E+F+G+H

if balance you know I is misweight and you know whether heavy or not from 3.

if imbalanced you know where misweight is as you know if it is heavy or light from 3.

for sake of argument say first group includes misweight

5. A+B v C+D

for sake of argument say first group includes misweight

6. A v B

 

All the other three scenario are symmetrical to 1<2 AND 3=4 above

 

 

 

I am never efficient on these things so I am sure someone will be able to do 5 max weighings

[Acme]

I have to rush off to enjoy some dental work so I will just give a quick answer.

 

First though, I have to ask what shape other than spherical are balls?

 

 

OK. Set one ball aside & put 19 of the rest on one pan and the other 19 balls on the other pan. If they balance then the ball set out is the odd-ball. Then put that odd-ball on a pan and any one of the other balls on the opposite pan to find if the odd-ball is heavier or lighter than all the others. If you luck out enough to have set out the odd-ball at the start then you can solve the puzzle in just two weighings.

 

Edited December 17, 2014 by Acme

[Commander]

 

 

make four groups of nine [1,2,3,4] and one group of three [5]

1. weigh 1v2

2. weigh 3v4

you get one of five scenarios

1=2 AND 3=4

1<2 AND 3=4 , 1>2 AND 3=4

1=2 AND 3<4, 1=2 AND 3>4

so treating each in turn

 

1=2 AND 3=4

misweight must be in [5]

call the balls in [5] a b and c. choose three from [1] and call them d e and f

3. a+b+c v d+e+f

4. a+b v d+e

5. a v d

So weighing 3 will tell you whether misweight is heavier or lighter (as d e f are correct)

weighing 4 will tell you if misweight is c or not

weighing 5 will tell you if misweight is a or b

 

 

1<2 AND 3=4

One group is heavier that other three - in this case 2.

3. weigh 2 v 3

can give two answers

if 2=3 misweight is light and is in 1

if 2>3 misweight is heavy and is in 2

so you now have 9 [A,C,..I] suspect balls and know whether misweight is light or heavy

4. A+B+C+D v E+F+G+H

if balance you know I is misweight and you know whether heavy or not from 3.

if imbalanced you know where misweight is as you know if it is heavy or light from 3.

for sake of argument say first group includes misweight

5. A+B v C+D

for sake of argument say first group includes misweight

6. A v B

 

All the other three scenario are symmetrical to 1<2 AND 3=4 above

 

 

 

I am never efficient on these things so I am sure someone will be able to do 5 max weighings

 

A very good attempt. However it can be bettered !

I have to rush off to enjoy some dental work so I will just give a quick answer.

 

First though, I have to ask what shape other than spherical are balls?

 

 

OK. Set one ball aside & put 19 of the rest on one pan and the other 19 balls on the other pan. If they balance then the ball set out is the odd-ball. Then put that odd-ball on a pan and any one of the other balls on the opposite pan to find if the odd-ball is heavier or lighter than all the others. If you luck out enough to have set out the odd-ball at the start then you can solve the puzzle in just two weighings.

 

 

The Solution does not depend on luck !

[Unity+]

There are 39 perfectly Spherical Metal Balls IDENTICAL to one another in Shape , Color and Weight.

 

Except that just one of these Balls is DEFECTIVE and has a DIFFERENT WEIGHT compared to the Rest of the Balls.

 

We don’t know whether this Defective Balls is HEAVIER or LIGHTER in Weight.

 

We also don’t know which is this Ball out of the 39.

 

We have Only a SIMPLE BLALANCE and nothing else to use [No Weight Units etc]

 

39 Balls.jpg

 

Some of these Balls can by weighed in the scale against each other and any Inference taken counts for one Weighing !

 

In how many weighings can you detect the Defective Ball and what is the Procedure ?

 

Remember, you need to also find whether that Defective Ball is Lighter or Heavier than the others within the same number of Weighings !!

Isn't this an NP problem? The larger the stack, the longer it will take to find the ball. The problem is similar to defining a list of number that have only one unique element and finding it. Of course, it is verifiable, but not easily solved.

[Acme]

The Solution does not depend on luck !

The one I gave does and it is correct.

[imatfaal]

Isn't this an NP problem? The larger the stack, the longer it will take to find the ball. The problem is similar to defining a list of number that have only one unique element and finding it. Of course, it is verifiable, but not easily solved.

I am not sure if BigO(n)counts as polynomial time - i thought it was BigO(n^k) where k>1. I would say this problem is bounded in linear time

[Unity+]

I am not sure if BigO(n)counts as polynomial time - i thought it was BigO(n^k) where k>1. I would say this problem is bounded in linear time

Yeah, my bad. I just thought there were similarities. Anyways, the only way I have found to solve it is keep halving and comparing till you get down to the last ball.

[tar]

I don't know how to mark spoiler, so don't read this since it might be a solution in 5 trials or less.

Weigh 10 against 10.
If they are equal you know the odd ball is in the other 19.

Second trial, wheigh 10 of the unwheighed against 10 of the already known to be nonodd. If the first time wheighed group goes up there is a light one in there, if it goes down there is a heavy one. Now after two trials you have a group of 10 in which you know there is an odd ball and you know if it is light or heavy, or you have narrowed the field to 9 but don't know heavy or light.

With the 10 that include the odd ball split them 5 5 and select the group that goes in the oddball direction, up or down.

fouth trial measure two against two of the oddball group if they balance the odd ball is the one not tried and you already know heavy or light and you are done.

If they don't balance, you take the oddball pair (that went in the oddball direction) and compare them, and this fifth trial will end it.

If after your second trial you have the field of 9 measure 5 against 5 known to be non odd and between dividing in half and learning heavy light or the same, you will be able to complete the challenge in 5 (or less) trials.

 

[Commander]

I don't know how to mark spoiler, so don't read this since it might be a solution in 5 trials or less.

 

 

Weigh 10 against 10.

If they are equal you know the odd ball is in the other 19.

 

Second trial, wheigh 10 of the unwheighed against 10 of the already known to be nonodd. If the first time wheighed group goes up there is a light one in there, if it goes down there is a heavy one. Now after two trials you have a group of 10 in which you know there is an odd ball and you know if it is light or heavy, or you have narrowed the field to 9 but don't know heavy or light.

 

With the 10 that include the odd ball split them 5 5 and select the group that goes in the oddball direction, up or down.

 

fouth trial measure two against two of the oddball group if they balance the odd ball is the one not tried and you already know heavy or light and you are done.

 

If they don't balance, you take the oddball pair (that went in the oddball direction) and compare them, and this fifth trial will end it.

 

If after your second trial you have the field of 9 measure 5 against 5 known to be non odd and between dividing in half and learning heavy light or the same, you will be able to complete the challenge in 5 (or less) trials.

 

 

Hi, Thanks.

 

One needs to be specific while listing out the Trials.

From my experience I know it helps a lot if the Balls are designated like B1, B2 etc and trials listed like B1,B2 etc... v B39, B38 etc , ... and if Left Up or Equal or Right Up etc to cover all possibilities to derive the rigorous Answer. Use of Pen and Paper accelerates processing instead of just trying to solve mentally !

 

 

 

 

I too did not know how Spoiler is given.

Just found it by clicking on Special BBCode Icon !

 

 

 

 

Edited December 18, 2014 by imatfaal

[Delta1212]

Yeah, my bad. I just thought there were similarities. Anyways, the only way I have found to solve it is keep halving and comparing till you get down to the last ball.

I'm aware of the more efficient method of mixing weighed and unweighed balls, but I can never remember how to do it properly on my own.

[imatfaal]

Tar - you will have to set me straight on where I am going wrong with your method

 

 

 

 

I have numbered balls 1-39

1. 1-10 v 11-20 --> equal therefore H or L is in 21-39

2. 1-10 v 21-30 --> equal therefore H or L is in 31-39

this is the situation you have described as "or you have narrowed the field to 9 but don't know heavy or light"

3 . 1-5 v 31-35 (ie 5 known good) versus 5 potential bad - per "measure 5 against 5 known to be non odd"

if this gives equal therefore H or L is in 36,37,38,39

 

I make it three moves from here - perhaps you could elucidate

 

 

 

 

Yeah, my bad. I just thought there were similarities. Anyways, the only way I have found to solve it is keep halving and comparing till you get down to the last ball.

Yeah - thats the upper bound. And that's linear - ie it grows with n. But you might want to check with a teacher if linear counts as polynomial - it could be that anything which doesn't get "economies of scale" ie anything where the T(n) doesn't grow slower than n will be counted as polynomial.

 

Although you should also bear in mind that not all NP are difficult - the difficult ones are the NP-Complete or NP-Hard. The NP is often thought to stand for non-polynomial - which would mean that it gets more complex quicker than polynomial time - ie exponential or worse. But NP actually stands for Non-deterministic Polynomial - which refers to the time to solve and form of turing machine needed to be invoked.

 

Be aware I fully expect you to be explaining this to me in a few years time

[Unity+]

Tar - you will have to set me straight on where I am going wrong with your method

 

 

 

 

I have numbered balls 1-39

1. 1-10 v 11-20 --> equal therefore H or L is in 21-39

2. 1-10 v 21-30 --> equal therefore H or L is in 31-39

this is the situation you have described as "or you have narrowed the field to 9 but don't know heavy or light"

3 . 1-5 v 31-35 (ie 5 known good) versus 5 potential bad - per "measure 5 against 5 known to be non odd"

if this gives equal therefore H or L is in 36,37,38,39

 

I make it three moves from here - perhaps you could elucidate

 

 

 

 

 

Yeah - thats the upper bound. And that's linear - ie it grows with n. But you might want to check with a teacher if linear counts as polynomial - it could be that anything which doesn't get "economies of scale" ie anything where the T(n) doesn't grow slower than n will be counted as polynomial.

 

Although you should also bear in mind that not all NP are difficult - the difficult ones are the NP-Complete or NP-Hard. The NP is often thought to stand for non-polynomial - which would mean that it gets more complex quicker than polynomial time - ie exponential or worse. But NP actually stands for Non-deterministic Polynomial - which refers to the time to solve and form of turing machine needed to be invoked.

 

Be aware I fully expect you to be explaining this to me in a few years time

Pressure is on, I guess.

[Acme]

There are 39 perfectly Spherical Metal Balls IDENTICAL to one another in Shape , Color and Weight.

...

We have Only a SIMPLE BLALANCE and nothing else to use [No Weight Units etc]

39 Balls.jpg

...

So Commander, just wondering about the significance -if any- of using balls and of your illustration. Is the puzzle the same if say we used cubes & not balls? Is the arrangement of balls or some other element of the illustration a subtle hint?

 

I couldn't improve on Imatfaal's solution of 6, I didn't quite follow Tar's 5, and the best I could do by extending my starting with 2 groups of 19 and a lone ball was 11 weighings.

[imatfaal]

 

 

1. 13 vs 13 and 13 spare ie 1-13 v 14-26 spare =27-39

if 1. is equal (bad must be in 27-39 and 1-26 are good)
2. 27-39 v 1-13

if 27-39>1-13 then 27-39 contains HEAVY ball

if 27-39<1-13 then 27-39 contains LIGHT ball

if 1. is not equal (27-39 are good and you have two set of 13 - one heavier and one lighter)
2. heavier 13 v 27-39

if heavier 13>27-39 then heavier 13 contain HEAVY ball

if heavier 13<27-39 then lighter 13 contain LIGHT BALL
you now have 13 balls which you know contains the odd - and you know if this is heavier or lighter

3. 6v6
4. 3v3
5. 1v1

 

 

 

max 5 weighings

Pressure is on, I guess.

 

The areas you have studied you are already streets ahead of me - it's just I have had more time to look at more subjects

[Commander]

Hi All,

 

This puzzle is my own creation though I have earlier heard about and solved similar problems.

 

These type of Puzzles need intuitive Human inference and therefore can not be solved with macros and programming.

 

I wish we can have a prize for the first CORRECT Solution and I am happy to see many attempts are being made from different angles.

 

imatfaal has found a neat solution with 5 weighings which is the best so far !

tar has given a different solution but I see some possibilities are not covered like

If first 10 = second 10 and then second 10 = third 10 in the 2nd weighing we still don't know whether the remaining 9 balls contain a lighter oddball or heavier oddball and therefore the statement that after 2 weighings we have max 10 balls containing a known oddity of the oddball within them is not understood by me.

I think we can handle 120 Balls if 5 Weighings are allowed !

Edited December 18, 2014 by Commander

[Sensei]

I didn't read other solutions, so maybe somebody already used this technique:

 

 

Split 39 balls to 3 groups, each with 13 balls. A,B,C groups.

Weight A with B.

Weight A with C.

If A=B then C will have different weight.

If A=C then B will have different weight.

Otherwise A.

 

Now we know which group has mismatch. And whether it's lower or higher mass.

 

We randomly pick up ball. 13-1 = 12 balls.

Split 12 balls to 2 groups, each with 6 balls. D,E

 

Weight D with E.

If D=E then randomly picked up ball will have different weight.

If D>E and group was heavier than 2 other groups in 1st step then D will have different weight.

 

 

Split 6 balls to 2 groups, each with 3 balls. F,G

 

Weight F with G.

If F>G and group was heavier than 2 other groups in 1st step then F will have different weight.

 

Pick 2 balls from 3 remaining.

If they're equal, 3rd one is the one we're searching for.

If they're different, we compare 1st with 3rd, if they're equal 2nd one is the one we're searching for, otherwise 1st.

 

 

 

It's slightly modified binary-search algorithm.

 

At best it'll find ball in 3 weighting (7.7%)

At worst it'll find ball in 6 weighting (46.15%), and 5 weighting (46.15% cases).

Edited December 18, 2014 by Sensei

[Robittybob1]

The one I gave does and it is correct.

1 chance in 39 of being lucky! not good odds.

[Acme]

1 chance in 39 of being lucky! not good odds.

'Not good' is a subjective measure. The fact remains that I have accurately described a solution and one which uses fewer weighings than other respondents.

 

While I'm here, I'm still waiting for an answer from Commander on my questions. Please do me the courtesy of a response.

 

So Commander, just wondering about the significance -if any- of using balls and of your illustration. Is the puzzle the same if say we used cubes & not balls? Is the arrangement of balls or some other element of the illustration a subtle hint? ...

Edit: PS My questions rely on intuitive Human inference.

...These type of Puzzles need intuitive Human inference and therefore can not be solved with macros and programming. ...

Edited December 19, 2014 by Acme

[Sensei]

1 chance in 39 of being lucky! not good odds.

 

Almost like on roulette in casino (1 from 37).

 

Once I saw that guy put maximum money (we have limits) on single number (and surrounding it pairs, corners etc. if you're not familiar with roulette hard to explain quickly), then croupier hit exactly that number, and guy earned ~40,000.

And he leaved coins on the same number.

Croupier hit it again, same number in a row!

80,000 earned in 3 minutes or so.

[Robittybob1]

 

Almost like on roulette in casino (1 from 37).

 

Once I saw that guy put maximum money (we have limits) on single number (and surrounding it pairs, corners etc. if you're not familiar with roulette hard to explain quickly), then croupier hit exactly that number, and guy earned ~40,000.

And he leaved coins on the same number.

Croupier hit it again, same number in a row!

80,000 earned in 3 minutes or so.

Did you ask him who he was?

[Commander]

So Commander, just wondering about the significance -if any- of using balls and of your illustration. Is the puzzle the same if say we used cubes & not balls? Is the arrangement of balls or some other element of the illustration a subtle hint?

 

I couldn't improve on Imatfaal's solution of 6, I didn't quite follow Tar's 5, and the best I could do by extending my starting with 2 groups of 19 and a lone ball was 11 weighings.

 

Hi, Thanks

 

Yes, all balls need to be identical in every aspect st an wisecrack does not use visible cues !

 

Can be Cubes or any other shape too - just equal is weight except just in one case and ONLY Weight IS THE CRITERIA TO USE and DEDUCE FROM !!

I didn't read other solutions, so maybe somebody already used this technique:

 

 

Split 39 balls to 3 groups, each with 13 balls. A,B,C groups.

Weight A with B.

Weight A with C.

If A=B then C will have different weight.

If A=C then B will have different weight.

Otherwise A.

 

Now we know which group has mismatch. And whether it's lower or higher mass.

 

We randomly pick up ball. 13-1 = 12 balls.

Split 12 balls to 2 groups, each with 6 balls. D,E

 

Weight D with E.

If D=E then randomly picked up ball will have different weight.

If D>E and group was heavier than 2 other groups in 1st step then D will have different weight.

 

 

Split 6 balls to 2 groups, each with 3 balls. F,G

 

Weight F with G.

If F>G and group was heavier than 2 other groups in 1st step then F will have different weight.

 

Pick 2 balls from 3 remaining.

If they're equal, 3rd one is the one we're searching for.

If they're different, we compare 1st with 3rd, if they're equal 2nd one is the one we're searching for, otherwise 1st.

 

 

 

It's slightly modified binary-search algorithm.

 

At best it'll find ball in 3 weighting (7.7%)

At worst it'll find ball in 6 weighting (46.15%), and 5 weighting (46.15% cases).

 

Hi,

 

Can you suggest a generic algorithm.

 

I think I have one which gives B_N which means the number of Balls that can be decided upon [spot and Fix the Direction of Variation Lighter or Heavier]as a Function of B_N-1

 

_{PS : I read your Spoiler later and I think your Solution is similar to that of imatfaal and may produce a Solution in 5 Turns ! Good Try !!}

Edited December 19, 2014 by Commander

[Acme]

Hi [Acme], Thanks

 

Yes, all balls need to be identical in every aspect st an wisecrack does not use visible cues !

 

Can be Cubes or any other shape too - just equal is weight except just in one case and ONLY Weight IS THE CRITERIA TO USE and DEDUCE FROM !!

OK, thank you. I think we have some language barrier issues as 'wisecrack' refers to a joke and I don't understand a joke in the context of your reply. I would also point out that you said pen and paper were helpful and that implies visual clues.

 

Hi, [sensei]

 

Can you suggest a generic algorithm.

 

I think I have one which gives B_N which means the number of Balls that can be decided upon [spot and Fix the Direction of Variation Lighter or Heavier]as a Function of B_N-1

Sensei can of course reply himself, however I'm unclear on what you have written. (Language barrier again perhaps.) What I get from it is that the solution for 39 balls [b₃₉ ] is 38 weighings [b_39-1 ]. However since we have solutions of as few as 5 weighings that doesn't make sense. Can you clarify?

[Sensei]

Can you suggest a generic algorithm.

 

Binary-search is basically divide to half, and compare.

http://en.wikipedia.org/wiki/Binary_search_algorithm

 

Suppose so we have array of strings, and want to find correct one matching input (or whether it exists),

you have length of array, so divide length by 2, and compare input string with entry that has index=length/2

if it's lower then you know that string you're searching for has index < length/2

otherwise it has index > length/2.

Repeat it in loop, dividing remaining length/2 each time, and appropriately add/subtract center position,

and you have ultra fast algorithm finding in library of words..

 

I have used such for dictionary that had multi million entries.

You need just something like 22 comparison operations for 4 millions alphabetically sorted dictionary database.

 

Variations of this algorithm are octree

http://en.wikipedia.org/wiki/Octree

and kd-tree

http://en.wikipedia.org/wiki/K-d_tree

(typically input is 3d vector)

 

Without them, Hollywood/TV would be in '60-'70 years, without computer generated special F/X..

 

ps. Of course it doesn't have to be string. It could be integer, float, or vector, or whatever you like, as long as comparison operator possible to make.

Edited December 19, 2014 by Sensei

[Commander]

OK, thank you. I think we have some language barrier issues as 'wisecrack' refers to a joke and I don't understand a joke in the context of your reply. I would also point out that you said pen and paper were helpful and that implies visual clues.

 

Sensei can of course reply himself, however I'm unclear on what you have written. (Language barrier again perhaps.) What I get from it is that the solution for 39 balls [b₃₉ ] is 38 weighings [b_39-1 ]. However since we have solutions of as few as 5 weighings that doesn't make sense. Can you clarify?

 

I meant B_N to mean the number of Balls which can be solved in N Weighings.

 

For example I can solve 120 Balls in 5 Weighings which means B₅ = 120 !

 

That means if the given number of Balls are 120 instead of 39 the answer will be : 5 Weighings and the procedure to find that Culprit Ball in those 5 Weighings !!

 

That can be taken as a second Puzzle !!!