flat assembler
Message board for the users of flat assembler.

 Index > Heap > [puzzle] Find the oddball Goto page Previous  1, 2
Author
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   (*-+)
>
....
<
...
>
...      ```
08 Feb 2014, 16:23
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.
08 Feb 2014, 16:41
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?
```
08 Feb 2014, 16:47
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.
08 Feb 2014, 16:49
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.
08 Feb 2014, 17:01
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?
08 Feb 2014, 17:02
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).
08 Feb 2014, 17:18
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17279
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?
You didn't even put number 12 on the scale so how would you know if it is heavier, lighter or same?
08 Feb 2014, 19:20
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17279
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?
08 Feb 2014, 19:22
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17279
revolution
tthsqe wrote:
Maybe our methods are different?
I would be keen to see different/new methods to solve this also.
08 Feb 2014, 19:31
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.
08 Feb 2014, 20:08
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
```
08 Feb 2014, 21:30
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)?
08 Feb 2014, 22:02
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17279
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.
09 Feb 2014, 04:41
 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 Previous  1, 2

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