flat assembler
Message board for the users of flat assembler.
Index
> Heap > [puzzle] Find the oddball Goto page 1, 2 Next 
Author 

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
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
This is using a balance scale, with a weighing pan on each side.


08 Feb 2014, 08:08 

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
tthsqe wrote: Does Revolution have a proof that 13 balls necessitates more than 3 trials? 

08 Feb 2014, 08:32 

tthsqe
Ah, if you have n trials, you can do at least 3 + 3^2 + ... + 3^(n1) balls. Still not absolutely sure about the 'at most' part.


08 Feb 2014, 09:10 

tthsqe
Revolution, I am convinced by induction that (3^n3)/2 is a valid lower bound, and we have the trivial upper bound of (3^n1)/2. For what reason is (3^n3)/2 an upper bound as well?


08 Feb 2014, 12:53 

revolution
tthsqe wrote: Revolution, I am convinced by induction that (3^n3)/2 is a valid lower bound, and we have the trivial upper bound of (3^n1)/2. For what reason is (3^n3)/2 an upper bound as well? 

08 Feb 2014, 13:16 

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
yes!
... [2] compare 9+10 to 1+2 [3] compare 9 to 1, ect. 

08 Feb 2014, 14:27 

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
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
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
@ revolution, I've eliminated the possibility of (3^n1)/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
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
it like the cmp + (jejajb) 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
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
it is the second one


08 Feb 2014, 15:42 

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 

Goto page 1, 2 Next < Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar. Also on YouTube, Twitter.
Website powered by rwasa.