3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I have a question about the last paragraph. After B plays $X^{p+1}$, why is he threatening to win by $Y^{p+1}$? A could play $X^{p-2}Y^{p+2}$ if the value of $p$ allows and A could probably win I guess? For example, if $p=3$, then A could play, in the second move of hers, $XY^5$ and win the game in $5$ steps. $\endgroup$
    – Teddy Frei
    Mar 13, 2016 at 11:03
  • $\begingroup$ @TeddyFrei: You are right. I need to work on it $\endgroup$ Mar 13, 2016 at 15:29
  • $\begingroup$ @TeddyFrei: Please see the update. $\endgroup$ Mar 14, 2016 at 15:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .