flat assembler
Message board for the users of flat assembler.

Index > Heap > [puzzle] Find the oddball

Goto page Previous  1, 2
Author
Thread Post new topic Reply to topic
tthsqe



Joined: 20 May 2009
Posts: 724
tthsqe
if you want to make a decision tree, it could start like this
Code:
1+2+3+4 ? 5+6+7+8
        = 9+11 ? 10+7
               = 12 ? 10
                    = no odd ball           (***)
                    < 12 is underweight     (**-)
                    > 12 is overweight      (**+)
               < 8+12 ? 9+10
                      =  11 is underweight  (*-*)
                      <  10 is overweight   (*--)
                      >  9 is underweight   (*-+)
               >
                 ....
        <
           ...
        >
           ...      
Post 08 Feb 2014, 16:23
View user's profile Send private message Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 8902
Location: ˛                             ⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
6 vs 6
Code:
1M measure (A)[1][2][3][4][5][6]    vs (B)[7][8][9][10][11][12]
2M measure (A)[1][2][3][10][11][12] vs (B)[7][8][9][4][5][6]
3M measure (A)[1][2][3][7][8][9]    vs (B)[4][5][6][10][11][12]

assume oddball is (A.H)
1M = (A.H) (B.L)
2M = (A.H) means ball in [1][2][3]
     (A.L) means ball in [4][5][6]


assume oddball is (A.L)
1M = (A.L) (B.H)
2M = (A.L) means ball in [1][2][3]
     (A.H) means ball in [4][5][6]

assume oddball is (B.H)
1M = (A.L) (B.H)
2M = (A.L) means ball in [7][8][9]
     (A.H) means ball in [10][11][12]

assume oddball is (B.L)
1M = (A.H) (B.L)
2M = (A.H) means ball in [7][8][9]
     (A.L) means ball in [10][11][12]
    

i guess i am near, but without knowing it is heavier or lighter seems like a problem to solve it in 3 measures.
Post 08 Feb 2014, 16:41
View user's profile Send private message Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 8902
Location: ˛                             ⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
tthsqe wrote:
if you want to make a decision tree, it could start like this
Code:
1+2+3+4 ? 5+6+7+8
        = 9+11 ? 10+7
               = 12 ? 10
                    = no odd ball           (***)
                    < 12 is underweight     (**-)
                    > 12 is overweight      (**+)
               < 8+12 ? 9+10
                      =  11 is underweight  (*-*)
                      <  10 is overweight   (*--)
                      >  9 is underweight   (*-+)
               >
                 ....
        <
           ...
        >
           ...      


Code:
(A)[1][2][3][4] vs (B)[5][6][7][8]
same equal odd ball in [9][10][11][12]
different = which set? A or B, oddball is heavy or light?
    
Post 08 Feb 2014, 16:47
View user's profile Send private message Reply with quote
TmX



Joined: 02 Mar 2006
Posts: 821
Location: Jakarta, Indonesia
TmX
sleepsleep wrote:

i guess i am near, but without knowing it is heavier or lighter seems like a problem to solve it in 3 measures.


That is my point, exactly.
Actually this has been the problem since the beginning.
Let's say first you want to weigh 6 vs 6 balls. Sure it will not be balanced.
Unfortunately we don't know which ball is the culprit, which is either lighter or heavier.
Post 08 Feb 2014, 16:49
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 724
tthsqe
guys, the problem is solvable in 3 weighings even if you don't know if the oddball is overweight or underweight, or even there is no oddball. I don't want to give it away.

(A)[1][2][3][4] vs (B)[5][6][7][8]
if they are different then you know that every ball in [9][10][11][12] is a good ball. I would then try the comparisons
[1][5][9] vs [2][3][7]
[2][5] vs [1][6]
this is enough info to find the possible odd ball.
Post 08 Feb 2014, 17:01
View user's profile Send private message Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 8902
Location: ˛                             ⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
ok, i found some insight using this method
Code:
1M (A)[1][2][3] vs (B)[4][5][6]
2M (A)[7][8]    vs (B)[9][10]
3M (A)[11]      vs (B)[1]

1M if same means oddball in [7][8][9][10][11][12]
2M if same means oddball in [11][12]
3M if same means oddball in [12] if different means oddball is [11]
    


i guess this pretty much could solve =)

could revolution gives me a star? Laughing
Post 08 Feb 2014, 17:02
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
I claim that you can point out which of tennis balls is lighter or heavier than others only in one weighing, doesn't matter how many balls you have (a kind of pun, lol).

You can drop all balls into a big aquarium filled with water and after some time you will see which of the balls is submerged differently than others (lighter ball will be less submerged, heavier will be more submerged).
Post 08 Feb 2014, 17:18
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17279
Location: In your JS exploiting you and your system
revolution
sleepsleep wrote:
ok, i found some insight using this method
Code:
1M (A)[1][2][3] vs (B)[4][5][6]
2M (A)[7][8]    vs (B)[9][10]
3M (A)[11]      vs (B)[1]

1M if same means oddball in [7][8][9][10][11][12]
2M if same means oddball in [11][12]
3M if same means oddball in [12] if different means oddball is [11]
    


i guess this pretty much could solve =)

could revolution gives me a star? Laughing
You didn't even put number 12 on the scale so how would you know if it is heavier, lighter or same?
Post 08 Feb 2014, 19:20
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17279
Location: In your JS exploiting you and your system
revolution
MHajduk wrote:
I claim that you can point out which of tennis balls is lighter or heavier than others only in one weighing, doesn't matter how many balls you have (a kind of pun, lol).

You can drop all balls into a big aquarium filled with water and after some time you will see which of the balls is submerged differently than others (lighter ball will be less submerged, heavier will be more submerged).
Cool, only the availability of an aquarium was not stated in the problem. Also, what if a heavier ball is also slightly larger and thus the amount the ball submerses is the same as the others?
Post 08 Feb 2014, 19:22
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17279
Location: In your JS exploiting you and your system
revolution
tthsqe wrote:
Maybe our methods are different?
I would be keen to see different/new methods to solve this also.
Post 08 Feb 2014, 19:31
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
revolution wrote:
Also, what if a heavier ball is also slightly larger and thus the amount the ball submerses is the same as the others?
Aren't tennis balls normalized in diameter?
A tennis ball is a ball designed for the sport of tennis, approximately 6.7 cm (2.63 in.) in diameter. Tennis balls are yellow at major sporting events, but in recreational play can be virtually any color.
Post 08 Feb 2014, 20:08
View user's profile Send private message Visit poster's website Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 8902
Location: ˛                             ⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
Code:
1M (A)[1][2][3] vs (B)[4][5][6]
2M (A)[7][8]    vs (B)[9][10]
3M (A)[11]      vs (B)[1]

1M if same means oddball in [7][8][9][10][11][12]
2M if same means oddball in [11][12]
3M if same means oddball in [12] if different means oddball is [11] 
    


Quote:

You didn't even put number 12 on the scale so how would you know if it is heavier, lighter or same?

if [11] is balance with [1], then no doubt, [12] is oddball.

the above solution is with the assumption, they are balance in 1M, 2M and 3M,
for unbalance approach,

Code:
1M (A)[1][2][3] vs (B)[4][5][6]

balance   = oddball inside [7] to [12]
unbalance = oddball inside [1] to [6]

but we obtain information
(A) is heavier or
(B) is heavier

2M (A)[1][4] vs (B)[2][5]
balance   = oddball inside [3] or [6]
unbalance = oddball inside [1][4] or [2][5]


assume (A) < (B) in 1M
assume (A) < (B) in 2M
[1][4] < [2][5] means [4] and [2] are normal ball.
odd ball [1] or [5]

        3M (A)[1] vs (B)[2]
        assume (A) < (B) in 3M
                then [1] is oddball
        assume (A) == (B) in 3M
                then [5] is oddball
    
Post 08 Feb 2014, 21:30
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 724
tthsqe
revolution, if you go with the conditional (decision tree) approach, you don't nec. have to put each ball on the scale in each path through the decision tree. If you use an unconditional approach, I would assert that you do need to put each ball on the balance at least once to determine if there is an oddball and if the oddball is underweight/overweight.

Here is another fundamental question: It should be plain that the conditional approach can correctly decide upon just as many balls as an unconditional approach; can an conditional approach decide upon more balls than an unconditional approach (assuming the total number of weighings is the same)?
Post 08 Feb 2014, 22:02
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17279
Location: In your JS exploiting you and your system
revolution
Okay the puzzle here is slightly easier than the one I did with coins.

For the coin puzzle it states: That all coins might be the same weight. And also that you must determine if a coin is heavier or lighter (or same) so you can't assume anything about a coin that has not been on the scale.

So in this case okay, not all balls must go on the scale. But I would encourage you to think of a general solution that produces a stronger result than just assuming the nature of the last ball.
tthsqe wrote:
Here is another fundamental question: It should be plain that the conditional approach can correctly decide upon just as many balls as an unconditional approach; can an conditional approach decide upon more balls than an unconditional approach (assuming the total number of weighings is the same)?
If you use a strong unconditional method then twelve balls can be determined. And with the puzzle stated here you could then assume the nature of a thirteenth ball. An optimal conditional method could not improve upon thirteen.
Post 09 Feb 2014, 04:41
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2

< 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.

Powered by rwasa.