flat assembler
Message board for the users of flat assembler.

Index > Heap > [puzzle] Find the oddball

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
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.

Instead of making decision trees,
I wounder if we could take a rather formal approach, maybe mathematical induction of proof by contradiction.
Any ideas?
Post 08 Feb 2014, 03:05
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17341
Location: In your JS exploiting you and your system
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.
Post 08 Feb 2014, 03:29
View user's profile Send private message Visit poster's website Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
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..
Post 08 Feb 2014, 07:49
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17341
Location: In your JS exploiting you and your system
revolution
This is using a balance scale, with a weighing pan on each side.
Post 08 Feb 2014, 08:08
View user's profile Send private message Visit poster's website Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
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?
Post 08 Feb 2014, 08:26
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17341
Location: In your JS exploiting you and your system
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.
Post 08 Feb 2014, 08:32
View user's profile Send private message Visit poster's website Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
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.
Post 08 Feb 2014, 09:10
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
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?
Post 08 Feb 2014, 12:53
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17341
Location: In your JS exploiting you and your system
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.
Post 08 Feb 2014, 13:16
View user's profile Send private message Visit poster's website Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 8958
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?
Post 08 Feb 2014, 14:15
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
yes!
...
[2] compare 9+10 to 1+2
[3] compare 9 to 1, ect.
Post 08 Feb 2014, 14:27
View user's profile Send private message Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 8958
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)
Post 08 Feb 2014, 14:40
View user's profile Send private message Reply with quote
sleepsleep



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


Last edited by sleepsleep on 08 Feb 2014, 14:52; edited 1 time in total
Post 08 Feb 2014, 14:49
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17341
Location: In your JS exploiting you and your system
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.
Post 08 Feb 2014, 14:52
View user's profile Send private message Visit poster's website Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
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.
Post 08 Feb 2014, 14:55
View user's profile Send private message Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 8958
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,
Post 08 Feb 2014, 15:20
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
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.
Post 08 Feb 2014, 15:25
View user's profile Send private message Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 8958
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.
Post 08 Feb 2014, 15:33
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 730
tthsqe
it is the second one
Post 08 Feb 2014, 15:42
View user's profile Send private message Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 8958
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?
Post 08 Feb 2014, 15:49
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.