flat assembler
Message board for the users of flat assembler.

 Index > Heap > [puzzle] Find the oddball Goto page 1, 2  Next
Author
TmX

Joined: 02 Mar 2006
Posts: 821
Location: Jakarta, Indonesia
TmX
Me and some friends are discussing this puzzle:
Quote:

You are given 12 tennis balls. All of them have the same weights, except one, which is possibly either lighter or heavier than the rest of the balls.
Given a scale, you have to find the oddball exactly in 3 attempts of weighing.

We draw several decision trees, and so far our conclusion is it is not always possible to do that in 3 attempts.
But 4 attempts is always possible.

Of course, if the problem is altered a bit so that oddball is heavier, or that oddball is lighter,
then we could exactly solve it in 3 attempts.

I wounder if we could take a rather formal approach, maybe mathematical induction of proof by contradiction.
Any ideas?
08 Feb 2014, 03:05
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17287
revolution
Google for 12 coins (not tennis balls) and finding the counterfeit coin and you can find the answer. It can also be solved in three weightings without even knowing the results of any of the previous weightings until after all three are done. You just have to say in advance which coins to put on which side of the scale for three times and then analyse the results and state which coin is the fake, and whether it is heavier or lighter than the others.

It can also be extended to four weightings and using 39 coins (or balls, or whatever). And five weightings and 120 objects. Once you know the method and spot the pattern you will then see how.
08 Feb 2014, 03:29
tthsqe

Joined: 20 May 2009
Posts: 729
tthsqe
The problem is not clear: do we have a balance that tells which pile weighs more? or do we have a scale that gives of the weight of a pile? I think this issue needs to be settled first..
08 Feb 2014, 07:49
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17287
revolution
This is using a balance scale, with a weighing pan on each side.
08 Feb 2014, 08:08
tthsqe

Joined: 20 May 2009
Posts: 729
tthsqe
Ok - in that case it might be possible. I assume that the problem is to find out, from a pile of 12 balls, whether
- all the balls have same weight
- one ball weighs more, and to find this ball
- one ball weights less, and to find this ball
There are 25 ( = 1+2*12) possible cases for the balls, and three trials can distinguish 27 (=3^3) cases. Does Revolution have a proof that 13 balls necessitates more than 3 trials?
08 Feb 2014, 08:26
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17287
revolution
tthsqe wrote:
Does Revolution have a proof that 13 balls necessitates more than 3 trials?
I do. And once you solve this you will have a proof also.
08 Feb 2014, 08:32
tthsqe

Joined: 20 May 2009
Posts: 729
tthsqe
Ah, if you have n trials, you can do at least 3 + 3^2 + ... + 3^(n-1) balls. Still not absolutely sure about the 'at most' part.
08 Feb 2014, 09:10
tthsqe

Joined: 20 May 2009
Posts: 729
tthsqe
Revolution, I am convinced by induction that (3^n-3)/2 is a valid lower bound, and we have the trivial upper bound of (3^n-1)/2. For what reason is (3^n-3)/2 an upper bound as well?
08 Feb 2014, 12:53
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17287
revolution
tthsqe wrote:
Revolution, I am convinced by induction that (3^n-3)/2 is a valid lower bound, and we have the trivial upper bound of (3^n-1)/2. For what reason is (3^n-3)/2 an upper bound as well?
I think if you are asking this then you haven't solved the problem as stated? Because (3^n-1)/2 is not divisible by 3.Anyhow in case someone doesn't want to see the clue I have hidden the answer in this post.
08 Feb 2014, 13:16
sleepsleep

Joined: 05 Oct 2006
Posts: 8906
Location: ˛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
12 balls,
divided to 3 groups,

(A)1,2,3,4 --- (B)5,6,7,8 --- (C)9,10,11,12
[1]weight A and B

+-> if same, means in C
| [2]weight 9,10 and 11,12
| then [3]weight 9 with 10 or 11 with 12
|

but if lighter or heavier is unknown, could we still solve it in 3 times?
08 Feb 2014, 14:15
tthsqe

Joined: 20 May 2009
Posts: 729
tthsqe
yes!
...
[2] compare 9+10 to 1+2
[3] compare 9 to 1, ect.
08 Feb 2014, 14:27
sleepsleep

Joined: 05 Oct 2006
Posts: 8906
Location: ˛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
if weight is not same in step 1, means oddball inside 1,2,3,4 and 5,6,7,8
assume the first weight would be group 1 (X), group 2 (Y), third group (X or Y) is unknown.

if second step, weight 1,2,3,9 with 5,6,7,10
the result would be (X,X), (X,Y), (Y,Y),(Y,X)
if (X,X) or (Y,Y) means, last step is weight ball 4 and 8 (we already know weight for each ball after step 2)

what if (X,Y) or (Y,X)
08 Feb 2014, 14:40
sleepsleep

Joined: 05 Oct 2006
Posts: 8906
Location: ˛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
it dones't work,

Last edited by sleepsleep on 08 Feb 2014, 14:52; edited 1 time in total
08 Feb 2014, 14:49
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17287
revolution
sleepsleep: Can you make your test unconditional? That is, lay out all your three weighing steps first and then someone does the weighings and gives you all the results later.
08 Feb 2014, 14:52
tthsqe

Joined: 20 May 2009
Posts: 729
tthsqe
@ revolution, I've eliminated the possibility of (3^n-1)/2, so the problem is solved, but the hint that you hid was completely useless to me. Maybe our methods are different?

@ sleepsleep, If you have solved the case of three trials on the balance, see how many balls you can do with an arbitrary (n) number of trials on balance.
08 Feb 2014, 14:55
sleepsleep

Joined: 05 Oct 2006
Posts: 8906
Location: ˛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
This is using a balance scale, with a weighing pan on each side.
does weight measure let me know weight unit of 2 groups or just which one is heavier or lighter?

i am confuse with this one,
08 Feb 2014, 15:20
tthsqe

Joined: 20 May 2009
Posts: 729
tthsqe
it like the cmp + (je|ja|jb) operator. it tells you if the right side is heavier, the left side is heavier, or they are both the same. three possibilities.
There may or may not be an oddball, and if there is one, you have to find it and tell if it is heavier or lighter.
08 Feb 2014, 15:25
sleepsleep

Joined: 05 Oct 2006
Posts: 8906
Location: ˛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
i am confuse in such a way,

weight = put something on top, and let me know the weight unit in g, kg

or

weight = u got 2 pan (so u could compare 2 groups), and the scale only tell u which on is heavier or lighter.
08 Feb 2014, 15:33
tthsqe

Joined: 20 May 2009
Posts: 729
tthsqe
it is the second one
08 Feb 2014, 15:42
sleepsleep

Joined: 05 Oct 2006
Posts: 8906
Location: ˛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
if let say, 2 pans,
(A)[1][2][3][4] vs (B)[5][6][7][8]
if both same, means oddball in [9][10][11][12]
if one is heavy or light, we still got no idea the oddball is light or heavy,
possible result, H = heavy, L = light
(A.H)(B.L)
(A.L)(B.H)

(B)[5][6][7][8] vs (C)[9][10][11][12]
(B.H)(C.L)
(B.L)(C.H)

if oddball in A is light === (A.L)(B.H) and (C.H)
if oddball in A is heavy === (A.H)(B.L) and (C.L)

if oddball in B is light === (A.H)(B.L) and (C.H)
if oddball in B is heavy === (A.L)(B.H) and (C.L)

if oddball in C is light === (A.H)(B.H) and (C.L)
if oddball in C is heavy === (A.L)(B.L) and (C.H)

based on this, we could know where the oddball group and if it is light or heavy,

but how to identified it in 3 measure,.... we used 2 measures already, last measure....how?
08 Feb 2014, 15:49
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area
Goto page 1, 2  Next

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum