Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G_1,\dotsc,G_r$ combinatorial impartial games. The selective compound $G=G_1 \vee \dotsc \vee G_r$ is the following game: The positions are the tuples of positions of the $G_i$, and a move is a move in any positive number of $G_i$s. My former question asked for the $\mathcal{P}$-positions of $G$ in terms of the ones for $G_i$. However, there we used implicitly the normal play rule (the one with the last move wins).

Question. What are the $\mathcal{P}$- and $\mathcal{N}$-positions for $G$ under the misère play rule?

Here is a very basic example which already shows that something strange may happen: Let $G_1$ be the subtraction game with one pile and substraction set $\{1\}$. Thus, positions of $G_1$ are natural numbers and the only moves are $n \mapsto n-1$ if $n>0$. The $\mathcal{P}$-positions of $G_1$ under the misère play rule are the odd natural numbers. One verifies that the $\mathcal{P}$-positions in $G_1 \vee \dotsc \vee G_1$ are a) the ones of the form $(0,\dotsc,0,n,0,\dotsc,0)$ for some odd natural number $n$, b) $(n_1,\dotsc,n_s)$, where at least two $n_i$ are positive, and all $n_i$ are even.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

Your very basic example points the way to the solution. In the general case, the misère $\mathcal P$-positions are a) the ones where all games but one are over and the one is in a misère $\mathcal P$-position and b) the ones where at least two games aren't over and all games that aren't over are in a normal $\mathcal P$-position.

Case a) is obvious. In case b), a move brings all selected games into a normal $\mathcal N$-position. For the winning response, in each game selected by the opponent we have one or both of the options of ending it or taking it back to a normal $\mathcal P$-position. If at least two of the selected games have the option of taking them back to a normal $\mathcal P$-position, that response gets us back to case b). Otherwise, we can end all but one of the games and leave the remaining game in a misère $\mathcal P$-position by playing in it if necessary, thus arriving at case a).


To give a concrete example, consider the subtraction game with a move consisting of a subtraction of any number from $1$ to $k$. In normal play the $\mathcal P$-positions are the heap sizes with residue $0\bmod k+1$, and in misère play the $\mathcal P$-positions are the heap sizes with residue $1\bmod k+1$. These sets are complements of each other only for $k=1$ (your example).

In this case the misère $\mathcal P$-positions of the selective compound are a) the ones where all games but one are over and the one has residue $1\bmod k+1$ and b) the ones where at least two games aren't over and all games that aren't over have residue $0\bmod k+1$.

For the winning response in case b), we can take the games selected in the opponent's move back to residue $0\bmod k+1$. In case at least two games are not ended by this response, we're back to case b). Otherwise we can end all but one of the games, and if necessary move in the remaining game to take it to residue $1\bmod k+1$.

share|improve this answer
    
Thanks for your answer! What is a normal $\mathcal{P}$-position? I suppose this is a $\mathcal{P}$-position of the game when played with the normal play rule. But how can I determine them when I only know the misere positions? –  Martin Brandenburg Apr 26 '12 at 20:25
    
@Martin: Sorry, yes, "misère/normal $\mathcal N/\mathcal P$-position" is short for "a position which under misère/normal play condition is an $\mathcal N/\mathcal P$-position. I'm not aware of a general way of deriving misère $\mathcal N/\mathcal P$-positions from normal $\mathcal N/\mathcal P$-positions or vice versa. (By the way, greetings from Berlin to Münster ;-) The fact that the Sprague-Grundy theorem holds for normal but not for misère play would seem to indicate that the two are fundamentally different and no general transformation is possible. –  joriki Apr 26 '12 at 20:27
    
Thanks. But I don't understand "with one or both of the options in each such game of ending it or taking it back to a normal P-position". Which options? And you only prove that a),b) are misère $\mathcal{P}$-positions, right? One also has to prove that the other ones are misère $\mathcal{N}$ [but I should be able to do this as an exercise ...] Grüße nach Berlin! –  Martin Brandenburg Apr 26 '12 at 20:45
    
@Martin: A normal $\mathcal N$-position is a position in which we have a winning move in normal play. This is either because we can win the game by ending it, or because we have a move that takes the game to a normal $\mathcal P$-position. (If you consider an ended game to be in a normal $\mathcal P$-position, read "non-final normal $\mathcal P$ position" for "normal $\mathcal P$-position" everywhere.) You're right about proving that the remaining positions are $\mathcal N$-positions, but these are precisely of the form for which the proof describes a winning move. –  joriki Apr 26 '12 at 20:53
    
I'm aware of the definition of normal $\mathcal{N}$-positions. Sorry, I don't understand your proof. Somehow it should be somehow some "image" of my example, but I cannot see it. –  Martin Brandenburg Apr 26 '12 at 21:02
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.