mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2003-07-14, 19:41   #1
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default Pick and Choose

Here's another strategy game for you to analyze.

Two players make a single line of twelve tokens. They could be dominoes, coins, or whatever. They are placed so that each token (except the two end tokens) touches each of its two neighbors, and no other. Now, one of the end tokens is moved away a bit so that there are two lines. The first contains one token and the second contains all the rest.

The players take turns removing the tokens. In each turn, a player must take either one token or two. However, if he takes two, they must be touching neighbors. No tokens are ever moved except when they are removed.

For clarification, if the tokens are taken from the end of a line, the line gets shorter (or disappears). If they are taken from any interior place in the line, that line is divided into two lines by the gap left by the tokens removed.

The objective is to remove the last token.

Is there a winning strategy for either player?

If so, what is the strategy?
Wacky is offline   Reply With Quote
Old 2003-07-14, 21:06   #2
alienz
 
Jun 2003

3×7 Posts
Default

http://world.std.com/~reinhold/math/nim.html

The answer is here,
alienz is offline   Reply With Quote
Old 2003-07-14, 21:24   #3
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

21018 Posts
Default

Sorry, Nim is a different game. Please reread the rules.
Wacky is offline   Reply With Quote
Old 2003-07-14, 23:15   #4
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

I have been approaching this problem in a less than graceful manner, namely, working backwards from winning positions (i.e. *, **) representing the possible positions at n as partitions of n.

So far (assuming I haven't made an error .. that would suck), I have gotten up through 9 pieces, and the positions where the next player will lose with optimal playing on both sides is 8+1, 6+3, 6+2+1, 5+3+1, 4+1+1+1+1+1, and 3+3+3

for eight pieces left, the losing positions are 4+4, 4+2+2, 3+2+1+1+1, 2+2+2+2, 2+2+1+1+1+1, and 1+1+1+1+1+1+1+1

This was much more manageable at 5 pieces :) I suppose I could keep on going until I exhaust the possibilities at 10 and 11 pieces left, but I still don't have a really graceful definition of the optimal strategy.
Orgasmic Troll is offline   Reply With Quote
Old 2003-07-15, 00:16   #5
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default

Travis,

Ive been trying to do the same, with not much more luck. :?

Something that might help you is to eliminate "good" positions that the previous player wouldn't give to you.
ie. The final winning position of **. The possible positions before that are (I think):
[code:1] ***, ****, ** *, and ** ** which a good player would make

**, ** *, * *, and ** * respectively. [/code:1]Notice that only the first one, ***, leads to your result, and based on its previous positions, it can be avoided by a good player. (again, I think)
So it should be pruned from your search.

The only winning stratagy I can think of is:
1. Reduce the game to an even number of lines of one or two tokens each.
2. Always leave an even number of lines of one or two tokens each.

The trick is how to complete step 1 while preventing your opponent from doing so. ;)
Maybeso is offline   Reply With Quote
Old 2003-07-16, 20:02   #6
c00ler
 
Jul 2003

1916 Posts
Default

The first one wins!

hints:
1)first move - make 1+3+7
2)one, who makes a+a+b+b+a+a (symmetrical position), loses


P.S. If objective is not to remove the last token then the first wins too.
And first winning moves are 1+3+7 and 1+5+5
P.P.S. It's much harder to analyse the game with modified rules; it's solution is much longer.
c00ler is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help to choose components for a Ryzen rig robert44444uk Hardware 50 2018-04-07 20:41
If you choose an answer at random Uncwilly Lounge 12 2018-02-14 15:00
Which settings to choose for best work? jmb1982 Software 2 2009-04-07 09:33
Choose your own exponent? Unregistered PrimeNet 3 2003-12-10 04:32
Pick a stone, or two, .... or three Wacky Puzzles 5 2003-06-24 16:11

All times are UTC. The time now is 05:40.

Mon May 10 05:40:14 UTC 2021 up 32 days, 21 mins, 0 users, load averages: 3.39, 3.36, 3.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.