Winning strategy of a game

622 Views Asked by At

The following is a game on monomials.

Let $M(X,Y)$ denote the set of all monomials in $X$ and $Y$, i.e.,
$$ M(X,Y)=\{X^aY^b\mid(a,b)\in\mathbb{N}^2\}, $$ where $\mathbb{N}=\{0,1,\dots\}$.

Alice and Bob take turns to write down monomials from $M(X,Y)$ with the following rules:

(i) Alice moves first.

(ii) $1$ is not allowed to be written down.

(iii) The monomial that a player is about to write down can NOT divide any monomial written down before or be divisible by any monomial written down before.

(iv) They are not allowed to 'pass'.

(v) The player makes the last move wins.

Now the question is:

If, by the end of each game, the loser pays \$$1$ to the winner for each monomial written down (by either Alice or Bob), then does Alice have a winning strategy to maximize the income in each game? What is the guaranteed maximum income of Alice in each game?

I have noticed the following:

(i) Let $S\subset M(X,Y)$ and $S_{\min}$ be the set of minimal elements of $(S,\mid)$ (which is a poset). So if $S$ is the set of all the monomials written down in one game, then $S=S_{\min}$.

(ii) Alice in fact has a winning strategy: just write $XY$ down first then she will in $3$ moves in total.

Then I got stuck. I guess the guaranteed maximum income in each game depends on the first monomial $X^pY^q$ written down by Alice because if she plays $XY$ then the income is definitely \$$3$. So I guess if it has something to do with $p,q$.

Could anybody help me with this question? Or some clue?

UPDATE

I think it might be too difficult to find out a winning strategy for Alice to maximize the money she can receive after each game. So here is another similar (but probably completely different) question:

Suppose Alice is so clever that she has a winning strategy to maximize the money she receives after each game, when possible. What is the maximum amount of money that she is guaranteed to receive after each game?

1

There are 1 best solutions below

3
On

Alice wins with any starting move of the form $X^pY^p$ by symmetry. If Bob plays $X^aY^b$ Alice can respond with $X^bY^a$. Alice loses with a starting move of $X^pY^{p+1}$ because Bob responds $X^{p+1}Y^p$ and wins by symmetry. I haven't solved more disparate opening moves.

After Alice opens with $X^pY^p$, every subsequent move must be of the form $X^aY^b$ where either $a \lt p \lt b$ or $b \lt p \lt a$ There will be at most $2p+1$ total moves in the game because you use up the options below $p$.

Alice can win as much as she wants. Her opening move is $X^pY^p$ with $p=2^r-1$. I believe she wins at least $2r+1$. As shown above, she could win as much as $2p+1$, but Bob can eliminate a lot of moves by moving to $X^{p+1}$. Now no move with $Y^k, k \le p$ is available. Alice can now move to $X^{(p-1)/2}Y^{2p}$. There is symmetry between the intervals in available $X$ exponents $[0,(p-3)/2]$ and $[(p+1)/2,p-1]$, so Alice can play symmetrically to Bob and still guarantee a win. Bob can eliminate one of the intervals, for example by playing $Y^{2p+1}$, but Alice can play the midpoint of the other interval and recreate the symmetry. This is certainly not rigorous, but I believe it is plausible.