DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

Weigh 3 vs 3. If it doesn't balance, swap another 3 in for one of the sets, and now you know which set has the odd ball and whether it's lighter or heavier. Finish in the obvious way.

If it does balance, swap another 3 in. If it doesn't balance, same as before. If it does balance, then it's in one of the 3 you haven't weighed yet. This is much better than my previous attempts, but since we don't know if the odd ball out is lighter or heavier it's still not good enough.

Best I've got here is to take two of them and weigh them against two of the others. If it balances then it's the one you haven't touched yet, and if it doesn't then you've got a 50% chance between the two you added. I'm up to 11/12 success, just need a little time (or a little prodding... )


Edit: Ah ha, I've got it!

How about starting with 4 vs 4. If it balances then you weigh 3 of those against 3 of the remaining 4. If it still balances, then it's the one you haven't touched yet. Otherwise it's one of the new 3, and you know whether it's lighter or heavier, so finish in the obvious way*.

If it doesn't balance, rotate 3 through**. If it now doesn't balance the other way, you know it's in one of the 3 you moved, and whether it's lighter or heavier. Finish in the obvious way. If it now balances, you know it's in one of the 3 you removed, and whether it's lighter or heavier. Finish in the obvious way. And that's all she wrote

*Obvious way is, since we know whether it's lighter or heavier, weigh two of the 3 against each other, and draw the obvious conclusion

**Rotate 3 through means remove 3 from the left side, move 3 from the right to the left, and put 3 of the unused ones on the left

Edit 2: I just realized I forgot to handle if it still doesn't balance in the same direction. This means it's one of the two you didn't move around, so weigh either of them against any other ball. If they balance, it's the one you didn't weigh and you know whether it was lighter or heavier, and if it doesn't than it's the one you DID weigh and you know whether it was lighter or heavier.

[Edited by DiMono on 01-05-2004 at 05:56 AM GMT]

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

Scott
Level: Smitemaster
Rank Points: 578
Registered: 02-12-2003
IP: Logged

I tried this but it only works if the first 8 are all the same.

Weigh 4 and 4.
If they balance weigh any 3 with 3 of the remaining ones.
If they balance the one left is the odd one out. Weigh it with any other to see if its heavier or lighter.
If they don't balance you now know if the odd one is heavier or lighter. Weigh any 2 of the last 3. If they balance the one you removed was the odd one out if they don't then you can see the odd one.

However if the first 8 don't balance I can't get it in 2 more tries.

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

DiMono wrote:
Edit: Ah ha, I've got it!

How about starting with 4 vs 4. If it balances then you weigh 3 of those against 3 of the remaining 4. If it still balances, then it's the one you haven't touched yet. Otherwise it's one of the new 3, and you know whether it's lighter or heavier, so finish in the obvious way*.

If it doesn't balance, rotate 3 through**. If it now doesn't balance the other way, you know it's in one of the 3 you moved, and whether it's lighter or heavier. Finish in the obvious way. If it now balances, you know it's in one of the 3 you removed, and whether it's lighter or heavier. Finish in the obvious way. And that's all she wrote

*Obvious way is, since we know whether it's lighter or heavier, weigh two of the 3 against each other, and draw the obvious conclusion

**Rotate 3 through means remove 3 from the left side, move 3 from the right to the left, and put 3 of the unused ones on the left

Edit 2: I just realized I forgot to handle if it still doesn't balance in the same direction. This means it's one of the two you didn't move around, so weigh either of them against any other ball. If they balance, it's the one you didn't weigh and you know whether it was lighter or heavier, and if it doesn't than it's the one you DID weigh and you know whether it was lighter or heavier.

And that's correct. Your turn.

Since this may be a little unclear, here's the solution written with a little more detail.

Weigh 4 against 4. If the scales balance, all the balls are normal. Weigh 3 of them against 3 of the last ones. If the scales balance, the last ball is the odd one out. Weigh it against any other ball. If the scales don't balance, one of the 3 new balls is the odd one out, and you know whether is is lighter or heavier. Weigh 2 of them against each other.

If the scales don't balance in the first weighing, call the balls on the heavy side "black" and the balls one the light side "white". The last four balls are normal. Now weigh one black and three white (right side) against one white and three normal (left side). Three black balls have been put aside.

If the scales balance, one of the three black balls put aside is the odd one out, and it's heavier. Weigh 2 of them against each other.

If the right side goes up, one of the three white balls on this side is too light. Weigh 2 of them against each other.

If the left side goes up, the white ball on this side is too light, or the black ball on the other side is too heavy. Weigh one of them against a normal ball.

____________________________
Today the refrigerator, tomorrow the world!

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

Wow, that's a lot more simple than my solution. However, my solution satisfies an extra unspecified condition - so I think I know what my next puzzle will be.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged

Nobody, give Schik a puzzle he can solve.

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....

Nobody
Level: Roachling
Rank Points: 10
Registered: 01-06-2004
IP: Logged

Ok, then this is out.

Avon
Level: Delver
Rank Points: 47
Registered: 12-06-2003
IP: Logged

Nobody, The_Red_Hawk wanted you to give Schik a puzzle he could solve. You should really have chosen something easier just to be sure.

I hope Schik can solve them, though.

[Edited by Avon on 01-06-2004 at 02:12 AM GMT: I realised Nobody had given four puzzles]

____________________________
"Les hommes ne sont jamais plus ingénieux que dans l'invention des jeux." -- Gottfried Wilhelm Leibniz

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

Since we seem to be on a balls binge, here's a puzzle along the same vein:

You are given five balls, one of which is slightly heavier than the others. You are also given three scales that look the same, which may each be used exactly once. One scale is balanced, one measures too much on the right, and one measures too much on the left. You do not know which scale is which, and when empty they all balance.

The amount the scales are overbalanced by is the same as the difference between the heavy ball and the rest. If the heavy ball is 5 grams heavier than the others, the unbalanced scales are unbalanced by 5 grams as well. This means if a scale favours the left side, and you're weighing the heavy ball against another with the heavy ball on the right, the scale will balance.

What is the greatest % accuracy you can arrange for, and how do you do it?

Since this is a little confusing, I'll give an example scenario. You weigh two balls against each other, and it leans to the left. This means any of 3 things:

1) The scale is balanced, and the ball on the left is the heavy ball.
2) The scale is unbalanced to the left, and the balls are the same.
3) The scale is unbalanced to the left, and the ball on the left is the heavy ball.

For the purpose of this puzzle, you can't see a visible difference between scenario 2 and scenario 3, as that would make it far too easy.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

It seems like you can always tell which one's heavy:

Number the balls 1 through 5. First weigh 1,2 against 3,4, and then weigh 1,3 against 2,4. If either of these balance, weigh the other one again.

Okay, let's stop and see what's happening. Suppose 1,2 against 3,4 balances; then we have two weighings of 1,3 against 2,4. If we get two lefts, then 1 is heavy. If we get two rights, 4 is heavy. If we get one left and one right, then 5 is heavy. If we get one left and a balance, 3 is heavy, and if we get one right and a balance, 2 is heavy. These aren't too hard to check. (If instead you had weighed 1,2 against 3,4 twice with 1,3 against 2,4 balancing, just switch 2 with 3 everywhere in the answer.)

All right. Suppose instead that both our initial weighings came out left. Then the heavy one is 1. If both initial weighings came out right, then 4 is heavy.

Suppose 1,2 against 3,4 came out left and 1,3 against 2,4 came out right. Then the heavy one is either 2 or 5. Put them both on the scale. If 5 is heavy, then this scale is normal, so it'll lean towards it. If 2 is heavy, it won't lean towards the 5. Likewise if 1,2 against 3,4 came out right and 1,3 against 2,4 came out left. Then the heavy one is 3 or 5; if the last weighing leans towards 5, it's heavy; otherwise 3 is.

[Edited by bibelot on 01-06-2004 at 06:25 AM GMT]

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

bibelot wrote:
Suppose 1,2 against 3,4 came out left and 1,3 against 2,4 came out right. Then the heavy one is either 2 or 5. Put them both on the scale. If 5 is heavy, then this scale is normal, so it'll lean towards it. If 2 is heavy, it won't lean towards the 5. Likewise if 1,2 against 3,4 came out right and 1,3 against 2,4 came out left. Then the heavy one is 3 or 5; if the last weighing leans towards 5, it's heavy; otherwise 3 is.

I know what you mean, so I'll reword it for other people to read:

If 1,2 vs 3,4 leans left and 1,3 vs 2,4 leans right, either 2 or 5 is heavy, so weigh 2 vs 5. Either:

1) the first leans left and the second is balanced, in which case 2 is heavy, so this will balance revealing 2 to be correct.

2) the first is balance and the second leans right, in which case 2 is heavy, so this will lean left revealing 2 to be correct.

3) the first leans left and the second leans right, in which case 5 is heavy, so this will lean right revealing 5 to be correct.

If the first two lean right then left, use 5 vs 3 and make the obvious changes to what's above.


Well, it lasted almost 4 hours, that's better than some. You're up!

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

I propose the following game. Using my secret continuous probability distribution, I pick two random real numbers and write them on separate slips of paper. I put one paper in each of my hands and ask you to pick one. I then show you the number on that slip of paper, and you have to guess which of my hands has the paper with the larger number on it. Obviously, if you guess randomly, your chance of winning is 50%. Is it possible for you to do better than that? If so, how, and if not, why not?

Mattcrampy
Level: Smitemaster

Rank Points: 2388
Registered: 05-29-2003
IP: Logged

Throwing this out there:

A continuous probability distribution is skewed to favour certain numbers. So over time, as you learn which numbers are more likely to come up, your odds of improving your guess is likely to improve, in which case your odds will settle at around 75%.

Unless you change the distribution every time I play, in which case the best strategy is to always guess the other hand. I have no way of knowing how far out the distribution goes, or which side the revealed number is on. However, the odds suggest that there's more numbers the distribution could end on that's larger than the revealed number than ones where it's smaller.

Matt

____________________________
What do you call an elephant at the North Pole?

Oneiromancer
Level: Legendary Smitemaster

Rank Points: 2936
Registered: 03-29-2003
IP: Logged

Does this have anything to do with why the contestant should always switch their choice on Monty Hall? Because I always forget why that is.

This page has such a good explanation of that problem that I just have to throw it out there. And it also shows me that the problems aren't really alike, although I am glad that it reminded me of it so I could go look it up.

Game on,

[Edited by Oneiromancer on 01-06-2004 at 10:50 AM GMT]

____________________________
"He who is certain he knows the ending of things when he is only beginning them is either extremely wise or extremely foolish; no matter which is true, he is certainly an unhappy man, for he has put a knife in the heart of wonder." -- Tad Williams

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

Mattcrampy wrote:
Unless you change the distribution every time I play, in which case the best strategy is to always guess the other hand. I have no way of knowing how far out the distribution goes, or which side the revealed number is on. However, the odds suggest that there's more numbers the distribution could end on that's larger than the revealed number than ones where it's smaller.

Technically we're only playing once, but regardless, if we play multiple times, let's say I'm allowed to change my distribution. It doesn't really make sense to say, always switch. In that case, since you picked the first number randomly, you're effectively still guessing randomly.

Mattcrampy
Level: Smitemaster

Rank Points: 2388
Registered: 05-29-2003
IP: Logged

Well, if we're only playing once... I don't know.

Matt

____________________________
What do you call an elephant at the North Pole?

zex20913
Level: Smitemaster

Rank Points: 1723
Registered: 02-04-2003
IP: Logged

Actually, just to be annoying and pedantic, the chances of winning are *obviously* slightly less than 50%. If the numbers, which were chosen randomly, are equal, then neither number is larger.

This is a one-in-a-who knows chance, but still possible. And I don't think that it can beat 50%. The number in the other hand will be

a)higher than the one in the shown hand
b)lower than the one in the shown hand
c)equal to the number in the shown hand.

But, whichever of the three, it is already set. If the number was not yet chosen, I would always pick the other hand, because there are always higher real numbers. As it is, we may as well guess randomly.

____________________________

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

zex20913 wrote:
Actually, just to be annoying and pedantic, the chances of winning are *obviously* slightly less than 50%. If the numbers, which were chosen randomly, are equal, then neither number is larger.

This is a one-in-a-who knows chance, but still possible.

This is the reason that I specified that my distribution was continuous; for continuous distributions the chance that the two numbers will be the same is 0. But if you're bothered by this, I'll just make sure the numbers are different, to be fair.

...because there are always higher real numbers.

There are always smaller real numbers, too; I'm allowed to go negative.

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

I want to say this:

If the number you see is negative, choose the other number. If the number you see is positive, stick with it. For any positive number, there are more numbers less than it than there are numbers greater than it. Likewise, there are more numbers greater than any negative number than there are greater than any positive number.

But I don't know anything about your distribution, so that can't be it.

After too much doodling with lines with dots on them, I came up with this - pick your own random number, and imagine that it's the still-hidden number. Answer accordingly.

-------------*------------*---------
That's a line with the two actual numbers as *s. If the number I see is the one on the left, then if my random number is anywhere to the right of it, I win. If the number I see is the one on the right, then if my random number is anywhere to the left of it, I win. Therefore, if my random number is between the two real numbers, then I always win - otherwise, it's still a 50/50 toss-up.

That's certainly better than 50%, but I don't know if it's the best possible.



____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

That's what I was looking for Schik, a strategy that wins with probability more than half the time. You just have to make sure that the distribution you use to pick your random number is nonzero on the whole real line, but that's a minor point.

The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged

So then it's Schik's turn?

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

Yup.

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

Cool, I'll take it.

So, once again you're confronted with 12 balls. Eleven of them still weigh the same, and the other one is either slightly heavier or slightly lighter than the rest.

You again have a balance scale, and can only weigh balls vs. balls - nothing else.

You still get to use the scale three times. However, this time you have to decide what you will put on each side of the scale for all three weighings before weighing anything, and you must not only determine which ball is different, but also if the different ball is lighter or heavier.


____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

Number the balls 1-9, with the last three called 0, A and B

These are the weighings:

1345 vs. 2780
1489 vs. 236A
1275 vs. 369B

If the scales tip the same way thrice, it's 1.
If the scales tip the same way twice, then the other way, it's 2.
If the scales tip one way first, then the other twice, it's 3.
If the scales tip the same way twice, then balance, it's 4.
If the scales tip the same way first and last, and balance in the second, it's 5.
If the scales balance first, then tip the same way twice, it's 6.
If the scales tip differently first and last, and balance in the second, it's 7.
If the scales tip differently twice, then balance, it's 8.
If the scales balance first, then tip differently twice, it's 9.
If the scales tip only the first time, it's 0.
If the scales tip only the second time, it's A.
If the scales tip only the third time, it's B.

In any case, you can figure out the weight of the odd one out by looking at which way the scales tipped.

____________________________
Today the refrigerator, tomorrow the world!

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

I thought this might take a little longer than that. Good job - you're up!

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

All right, next puzzle!

Two players play the following game: There are four piles of matches on a table, containing 89, 53, 61 and 73 matches, respectively. The two players alternate in taking turns. A turn consists of selecting two of the four piles and removing a number of matches from each of them. It is not necessary to remove the same number of matches from both piles, but it is necessary to remove at least one match from each of the two piles. A player loses if he can't make a legal move (that is, there is only one pile or no piles left).

Does the player who goes first or the player who goes second have a winning strategy?

____________________________
Today the refrigerator, tomorrow the world!

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

The person who goes first has a winning strategy.

Suppose that at a given point, the piles have a, b, c, and d matches in them, a<=b<=c<=d. We'll call positions in which a=c (hence a=b=c) bad; otherwise, we'll call the position good. If you get a good position, you can always make it bad; c and d are greater than a, so you can make them equal to a. Moreover, if you get a bad position, any move you make has to make it good. Therefore, if a player gets a good position, then he can always make a move and ensure that he'll receive a good position on his next turn. Since the initial position is good, the first player wins.

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

bibelot wrote:
The person who goes first has a winning strategy.

Suppose that at a given point, the piles have a, b, c, and d matches in them, a<=b<=c<=d. We'll call positions in which a=c (hence a=b=c) bad; otherwise, we'll call the position good. If you get a good position, you can always make it bad; c and d are greater than a, so you can make them equal to a. Moreover, if you get a bad position, any move you make has to make it good. Therefore, if a player gets a good position, then he can always make a move and ensure that he'll receive a good position on his next turn. Since the initial position is good, the first player wins.

You're definitely on the right track, but you haven't explained why moving to a bad position wins.

____________________________
Today the refrigerator, tomorrow the world!

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

Any move from a bad position leads to a good position; you always have to take from one of the three small piles and only one other, so there will always be two piles larger than the smallest after you are done. Since you can always make a move in a good position and you can only get a good position back if you move to a bad position, you will never reach a point where you can't move, so you can't lose. Obviously someone has to lose because the total number of matches strictly decreases, so it has to be the other person.

[Edited by bibelot on 01-07-2004 at 06:03 PM GMT]

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

If you move to a bad position, you have 3 stacks with the same amount of matches, and 1 stack with more. For argument's sake, let's say the stacks are 9, 9, 9, 12. Your opponent will make some move, setting you in a good position again. As long as you always pull from the piles your opponent doesn't pull from, you will always set your opponent in a bad position. When the bad position includes three zeroes, your opponent has no moves to make, and you win.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!