The Student Room Group

Scroll to see replies

cms271828
Then give a function W(N) that tells exactly what the MININUM number of weighings required is, to determine the odd ball, and if it is heavier or lighter.


You clearly asked for the minimum number of weighings required for any permutation. (and not the minimum number of weighings for all permutations)
cms271828
TRUE,BUT, what is it, heavy or lighter, u gotta say which


Oh, you didnt make it blatantly obvious in the original post?...

At the end add one weighing by comparing the odd ball out with a standard ball.
DaveManUK
better ver of 12.

(1:5 6:10 11 12) 1:5=6:10
(any(1:10) 11 12 ) any(1:10)=11 ==> 12 is the heavier or lighter

2 weighings!!


sorry for sloppy notation - 1:5 means balls of equal weight numbered 1 2 3 4 5.

so [1,2,3,4,5],[6,7,8,9,10],[11],[12] would be the groupings for the first weighing. weigh 1:5 and 6:10, they turn out to be equal.
Reply 23
DaveManUK
If (a b c D) where D is the odd one out that you need to compare whether the first three are the same, which will imply that the last D is of a different weight.

If a=b and a=c then you will know that D is the odd one out.

I think your going about it wrong
let me know if you wanna chat on yahoo messenger, and I'll explain it
better
Reply 24
u want to discuss this on yahoo messenger???
can do. i use msn messenger tho. try adding my email see if that works.
Reply 26
DaveManUK
You clearly asked for the minimum number of weighings required for any permutation. (and not the minimum number of weighings for all permutations)

Thats totally irrelevant
To clarify:
Suppose you have 12 balls, 11 of them weigh the same, whilst 1 of them is a different weight, maybe heavier, maybe lighter than the other balls.
Now, using balance scales 3 times, this odd ball must be found, and also if it is heavier or lighter must be determined by the end of the 3 weighings.

I answered that for any permutation the answer is trivial for finding the odd ball out. :smile:
Reply 28
cms271828
Hello mate,

Thanks for trying, but you have misunderstood the question, and I beleive
it is more difficult than you think.
....it cannot be done in 2 weighings, and I have the proof to show it can be done in 3.


First things first, I never said you can find the odd ball from 12 balls in just two weighs. Clearly this is impossible.

Secondly, I have not misunderstood this question, perhaps you didn't understand my solution.

Say we have N balls. Now N can be odd or even. If it is even then we are fine and we can proceed (as I will show...).

If N is odd then take out a random ball. (Not to worry, this ball is either the odd one or not). Then the remaining N-1 balls will be an even number of balls.

Split them up (ie. if we have 8 balls then take 4 balls from random and place them onto one scale, and the other 4 onto the remaining scale).

From this first weighing we have two observations:
1) If they weigh the same then the ball we took out at the very beginning is the odd one
2) If the odd ball is still in the N-1 balls then obviously one of the balances will weigh differently from the other. To find out which balance contains the odd ball just divide the total weight of one of the balances by the number of balls on the balance. If we don't get an integer value then the odd ball is in that balance.

Then just repeat this procedure, and this will ensure you get the minimum number of weighings in order to find the odd ball.

Then as DaveManUk said, to find if its lighter or heavier than the remaining just weigh it against a normal ball in the pile.
-----------------------

Also, DaveManUk, what halls are you in? I'm also staying in Evelyn Gardens (Fisher).
-----------------------

Galois.
Reply 29
Hi Galois,

Its not Evariste Galois is it, cuz he got shot, that'll teach him for inventing
group theory!!

Anyway, your solution doesnt make sense.
This is what I would like u to do. Say u have 12 balls. I tell u that 11
of them weigh the same, and 1 is either heavier ,or it is lighter than the others.
I want u to find this ball for me, and tell me which it is, heavier, or lighter.
I will allow you to use scales 3 times, no more.

Clearly, there are 24 possible outcomes that u may reach depending
which way the scales tip.

I believe from your method, you would first take 6 balls against 6 balls.
If so, then this is wrong. U know that the scales are gonna tip, cuz I told u
one of the balls is an oddball(different weight to others).
So the left side will either go down, telling u that either 1 of the 6 balls on
the left is heavy, or 1 of the 6 balls on the right is light.
Or it will go up, telling u that either 1 of the 6 balls on the left is light, or 1 of the 6 ball on the right is heavy.
So thats a bit of information, but its not that helpful, and you can do much better.

I'll leave it to you, keep trying good luck
Reply 30
cms271828
Hi Galois,

I believe from your method, you would first take 6 balls against 6 balls.
If so, then this is wrong. U know that the scales are gonna tip, cuz I told u
one of the balls is an oddball(different weight to others).
So the left side will either go down, telling u that either 1 of the 6 balls on
the left is heavy, or 1 of the 6 balls on the right is light.
Or it will go up, telling u that either 1 of the 6 balls on the left is light, or 1 of the 6 ball on the right is heavy.
So thats a bit of information, but its not that helpful ...


Please take a moment to read my solution fully, and then comment.

Galois.
Reply 31
cms271828
Hello mate,

Thanks for trying, but you have misunderstood the question, and I beleive
it is more difficult than you think.
from the N balls u have, all of them weigh the same, except 1 of them is a different weight, possibly heavier or lighter.
You dont have any more balls to use, just those N.
so when N=12, the minimum number of weighings u need to establish which ball is the odd one out, and whether it is heavier or lighter is 3.
it cannot be done in 2 weighings, and I have the proof to show it can be done in 3.
If you want to attempt this problem, I recommend you show how to find the odd one out with 12 balls, and say whether it is heavier or lighter, using balance scales 3 times, so there are obviously 24 different outcomes.
My question, is to find the minimum number of weighings required when you have N>=3 ball, to find the odd ball, and determine if it is heavier or lighter than the others.

Any questions, let me know.


If you are so sure about Galois' solution being incorrect then I do not see a point of you posting your query here as to seek reassurance for your personal solution. Perhaps this should help you to understand better.

Newton.
Reply 32
I don't believe we are told that the weight of the balls in an integer value.
Also, a beam balance doesn't actually gives weights. It is only used to balance two weights and therefore can be used to show that two weights are not equal.
Reply 33
Galois
Please take a moment to read my solution fully, and then comment.

Galois.

In your previous reply, in 2), you mention sumthing about dividing the total weight by the number of balls?
This is impossible, u cannot know the total weight, I haven't said how heavy
the balls are, and you are USING BALANCE SCALES, as I said in my original
question.
These don't weigh objects,but just compare weights.
So perhaps your solution would be correct using digital scales,
but they are not allowed.

Hope you understand.
Reply 34
Newton
If you are so sure about Galois' solution being incorrect then I do not see a point of you posting your query here as to seek reassurance for your personal solution. Perhaps this should help you to understand better.

Newton.

Why are u trying to patronise me with a definition of integer?
I know Galois' solution is wrong, because it is nonsense, he is talking about
dividing the total weight of the balls, but this is unknown, and we are
using BALANCE SCALES.
I know my solution to the 12 ball problem is correct, but I have extended
this problem to N balls, and wish to find the minimum number of weighings
needed, using a balance scale, to determine the oddball(which ever it is),
and also determine if it is heavier, or if it is lighter than the others.
So for N=12, the minimum number is 3, and I have proved this by obtaining
all of the 24 different outcomes.

If you like, we can go on messenger, and I'll show u directly. Ill get u to secretly choose a ball from 1-12,and choose it to be heavier or lighter.
Then with 3 weighings on BALANCE SCALES, I will tell u which ball u chose,
and if it is heavier or lighter.

Let me know please.
Reply 35
cms271828
In your previous reply, in 2), you mention sumthing about dividing the total weight by the number of balls?
This is impossible, u cannot know the total weight, I haven't said how heavy
the balls are, and you are USING BALANCE SCALES, as I said in my original
question.
These don't weigh objects,but just compare weights.
So perhaps your solution would be correct using digital scales,
but they are not allowed.

Hope you understand.


Balancing weights, aha :smile:. I prefer the digital age :p:

Galois.
Reply 36
cms271828
Here is a challenging puzzle for all you maths lovers, I came up with it myself,
kind of.
Suppose u have 12 balls, 11 of them weigh the same, whilst 1 of them is a different weight, maybe heavier, maybe lighter than the other balls.
Now, using balance scales 3 times, this odd ball may be found, and also if it is heavier or lighter can determined.
For those that want, you can try to prove this.

But here is my question,
Suppose you have N balls (N>=3), such that all of them weigh the same, except for 1 which is heavier or lighter than each of the others.
Then give a function W(N) that tells exactly what the MININUM number of weighings required is, to determine the odd ball, and if it is heavier or lighter.
So for example W(12)=3.
I'm pretty sure there is a log in there somewhere, I haven't had time to solve this myself, but would love to see someone elses proof, if possible

good luck


There is a paradox in the formulation of the question. Galois' solution was not wrong, given that he assumed digital scales; in a sense the weight must be a known quantaty as otherwise there is a very big number of permutations, although since this problem is purely logical one would not want to involve probability.

Now let us assume that we are given an even pile of balls i. e. where there is an even amount of balls. We shall be splitting the pile constantly into two piles until we find the right ball, now since we are talking about finding the MINIMUM number of turns, we must assume a perfect situation where each time we pick the pile with the right ball in it, be it heavier or lighter.

For example, if we have twelve balls, it follows,

12->6, 6->3, 3->2, 1

Now we weigh the last 2 balls in the last step to see if they are of equal weight. If they are that means that the "1" ball in the last step was the odd one out. So,

12->6, 6->3, 3->2, 1 (+1) (4)

Observe the similar patterns,

16->8, 8->4, 4->2, 2->1, 1 (4)

32->16, 16->8, 8->4, 4->2, 2->1, 1 (5)

It can be seen that for any number of balls, N, the number of steps there is to finding the right ball is to what power two must be raised to give us N,

(2^x)=N

=>x~(logN/log2)

=>f(N)=(logN/log2)

Although in a case where N is not a power of 2, at the end we shall always end up with three balls, be N odd or even, and we need to weigh those balls against each other. If we are left with A, B, C, we need to weight A against B, B against C, and C against A, so in such a case f(N) becomes,

f(N)=(logN/log2)+3

Newton.
Reply 37
Newton
There is a paradox in the formulation of the question. Galois' solution was not wrong, given that he assumed digital scales; in a sense the weight must be a known quantaty as otherwise there is a very big number of permutations, although since this problem is purely logical one would not want to involve probability.

Now let us assume that we are given an even pile of balls i. e. where there is an even amount of balls. We shall be splitting the pile constantly into two piles until we find the right ball, now since we are talking about finding the MINIMUM number of turns, we must assume a perfect situation where each time we pick the pile with the right ball in it, be it heavier or lighter.

For example, if we have twelve balls, it follows,

12->6, 6->3, 3->2, 1


Now we weigh the last 2 balls in the last step to see if they are of equal weight. If they are that means that the "1" ball in the last step was the odd one out. So,

12->6, 6->3, 3->2, 1 (+1) (4)

Observe the similar patterns,

16->8, 8->4, 4->2, 2->1, 1 (4)

32->16, 16->8, 8->4, 4->2, 2->1, 1 (5)

It can be seen that for any number of balls, N, the number of steps there is to finding the right ball is to what power two must be raised to give us N,

(2^x)=N

=>x~(logN/log2)

=>f(N)=(logN/log2)

Although in a case where N is not a power of 2, at the end we shall always end up with three balls, be N odd or even, and we need to weigh those balls against each other. If we are left with A, B, C, we need to weight A against B, B against C, and C against A, so in such a case f(N) becomes,

f(N)=(logN/log2)+3

Newton.

Great stuff Newton, but..............
U have to say explicity wether the oddball is heavier or
if the oddball is lighter, obviously it is (heavier or lighter) since it
is the oddball.
So using your method, how many weighings does it take you to find
the oddball from 12balls, and also say if it is heavier, or if it is lighter.

looking forward to your answer.
Reply 38
For 12:

Weigh 1,2,3,4 against 5,6,7,8

If they balance then one of 9,10,11,12 is odd.
Weigh 1,2,3 against 9,10,11.
If they balance then 12 is odd. Weigh against 1 to find if it's heavy or light.
If they don't balance then let's suppose 9,10,11 is heavier (a similar argument can be used if it's lighter). Weigh 9 against 10. If they balance then you know 11 is heavy. If they don't then the heavier one is the odd ball.

If 1,2,3,4 against 5,6,7,8 doesn't balance then suppose 1,2,3,4 is heavier (if 5,6,7,8 is heavy then switch the labels around).
Weigh 1,2,5 against 3,6,9
If they balance then either 4 is heavy or 7 is light or 8 is light. Weigh 7 against 8. If they balance then 4 is heavy. If they don't then the lighter one is the odd ball.
If 1,2,5 against 3,6,9 doesn't balance consider two cases:

1,2,5 is heavier than 3,6,9:
Either 1 is heavy or 2 is heavy or 6 is light. Weigh 1 against 2 to determine the odd ball and its weight.

1,2,5 is lighter than 3,6,9:
Either 5 is light or 3 is heavy. Weigh 5 against 12. If it balances then 3 is heavy. If it doesn't then 5 is light.
Reply 39
SsEe
For 12:

Weigh 1,2,3,4 against 5,6,7,8

If they balance then one of 9,10,11,12 is odd.
Weigh 1,2,3 against 9,10,11.
If they balance then 12 is odd. Weigh against 1 to find if it's heavy or light.
If they don't balance then let's suppose 9,10,11 is heavier (a similar argument can be used if it's lighter). Weigh 9 against 10. If they balance then you know 11 is heavy. If they don't then the heavier one is the odd ball.

If 1,2,3,4 against 5,6,7,8 doesn't balance then suppose 1,2,3,4 is heavier (if 5,6,7,8 is heavy then switch the labels around).
Weigh 1,2,5 against 3,6,9
If they balance then either 4 is heavy or 7 is light or 8 is light. Weigh 7 against 8. If they balance then 4 is heavy. If they don't then the lighter one is the odd ball.
If 1,2,5 against 3,6,9 doesn't balance consider two cases:

1,2,5 is heavier than 3,6,9:
Either 1 is heavy or 2 is heavy or 6 is light. Weigh 1 against 2 to determine the odd ball and its weight.

1,2,5 is lighter than 3,6,9:
Either 5 is light or 3 is heavy. Weigh 5 against 12. If it balances then 3 is heavy. If it doesn't then 5 is light.


ABSOLUTELY SPOT ON
Good work, it is exactly the same as my solution, except when 1,2,3,4
doesnt balance with 5,6,7,8, (say 1,2,3,4 goes down)
I weigh 1,2,5 against 3,4,6, this eliminates 3,4,5.
But either way is fine.
Next try to find the minimal number of weighings necessary for n>=3 balls
so in this case W(12)=3, W(13)=4.
I haven't done this yet, but I am workign on it.
Thanks for your help.

Latest