wu :: forums
« wu :: forums - Odd victory condition »

Welcome, Guest. Please Login or Register.
Sep 24th, 2018, 5:59pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: towr, Grimbal, ThudnBlunder, Icarus, william wu, Eigenray, SMQ)
   Odd victory condition
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Odd victory condition  (Read 273 times)
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Odd victory condition  
« on: Feb 23rd, 2018, 10:04am »
Quote Quote Modify Modify

(shamelessly appropriated from BBC Radio 4's daily puzzle a bit over a week ago):
 
Two people are playing a take-away game with a twist:
 
On each player's turn, they take 1, 2 or 3 tokens from the pile, and play continues until all tokens are taken. So far, so standard, but the winner is determined not by who takes the last turn, but by how many tokens each ends up with. The player with an odd number of tokens wins.
 
The game starts with 23 tokens in the pile (and none in either player's possession). Assuming perfect play, who wins, and what's their strategy?
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7408
Re: Odd victory condition  
« Reply #1 on: Feb 23rd, 2018, 1:07pm »
Quote Quote Modify Modify

Interesting!
 
It looks like a symmetrical poset game, but it is more tricky than that.
 
If you consider A and B to have symmetrical roles where each wants an odd sum, then their goals are not necessarily opposed in the analysis, i.e. if you start with an even number, they both can win.
 
If you consider that A tries to get an odd sum and B tries to prevent that to happen, then their goals are opposed but their roles are not symmetrical.  B does not change the parity of A's sum.
 
So even though the game is actually symmetrical, you cannot evaluate positions in terms of "from this position the next player wins".  Or not easily.
« Last Edit: Feb 23rd, 2018, 1:15pm by Grimbal » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Odd victory condition  
« Reply #2 on: Feb 24th, 2018, 4:21am »
Quote Quote Modify Modify

hidden:

I think you can just split the odd and even cases to build the win/lose table
 
If A has an odd number of tokens, and there are N tokens remaining, then B must have an odd number of tokens iff N is odd. (Given we started with 23.)
Similarly if A has an even number of tokens, B must have an even number iff N is odd
So look in the appropriate column to see if there's a move where (s)he's in the losing position.
 
 
    even   odd
 0  Lose   Win
 1  Win    Lose
 2  Win    Win
 3  Win    Win
 4  Win    Lose
 5  Lose   Win
 6  Win    Win
 7  Win    Win
 8  Lose   Win
 9  Win    Lose
10  Win    Win
11  Win    Win
12  Win    Lose
13  Lose   Win
14  Win    Win
15  Win    Win
16  Lose   Win
17  Win    Lose
18  Win    Win
19  Win    Win
20  Win    Lose
21  Lose   Win
22  Win    Win
23  Win    Win
« Last Edit: Feb 24th, 2018, 4:24am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Odd victory condition  
« Reply #3 on: Feb 24th, 2018, 7:46am »
Quote Quote Modify Modify

on Feb 23rd, 2018, 1:07pm, Grimbal wrote:
if you start with an even number, they both can win.

 
There are a couple of options for dealing with this. One is to say that you can, indeed, play for a collaborative victory (which is a much less interesting game to analyse since the only plays that matter are the ones that could leave just 1 coin remaining). Another is to say that you can only start with an odd number in the pile. A third is to say that you can start with any number in the pile, but, if it's even, one player starts with an extra token (or, equivalently, one player wins on even; the other on odd).
 
Follow up question: What if, rather than 1-3, you take 1-n coins (where n is fixed for an entire game). How does that change things?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Odd victory condition  
« Reply #4 on: Feb 24th, 2018, 12:23pm »
Quote Quote Modify Modify

on Feb 24th, 2018, 7:46am, rmsgrey wrote:
Follow up question: What if, rather than 1-3, you take 1-n coins (where n is fixed for an entire game). How does that change things?
I don't think that qualitatively changes the solution, though the outcome may be different.
You'll just have to look at more rows in the table to see if there's a winning move. And if you change the goal to 1 mod 3, or 1 mod M, you just add more columns, but it also doesn't really change anything, I think.
Multiple players would make things more complicated.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board