flat assembler
Message board for the users of flat assembler. Index > Heap > [puzzle] Find the oddball Goto page Previous  1, 2
Author
 Thread  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)    vs (B)
2M measure (A) vs (B)
3M measure (A)    vs (B)

assume oddball is (A.H)
1M = (A.H) (B.L)
2M = (A.H) means ball in 
(A.L) means ball in 

assume oddball is (A.L)
1M = (A.L) (B.H)
2M = (A.L) means ball in 
(A.H) means ball in 

assume oddball is (B.H)
1M = (A.L) (B.H)
2M = (A.L) means ball in 
(A.H) means ball in 

assume oddball is (B.L)
1M = (A.H) (B.L)
2M = (A.H) means ball in 
(A.L) means ball in 
```

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) vs (B)
same equal odd ball in 
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) vs (B)
if they are different then you know that every ball in  is a good ball. I would then try the comparisons
 vs 
 vs 
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) vs (B)
2M (A)    vs (B)
3M (A)      vs (B)

1M if same means oddball in 
2M if same means oddball in 
3M if same means oddball in  if different means oddball is 
```

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 Location: In your JS exploiting you and your system revolution sleepsleep wrote:ok, i found some insight using this method Code:```1M (A) vs (B) 2M (A) vs (B) 3M (A) vs (B) 1M if same means oddball in  2M if same means oddball in  3M if same means oddball in  if different means oddball is  ``` 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 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? 08 Feb 2014, 19:22
 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. 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) vs (B)
2M (A)    vs (B)
3M (A)      vs (B)

1M if same means oddball in 
2M if same means oddball in 
3M if same means oddball in  if different means oddball is 
```

Quote:

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

if  is balance with , then no doubt,  is oddball.

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

Code:
```1M (A) vs (B)

balance   = oddball inside  to 
unbalance = oddball inside  to 

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

2M (A) vs (B)
balance   = oddball inside  or 
unbalance = oddball inside  or 

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

3M (A) vs (B)
assume (A) < (B) in 3M
then  is oddball
assume (A) == (B) in 3M
then  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 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. 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