Mixing
Each Player Removes a Number and All Its Divisors
$begingroup$
Initially, the numbers $2,3,ldots,n$ are written on a board. Alice and Bob alternately do the following: erase one number and all its divisors remaining on the board. The player who erases the last number wins. Who has a winning strategy?
Note that this problem is different from a classical easy problem as $1$ is not initially on the board.
I don't know if this problem has a nice solution. I have checked all $nle25$ and found that Bob has a winning strategy only when $n=3$ or $n=7$. The following table lists all possible first steps in Alice's winning strategy when $nle20$. I have not found any patterns.
n=2: 2
n=4: 2
n=5: 4
n=6: 5 6
n=8: 2 5 7
n=9: 2 5 7
n=10: 4 6
n=11: 8 10
n=12: 2 5
n=13: 6
n=14: 10 11 12 13 14
n=15: 12
n=16: 14
n=17: 10
n=18: 5
n=19: 12 14
n=20: 4 5 6 9
“Graph theory” is included in the tags because this game can be reformulated on a graph where there is an edge from each number to all its divisors, and the players alternately remove a vertex together with all its neighbors.
elementary-number-theory graph-theory algorithms divisibility combinatorial-game-theory
edited Jan 14 at 6:02
Alex Ravsky
41.3k32282
asked Jan 13 at 1:05
Johnson ChenJohnson Chen
192
$endgroup$
add a comment |
$begingroup$
Initially, the numbers $2,3,ldots,n$ are written on a board. Alice and Bob alternately do the following: erase one number and all its divisors remaining on the board. The player who erases the last number wins. Who has a winning strategy?
Note that this problem is different from a classical easy problem as $1$ is not initially on the board.
I don't know if this problem has a nice solution. I have checked all $nle25$ and found that Bob has a winning strategy only when $n=3$ or $n=7$. The following table lists all possible first steps in Alice's winning strategy when $nle20$. I have not found any patterns.
n=2: 2
n=4: 2
n=5: 4
n=6: 5 6
n=8: 2 5 7
n=9: 2 5 7
n=10: 4 6
n=11: 8 10
n=12: 2 5
n=13: 6
n=14: 10 11 12 13 14
n=15: 12
n=16: 14
n=17: 10
n=18: 5
n=19: 12 14
n=20: 4 5 6 9
“Graph theory” is included in the tags because this game can be reformulated on a graph where there is an edge from each number to all its divisors, and the players alternately remove a vertex together with all its neighbors.
elementary-number-theory graph-theory algorithms divisibility combinatorial-game-theory
edited Jan 14 at 6:02
Alex Ravsky
41.3k32282
asked Jan 13 at 1:05
Johnson ChenJohnson Chen
192
$endgroup$
$begingroup$
@Henry The divisors are removed, not the multiples.
$endgroup$
– saulspatz
Jan 13 at 1:17
1
$begingroup$
It would have to be a digraph. If you remove $6$ you also remove $3$, but if you remove $3$, you don't remove $6.$
$endgroup$
– saulspatz
Jan 13 at 1:18
$begingroup$
Ok - my mistake - reading too fast
$endgroup$
– Henry
Jan 13 at 1:24
1
$begingroup$
It's a special instance of the poset game, but not one that I've found any references to.
$endgroup$
– Misha Lavrov
Jan 13 at 1:58
add a comment |
$begingroup$
Initially, the numbers $2,3,ldots,n$ are written on a board. Alice and Bob alternately do the following: erase one number and all its divisors remaining on the board. The player who erases the last number wins. Who has a winning strategy?
Note that this problem is different from a classical easy problem as $1$ is not initially on the board.
I don't know if this problem has a nice solution. I have checked all $nle25$ and found that Bob has a winning strategy only when $n=3$ or $n=7$. The following table lists all possible first steps in Alice's winning strategy when $nle20$. I have not found any patterns.
n=2: 2
n=4: 2
n=5: 4
n=6: 5 6
n=8: 2 5 7
n=9: 2 5 7
n=10: 4 6
n=11: 8 10
n=12: 2 5
n=13: 6
n=14: 10 11 12 13 14
n=15: 12
n=16: 14
n=17: 10
n=18: 5
n=19: 12 14
n=20: 4 5 6 9
“Graph theory” is included in the tags because this game can be reformulated on a graph where there is an edge from each number to all its divisors, and the players alternately remove a vertex together with all its neighbors.
elementary-number-theory graph-theory algorithms divisibility combinatorial-game-theory
edited Jan 14 at 6:02
Alex Ravsky
41.3k32282
asked Jan 13 at 1:05
Johnson ChenJohnson Chen
192
$endgroup$
Initially, the numbers $2,3,ldots,n$ are written on a board. Alice and Bob alternately do the following: erase one number and all its divisors remaining on the board. The player who erases the last number wins. Who has a winning strategy?
Note that this problem is different from a classical easy problem as $1$ is not initially on the board.
I don't know if this problem has a nice solution. I have checked all $nle25$ and found that Bob has a winning strategy only when $n=3$ or $n=7$. The following table lists all possible first steps in Alice's winning strategy when $nle20$. I have not found any patterns.
n=2: 2
n=4: 2
n=5: 4
n=6: 5 6
n=8: 2 5 7
n=9: 2 5 7
n=10: 4 6
n=11: 8 10
n=12: 2 5
n=13: 6
n=14: 10 11 12 13 14
n=15: 12
n=16: 14
n=17: 10
n=18: 5
n=19: 12 14
n=20: 4 5 6 9
“Graph theory” is included in the tags because this game can be reformulated on a graph where there is an edge from each number to all its divisors, and the players alternately remove a vertex together with all its neighbors.
elementary-number-theory graph-theory algorithms divisibility combinatorial-game-theory
elementary-number-theory graph-theory algorithms divisibility combinatorial-game-theory
edited Jan 14 at 6:02
Alex Ravsky
41.3k32282
asked Jan 13 at 1:05
Johnson ChenJohnson Chen
192
edited Jan 14 at 6:02
Alex Ravsky
41.3k32282
asked Jan 13 at 1:05
Johnson ChenJohnson Chen
192
edited Jan 14 at 6:02
Alex Ravsky
41.3k32282
edited Jan 14 at 6:02
Alex Ravsky
41.3k32282
edited Jan 14 at 6:02
Alex Ravsky
41.3k32282
41.3k32282
asked Jan 13 at 1:05
Johnson ChenJohnson Chen
192
asked Jan 13 at 1:05
Johnson ChenJohnson Chen
192
asked Jan 13 at 1:05
Johnson ChenJohnson Chen
192
192
$begingroup$
@Henry The divisors are removed, not the multiples.
$endgroup$
– saulspatz
Jan 13 at 1:17
1
$begingroup$
It would have to be a digraph. If you remove $6$ you also remove $3$, but if you remove $3$, you don't remove $6.$
$endgroup$
– saulspatz
Jan 13 at 1:18
$begingroup$
Ok - my mistake - reading too fast
$endgroup$
– Henry
Jan 13 at 1:24
1
$begingroup$
It's a special instance of the poset game, but not one that I've found any references to.
$endgroup$
– Misha Lavrov
Jan 13 at 1:58
add a comment |
$begingroup$
@Henry The divisors are removed, not the multiples.
$endgroup$
– saulspatz
Jan 13 at 1:17
1
$begingroup$
It would have to be a digraph. If you remove $6$ you also remove $3$, but if you remove $3$, you don't remove $6.$
$endgroup$
– saulspatz
Jan 13 at 1:18
$begingroup$
Ok - my mistake - reading too fast
$endgroup$
– Henry
Jan 13 at 1:24
1
$begingroup$
It's a special instance of the poset game, but not one that I've found any references to.
$endgroup$
– Misha Lavrov
Jan 13 at 1:58
$begingroup$
@Henry The divisors are removed, not the multiples.
$endgroup$
– saulspatz
Jan 13 at 1:17
$begingroup$
@Henry The divisors are removed, not the multiples.
$endgroup$
– saulspatz
Jan 13 at 1:17
1
1
$begingroup$
It would have to be a digraph. If you remove $6$ you also remove $3$, but if you remove $3$, you don't remove $6.$
$endgroup$
– saulspatz
Jan 13 at 1:18
$begingroup$
It would have to be a digraph. If you remove $6$ you also remove $3$, but if you remove $3$, you don't remove $6.$
$endgroup$
– saulspatz
Jan 13 at 1:18
$begingroup$
Ok - my mistake - reading too fast
$endgroup$
– Henry
Jan 13 at 1:24
$begingroup$
Ok - my mistake - reading too fast
$endgroup$
– Henry
Jan 13 at 1:24
1
1
$begingroup$
It's a special instance of the poset game, but not one that I've found any references to.
$endgroup$
– Misha Lavrov
Jan 13 at 1:58
$begingroup$
It's a special instance of the poset game, but not one that I've found any references to.
$endgroup$
– Misha Lavrov
Jan 13 at 1:58
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3071595%2feach-player-removes-a-number-and-all-its-divisors%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3071595%2feach-player-removes-a-number-and-all-its-divisors%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
@Henry The divisors are removed, not the multiples.
$endgroup$
– saulspatz
Jan 13 at 1:17
1
$begingroup$
It would have to be a digraph. If you remove $6$ you also remove $3$, but if you remove $3$, you don't remove $6.$
$endgroup$
– saulspatz
Jan 13 at 1:18
$begingroup$
Ok - my mistake - reading too fast
$endgroup$
– Henry
Jan 13 at 1:24
1
$begingroup$
It's a special instance of the poset game, but not one that I've found any references to.
$endgroup$
– Misha Lavrov
Jan 13 at 1:58