Toothpicks....
Erwin Quejado
Can someone figure this one out?
Ok..there are 2 players.
There are 32 toothpicks.
Player one starts the game.
He can draw either 1, 2, 3, or 4 toothpicks.
The same goes for Player two.
This goes on and on till the end.
The winner is the one to pick up the last toothpick.
Can you help me out on this one?
thanks
Michael Jason Lewis
This is a version of a game called Nim. In this rule-set, player 1 can
always win. If you are player 1, take 2 toothpicks on your first turn, and
then take (5-n) toothpicks each turn, where n is the number of toothpicks
your opponent took.
- Mike
John Boehm
>Hi..
>Can someone figure this one out?
>Ok..there are 2 players.
>There are 32 toothpicks.
>Player one starts the game.
>He can draw either 1, 2, 3, or 4 toothpicks.
>The same goes for Player two.
>This goes on and on till the end.
>The winner is the one to pick up the last toothpick.
>Can you help me out on this one?
>thanks
Sure. If player 1 chooses 2 toothpicks (leaving 30), they insure a
victory. No matter what player 2 does, player one draws as many
toothpicks as necessary to leave an even multiple of 5 toothpicks left
(25,20,15,10,5). With only 5 toothpicks left for player 2, no matter how
many they pick player 1 will get the last one.
If player 1 is STUPID enough not to take 2 toothpicks, player 2 can use
the same strategy (multiples of 5) to guarantee their own victory.
John
Pete Mitchell
>Can someone figure this one out?
>Ok..there are 2 players.
>There are 32 toothpicks.
>Player one starts the game.
>He can draw either 1, 2, 3, or 4 toothpicks.
>The same goes for Player two.
>This goes on and on till the end.
>The winner is the one to pick up the last toothpick.
>Can you help me out on this one?
>thanks
>
Sure. You want to *always* leave your opponent with a multiple of 5.
Thus, if you go first (in which case you cannot lose if you proceed
correctly), you take 2, leaving him at 30. No matter how many he
takes, you can then put him at 25; then 20, etc. It should be
pretty obvious when you put him at 5 that he cannot beat you.
- Pete
--
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
: "There but for the grace of God, go I."
Pete Mitchell :
p...@mv.mv.com : No, wait...
: Shit, that IS me! :-)
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Jonathan Haas
>Hi..
>Can someone figure this one out?
>Ok..there are 2 players.
>There are 32 toothpicks.
>Player one starts the game.
>He can draw either 1, 2, 3, or 4 toothpicks.
>The same goes for Player two.
>This goes on and on till the end.
>The winner is the one to pick up the last toothpick.
>Can you help me out on this one?
Sure. A very simple variant of the Nim family. Player one wins by
taking two toothpicks on his first move, leaving 30. From then
on, he takes however many toothpicks are necessary to leave the
remainder an even multiple of 5, which he can always do. He'll
be able to get the last toothpick.
ObEasyPuzzle: Who wins the variant of the above game where the goal
is *not* to take the last toothpick?
--
__/\__ Jonathan S. Haas | Jake liked his women the way he liked
\ / posi...@devel.trimarkint.com | his kiwi fruit: sweet yet tart, firm-
/_ _\ Trimark Interactive, Inc. | fleshed yet yielding to the touch, and
\/ Don't Tread On Me | covered with short brown fuzzy hair.
Wei-Hwa Huang
>ep...@crl.com (Erwin Quejado) writes:
>>Ok..there are 2 players.
>>There are 32 toothpicks.
>>Player one starts the game.
>>He can draw either 1, 2, 3, or 4 toothpicks.
>>The same goes for Player two.
>>This goes on and on till the end.
>>The winner is the one to pick up the last toothpick.
>If player 1 is STUPID enough not to take 2 toothpicks, player 2 can use
>the same strategy (multiples of 5) to guarantee their own victory.
New puzzle: If both players are stupid and make their moves randomly,
who is more likely to win?
--
-- Wei-Hwa Huang (whu...@cco.caltech.edu)
Homepage (under construction): http://www.ugcs.caltech.edu/~whuang/
You can tuna fish, but you can't carp a tunnel syndrome.
Seth Breidbart
>In article <45geol$b...@gap.cco.caltech.edu>, whu...@cco.caltech.edu (Wei-Hwa
>Huang) writes:
>>>ep...@crl.com (Erwin Quejado) writes:
>>>>Ok..there are 2 players.
>>>>There are 32 toothpicks.
>> who is more likely to win?
>
>number of moves required to clear the board is 12.8. Thus, this is likely to
>be a first player win, I think. I'm not certain how the intervals increasing
>far away from 12.8 will add up, but I would expect that they will be
>comparatively small.
They'll be relatively huge. Let's look at just the first move:
1: 31 remaining, 12.4 expected moves
2: 30 remaining, 12.0 expected moves
3: 29 remaining, 11.6 expected moves
4: 28 remaining, 11.2 expected moves
5: 27 remaining, 10.8 expected moves
Now, who is the expected winner in each of those cases?
Seth
Unverified User
>jo...@pacifier.com (John Boehm) writes:
>>ep...@crl.com (Erwin Quejado) writes:
>>>Ok..there are 2 players.
>>>There are 32 toothpicks.
>>>This goes on and on till the end.
>
>New puzzle: If both players are stupid and make their moves randomly,
>who is more likely to win?
The question is (very slightly) ill-defined, based on the vagueness of
"randomly." Assuming that this means flat random, the problem can be
solved as follows:
Let p(n)=Prob(player 1 wins the game which starts with n toothpicks)
Then p satisfies the recursion:
p(n+4)=1-.25*(p(n)+p(n+1)+p(n+2)+p(n+3)).
We can take the base case to be p(-3)=p(-2)=p(-1)=p(0)=0, and just
do the calculations. I used a spreadsheet to find p(32)=0.50008035.
Obpuzzle: Prove p(n) converges to .5 as n increases without bound.
jason howald
Admiral Jota
>Erwin Quejado <ep...@crl.com> wrote:
>>Ok..there are 2 players.
>>There are 32 toothpicks.
>>[One] can draw either 1, 2, 3, or 4 toothpicks.
>>This goes on and on till the end.
>>The winner is the one to pick up the last toothpick.
>Sure. A very simple variant of the Nim family. Player one wins by
>taking two toothpicks on his first move, leaving 30. From then
>on, he takes however many toothpicks are necessary to leave the
>remainder an even multiple of 5, which he can always do. He'll
>be able to get the last toothpick.
>ObEasyPuzzle: Who wins the variant of the above game where the goal
>is *not* to take the last toothpick?
Good old player one, again -- if he knows what he's doing. If player one
takes 1 toothpick on his first turn, and then always leaves one more than
a multiple of five (31, 26, 21, etc.) on the table, he'll end up leaving
just one toothpick for his doomed opponent to deal with.
--
/<-= -=-=- -= Admiral Jota =- -=-=- =->\
__/><-=- http://www.tiac.net/users/jota/ =-><\__
\><-= jo...@mv.mv.com -- Finger for PGP =-></
\<-=- -= -=- -= -==- =- -=- =- -=->/
Geoff Bailey
In article <45geol$b...@gap.cco.caltech.edu>,
Wei-Hwa Huang <whu...@cco.caltech.edu> wrote:
>jo...@pacifier.com (John Boehm) writes:
>>ep...@crl.com (Erwin Quejado) writes:
>>>There are 32 toothpicks.
>>>He can draw either 1, 2, 3, or 4 toothpicks.
>>>The same goes for Player two.
>>>The winner is the one to pick up the last toothpick.
>
>>the same strategy (multiples of 5) to guarantee their own victory.
>
>who is more likely to win?
Let P(n) be the probability of the player whose move it is to win with n
toothpicks remaining. Then:
P(1) = 1
P(2) = 1/2
P(3) = 1/2
P(4) = 1/2
And in fact, if you were always allowed to choose any number of toothpicks,
then this pattern would continue. i.e P(n) = 1/2 for n > 1. But we can
choose at most 4 toothpicks, so the recurrence is:
P(n+4) = ( (1-P(n+3)) + (1-P(n+2)) + (1-P(n+1)) + (1-P(n))) / 4
The next few values are:
P(5) = 3/8
P(6) = 17/32
P(7) = 67/128
P(8) = 265/512
It gets pretty close to 1/2, mostly over it, but occasionally under
(P(10) and P(15) are < 1/2, P(20) and P(25) are > 1/2, and P(30) < 1/2 again).
P(32) = 288230655211303867 / 576460752303423488
~= 0.50000048409122565
So the first player is more likely to win.
Cheers,
Geoff.
-------------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm) | Programmer by trade --
ft...@cs.su.oz.au | Gameplayer by vocation.
-------------------------------------------------------------------------------
Seth Breidbart
Geoff Bailey <ft...@cs.su.oz.au> wrote:
>In article <45geol$b...@gap.cco.caltech.edu>,
>Wei-Hwa Huang <whu...@cco.caltech.edu> wrote:
>>New puzzle: If both players are stupid and make their moves randomly,
>>who is more likely to win?
>
>Let P(n) be the probability of the player whose move it is to win with n
>toothpicks remaining. Then:
>
>P(1) = 1
>P(2) = 1/2
>P(3) = 1/2
>P(4) = 1/2
Interesting. Two people have posted "correct" answers, which differ,
based on the value of "randomly" in the problem statement.
1. Pick a number u[1,4] and take that many (or as many as can be taken
if fewer).
2. Pick a number u[1,minimum(4,#left)]
Seth
James Edward Russell
>Hi..
>Can someone figure this one out?
>Ok..there are 2 players.
>There are 32 toothpicks.
>Player one starts the game.
>He can draw either 1, 2, 3, or 4 toothpicks.
>The same goes for Player two.
>This goes on and on till the end.
>The winner is the one to pick up the last toothpick.
>Can you help me out on this one?
>thanks
If you are player two, the number of toothpick you pick up is a function
of how many the other play picks up. If he picks up 4, you pick up 1, if
he picks up 1, you pick up 4. Using this, you can make sure that
the number of toothpicks is reduced by 5 every two turns. When it gets to
25 picked up (7 left), If he picks up 1, you pick up one (5 left). He
then has to pick up 1-4, leaving 1-4 toothpicks for you.
If he picks up 2 you are in trouble, so you take a different tack.
If he picks up 3 or 4, there will be 3-4 left on the table so you win.
So concentrate on the '2' part and you'll have a sure fire way of winning.
I just can't remember what it is.
Jimmy
Stitch
..Hi..
..Can someone figure this one out?
..Ok..there are 2 players.
..There are 32 toothpicks.
..Player one starts the game.
..He can draw either 1, 2, 3, or 4 toothpicks.
..The same goes for Player two.
..This goes on and on till the end.
..The winner is the one to pick up the last toothpick.
..Can you help me out on this one?
>thanks
Now let's change the rules just a little. On your turn you can take 1, 2
or 4 toothpicks (but _not_ 3) Now who wins and how?
Stitch
Ross Millikan
Stitch <SWI...@nauvax.ucc.nau.edu> writes:
The general approach for problems like this is shown in Winning Ways
by Conway and Berlekamp (sp?). Define an N position as one in which
the next player wins, and a P position as one in which the previous
player wins. So 1, 2, and 4 are N, and obviously 3 is P. The general
rule is that a position is N unless all positions you can reach are N.
For these rules, the ability to take 4 doesn't matter and the P
positions are 3n. So take 2 and win.
Ross Millikan
Rajesh Shingavi
CASE 1
: ..He can draw either 1, 2, 3, or 4 toothpicks.
: ..The winner is the one to pick up the last toothpick.
CASE 2
: Now let's change the rules just a little. On your turn you can take 1, 2
: or 4 toothpicks (but _not_ 3) Now who wins and how?
spoiler.....
^L
CASE 1.
in case of 1,2,3 or 4 you should go on reducing 32 be 5.
thus one who reaches 2 or 7 first can win.
CASE 2.
here one should go on reducing 3 or 6 from 32.
thus one who reaches 2 first can win the game.
``````````````````````````````````````````````````````````````````
` Believe nothing, merely because you have been told it, `
` or because it is traditional, `
` or because you have imagined it. `
` Gautama Buddha `
``````````````````````````````````````````````````````````````````
Jonathan Haas
>..This goes on and on till the end.
>Now let's change the rules just a little. On your turn you can take 1, 2
>or 4 toothpicks (but _not_ 3) Now who wins and how?
It depends on the legal moves when there are only 3 remaining. Can
the player facing three toothpicks take them all, and win? If
not, the game is a first player win. He takes two toothpicks
on the first move, leaving 30, and from then on, endeavors to
keep the number of matches a multiple of 3, by taking 2 when
his opponent takes 1 or 4, and by taking 1 or 4 when his
opponent takes 2.
If a player can take all three remaining matches and win, the
strategy is to keep the number of toothpicks one *less* than
a multiple of three. Since 32 is one less than a multiple
of three, the game is a second player win... he follows
the strategy of taking 2 when his opponent takes 1 or 4,
and taking 1 or 4 when his opponent takes 2, until the
count of matches reaches 5 or 8, and it's his opponent's
turn. If his opponent is facing 5 matches, the second
player will obviously win no matter what. If there are 8
remaining and his opponent takes 4, he takes 4 to win. If
there are 8 remaining and his opponent takes 1 or 2, he
takes 2 or 1, leaving 5 and a victory.
--
__/\__ Jonathan S. Haas | Jake liked his women the way he liked
\ / posi...@primenet.com | his kiwi fruit: sweet yet tart, firm-