For which of the starting polynomials can Alice ensure that Bob does not win in finite number of moves?
$begingroup$
Note: More than one option maybe correct.
Alice and Bob are playing a game. At the beginning of the game, there is a
cubic polynomial with integral coefficients written on the blackboard, which we denote as
the starting polynomial. The two players take turns one by one. In each turn, the player either chooses any natural number $n$ and replaces the existing cubic polynomial $f(x)$ on the blackboard by any one of $f(n + x), f(nx), f(x) + n$ or just changes the sign of the
coefficients of $x^2$ , i.e. if the existing polynomial is $a_0 + a_1x + a_2x^2 + a_3x^3$, then he can replace it by $a_0 + a_1x - a_2x^2 + a_3x^3$. Alice takes the first turn. Bob wins if, after finitely many moves, the cubic polynomial on the blackboard has all coefficients (upto $x^3$) non-zero and equal. For which of the starting polynomials can Alice ensure that Bob does not win in finite number of moves?
a) $x^3+4x^2+4x+1$
b) $x^3+6x^2+7x$
c) $x^3+3$
d) none of the above
It is an art of problem-solving question and I am not getting any clue. Please help how to solve these problems.
combinatorics functions polynomials recurrence-relations contest-math
asked Jan 10 at 21:04
GimgimGimgim
34314
$endgroup$
add a comment |
$begingroup$
Note: More than one option maybe correct.
Alice and Bob are playing a game. At the beginning of the game, there is a
cubic polynomial with integral coefficients written on the blackboard, which we denote as
the starting polynomial. The two players take turns one by one. In each turn, the player either chooses any natural number $n$ and replaces the existing cubic polynomial $f(x)$ on the blackboard by any one of $f(n + x), f(nx), f(x) + n$ or just changes the sign of the
coefficients of $x^2$ , i.e. if the existing polynomial is $a_0 + a_1x + a_2x^2 + a_3x^3$, then he can replace it by $a_0 + a_1x - a_2x^2 + a_3x^3$. Alice takes the first turn. Bob wins if, after finitely many moves, the cubic polynomial on the blackboard has all coefficients (upto $x^3$) non-zero and equal. For which of the starting polynomials can Alice ensure that Bob does not win in finite number of moves?
a) $x^3+4x^2+4x+1$
b) $x^3+6x^2+7x$
c) $x^3+3$
d) none of the above
It is an art of problem-solving question and I am not getting any clue. Please help how to solve these problems.
combinatorics functions polynomials recurrence-relations contest-math
asked Jan 10 at 21:04
GimgimGimgim
34314
$endgroup$
$begingroup$
If $n$ is natural, how could he get the example you gave, with a negative coefficient $-a_2x^2$?
$endgroup$
– Lincon Ribeiro
Jan 10 at 21:18
$begingroup$
@LinconRibeiro: that was one of the options for the players, to negate the quadratic term.
$endgroup$
– Ross Millikan
Jan 10 at 21:27
$begingroup$
Are you sure you stated the problem correctly? It seems so hard for Bob to win that I would expect there to be cases where he does to make it interesting.
$endgroup$
– Ross Millikan
Jan 10 at 21:53
$begingroup$
Yes, artofproblemsolving.com/community/c6h1574839p11554312 this is the link.
$endgroup$
– Gimgim
Jan 10 at 21:54
add a comment |
$begingroup$
Note: More than one option maybe correct.
Alice and Bob are playing a game. At the beginning of the game, there is a
cubic polynomial with integral coefficients written on the blackboard, which we denote as
the starting polynomial. The two players take turns one by one. In each turn, the player either chooses any natural number $n$ and replaces the existing cubic polynomial $f(x)$ on the blackboard by any one of $f(n + x), f(nx), f(x) + n$ or just changes the sign of the
coefficients of $x^2$ , i.e. if the existing polynomial is $a_0 + a_1x + a_2x^2 + a_3x^3$, then he can replace it by $a_0 + a_1x - a_2x^2 + a_3x^3$. Alice takes the first turn. Bob wins if, after finitely many moves, the cubic polynomial on the blackboard has all coefficients (upto $x^3$) non-zero and equal. For which of the starting polynomials can Alice ensure that Bob does not win in finite number of moves?
a) $x^3+4x^2+4x+1$
b) $x^3+6x^2+7x$
c) $x^3+3$
d) none of the above
It is an art of problem-solving question and I am not getting any clue. Please help how to solve these problems.
combinatorics functions polynomials recurrence-relations contest-math
asked Jan 10 at 21:04
GimgimGimgim
34314
$endgroup$
Note: More than one option maybe correct.
Alice and Bob are playing a game. At the beginning of the game, there is a
cubic polynomial with integral coefficients written on the blackboard, which we denote as
the starting polynomial. The two players take turns one by one. In each turn, the player either chooses any natural number $n$ and replaces the existing cubic polynomial $f(x)$ on the blackboard by any one of $f(n + x), f(nx), f(x) + n$ or just changes the sign of the
coefficients of $x^2$ , i.e. if the existing polynomial is $a_0 + a_1x + a_2x^2 + a_3x^3$, then he can replace it by $a_0 + a_1x - a_2x^2 + a_3x^3$. Alice takes the first turn. Bob wins if, after finitely many moves, the cubic polynomial on the blackboard has all coefficients (upto $x^3$) non-zero and equal. For which of the starting polynomials can Alice ensure that Bob does not win in finite number of moves?
a) $x^3+4x^2+4x+1$
b) $x^3+6x^2+7x$
c) $x^3+3$
d) none of the above
It is an art of problem-solving question and I am not getting any clue. Please help how to solve these problems.
combinatorics functions polynomials recurrence-relations contest-math
combinatorics functions polynomials recurrence-relations contest-math
asked Jan 10 at 21:04
GimgimGimgim
34314
asked Jan 10 at 21:04
GimgimGimgim
34314
asked Jan 10 at 21:04
GimgimGimgim
34314
asked Jan 10 at 21:04
GimgimGimgim
34314
asked Jan 10 at 21:04
GimgimGimgim
34314
34314
$begingroup$
If $n$ is natural, how could he get the example you gave, with a negative coefficient $-a_2x^2$?
$endgroup$
– Lincon Ribeiro
Jan 10 at 21:18
$begingroup$
@LinconRibeiro: that was one of the options for the players, to negate the quadratic term.
$endgroup$
– Ross Millikan
Jan 10 at 21:27
$begingroup$
Are you sure you stated the problem correctly? It seems so hard for Bob to win that I would expect there to be cases where he does to make it interesting.
$endgroup$
– Ross Millikan
Jan 10 at 21:53
$begingroup$
Yes, artofproblemsolving.com/community/c6h1574839p11554312 this is the link.
$endgroup$
– Gimgim
Jan 10 at 21:54
add a comment |
$begingroup$
If $n$ is natural, how could he get the example you gave, with a negative coefficient $-a_2x^2$?
$endgroup$
– Lincon Ribeiro
Jan 10 at 21:18
$begingroup$
@LinconRibeiro: that was one of the options for the players, to negate the quadratic term.
$endgroup$
– Ross Millikan
Jan 10 at 21:27
$begingroup$
Are you sure you stated the problem correctly? It seems so hard for Bob to win that I would expect there to be cases where he does to make it interesting.
$endgroup$
– Ross Millikan
Jan 10 at 21:53
$begingroup$
Yes, artofproblemsolving.com/community/c6h1574839p11554312 this is the link.
$endgroup$
– Gimgim
Jan 10 at 21:54
$begingroup$
If $n$ is natural, how could he get the example you gave, with a negative coefficient $-a_2x^2$?
$endgroup$
– Lincon Ribeiro
Jan 10 at 21:18
$begingroup$
If $n$ is natural, how could he get the example you gave, with a negative coefficient $-a_2x^2$?
$endgroup$
– Lincon Ribeiro
Jan 10 at 21:18
$begingroup$
@LinconRibeiro: that was one of the options for the players, to negate the quadratic term.
$endgroup$
– Ross Millikan
Jan 10 at 21:27
$begingroup$
@LinconRibeiro: that was one of the options for the players, to negate the quadratic term.
$endgroup$
– Ross Millikan
Jan 10 at 21:27
$begingroup$
Are you sure you stated the problem correctly? It seems so hard for Bob to win that I would expect there to be cases where he does to make it interesting.
$endgroup$
– Ross Millikan
Jan 10 at 21:53
$begingroup$
Are you sure you stated the problem correctly? It seems so hard for Bob to win that I would expect there to be cases where he does to make it interesting.
$endgroup$
– Ross Millikan
Jan 10 at 21:53
$begingroup$
Yes, artofproblemsolving.com/community/c6h1574839p11554312 this is the link.
$endgroup$
– Gimgim
Jan 10 at 21:54
$begingroup$
Yes, artofproblemsolving.com/community/c6h1574839p11554312 this is the link.
$endgroup$
– Gimgim
Jan 10 at 21:54
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Alice can keep from losing with any starting polynomial with nonnegative coefficients that includes a non-zero cubic term. She can always use the $f(x)+n$ option leave a polynomial $ax^3+bx^2+cx+d$ with $d gt a$ and the ratio $frac da$ not a cube. If Bob negates the squared term she just negates it back. As long as all the coefficients are nonnegative, all the options except $f(nx)$ will keep the constant term larger than the coefficient of the $x^3$ term. As long as the ratio is not a cube Bob can never make the coefficient of the $x^3$ term match the constant.
The only reason I specified non-negative coefficients was to make sure the $f(x+n)$ option cannot decrease the constant term. I would be surprised if Alice cannot win all of those as well.
The same argument applies to quadratics and linear polynomials using the leading term, but you need to adapt the requirement for the ratio between the the constant term and the leading coefficient.
answered Jan 10 at 21:50
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
Hi, Will you please explain with one of the example say for the polynomial a)?
$endgroup$
– Gimgim
Jan 10 at 21:53
1
$begingroup$
Alice just adds $2$ to get $x^3+4x^2+4x+3$. Bob can't win this move because the only way to get the leading term higher is $f(xn)$ which multiplies the $1$ by a cube. He cannot produce $3$ this way, so cannot win this time. If Bob moves to $f(2n), 8x^3+16x^2+8x+3$ Alice can just add $6$, say. As long as $d gt a$ the only polynomials that Bob can win from are ones of the form $ax^3+anx^2+an^2x+an^3$. Alice just has to avoid these.
$endgroup$
– Ross Millikan
Jan 10 at 22:00
add a comment |
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%2f3069170%2ffor-which-of-the-starting-polynomials-can-alice-ensure-that-bob-does-not-win-in%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Alice can keep from losing with any starting polynomial with nonnegative coefficients that includes a non-zero cubic term. She can always use the $f(x)+n$ option leave a polynomial $ax^3+bx^2+cx+d$ with $d gt a$ and the ratio $frac da$ not a cube. If Bob negates the squared term she just negates it back. As long as all the coefficients are nonnegative, all the options except $f(nx)$ will keep the constant term larger than the coefficient of the $x^3$ term. As long as the ratio is not a cube Bob can never make the coefficient of the $x^3$ term match the constant.
The only reason I specified non-negative coefficients was to make sure the $f(x+n)$ option cannot decrease the constant term. I would be surprised if Alice cannot win all of those as well.
The same argument applies to quadratics and linear polynomials using the leading term, but you need to adapt the requirement for the ratio between the the constant term and the leading coefficient.
answered Jan 10 at 21:50
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
Hi, Will you please explain with one of the example say for the polynomial a)?
$endgroup$
– Gimgim
Jan 10 at 21:53
1
$begingroup$
Alice just adds $2$ to get $x^3+4x^2+4x+3$. Bob can't win this move because the only way to get the leading term higher is $f(xn)$ which multiplies the $1$ by a cube. He cannot produce $3$ this way, so cannot win this time. If Bob moves to $f(2n), 8x^3+16x^2+8x+3$ Alice can just add $6$, say. As long as $d gt a$ the only polynomials that Bob can win from are ones of the form $ax^3+anx^2+an^2x+an^3$. Alice just has to avoid these.
$endgroup$
– Ross Millikan
Jan 10 at 22:00
add a comment |
$begingroup$
Alice can keep from losing with any starting polynomial with nonnegative coefficients that includes a non-zero cubic term. She can always use the $f(x)+n$ option leave a polynomial $ax^3+bx^2+cx+d$ with $d gt a$ and the ratio $frac da$ not a cube. If Bob negates the squared term she just negates it back. As long as all the coefficients are nonnegative, all the options except $f(nx)$ will keep the constant term larger than the coefficient of the $x^3$ term. As long as the ratio is not a cube Bob can never make the coefficient of the $x^3$ term match the constant.
The only reason I specified non-negative coefficients was to make sure the $f(x+n)$ option cannot decrease the constant term. I would be surprised if Alice cannot win all of those as well.
The same argument applies to quadratics and linear polynomials using the leading term, but you need to adapt the requirement for the ratio between the the constant term and the leading coefficient.
answered Jan 10 at 21:50
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
Hi, Will you please explain with one of the example say for the polynomial a)?
$endgroup$
– Gimgim
Jan 10 at 21:53
1
$begingroup$
Alice just adds $2$ to get $x^3+4x^2+4x+3$. Bob can't win this move because the only way to get the leading term higher is $f(xn)$ which multiplies the $1$ by a cube. He cannot produce $3$ this way, so cannot win this time. If Bob moves to $f(2n), 8x^3+16x^2+8x+3$ Alice can just add $6$, say. As long as $d gt a$ the only polynomials that Bob can win from are ones of the form $ax^3+anx^2+an^2x+an^3$. Alice just has to avoid these.
$endgroup$
– Ross Millikan
Jan 10 at 22:00
add a comment |
$begingroup$
Alice can keep from losing with any starting polynomial with nonnegative coefficients that includes a non-zero cubic term. She can always use the $f(x)+n$ option leave a polynomial $ax^3+bx^2+cx+d$ with $d gt a$ and the ratio $frac da$ not a cube. If Bob negates the squared term she just negates it back. As long as all the coefficients are nonnegative, all the options except $f(nx)$ will keep the constant term larger than the coefficient of the $x^3$ term. As long as the ratio is not a cube Bob can never make the coefficient of the $x^3$ term match the constant.
The only reason I specified non-negative coefficients was to make sure the $f(x+n)$ option cannot decrease the constant term. I would be surprised if Alice cannot win all of those as well.
The same argument applies to quadratics and linear polynomials using the leading term, but you need to adapt the requirement for the ratio between the the constant term and the leading coefficient.
answered Jan 10 at 21:50
Ross MillikanRoss Millikan
301k24200375
$endgroup$
Alice can keep from losing with any starting polynomial with nonnegative coefficients that includes a non-zero cubic term. She can always use the $f(x)+n$ option leave a polynomial $ax^3+bx^2+cx+d$ with $d gt a$ and the ratio $frac da$ not a cube. If Bob negates the squared term she just negates it back. As long as all the coefficients are nonnegative, all the options except $f(nx)$ will keep the constant term larger than the coefficient of the $x^3$ term. As long as the ratio is not a cube Bob can never make the coefficient of the $x^3$ term match the constant.
The only reason I specified non-negative coefficients was to make sure the $f(x+n)$ option cannot decrease the constant term. I would be surprised if Alice cannot win all of those as well.
The same argument applies to quadratics and linear polynomials using the leading term, but you need to adapt the requirement for the ratio between the the constant term and the leading coefficient.
answered Jan 10 at 21:50
Ross MillikanRoss Millikan
301k24200375
edited Jan 10 at 22:11
answered Jan 10 at 21:50
Ross MillikanRoss Millikan
301k24200375
answered Jan 10 at 21:50
Ross MillikanRoss Millikan
301k24200375
answered Jan 10 at 21:50
Ross MillikanRoss Millikan
301k24200375
301k24200375
$begingroup$
Hi, Will you please explain with one of the example say for the polynomial a)?
$endgroup$
– Gimgim
Jan 10 at 21:53
1
$begingroup$
Alice just adds $2$ to get $x^3+4x^2+4x+3$. Bob can't win this move because the only way to get the leading term higher is $f(xn)$ which multiplies the $1$ by a cube. He cannot produce $3$ this way, so cannot win this time. If Bob moves to $f(2n), 8x^3+16x^2+8x+3$ Alice can just add $6$, say. As long as $d gt a$ the only polynomials that Bob can win from are ones of the form $ax^3+anx^2+an^2x+an^3$. Alice just has to avoid these.
$endgroup$
– Ross Millikan
Jan 10 at 22:00
add a comment |
$begingroup$
Hi, Will you please explain with one of the example say for the polynomial a)?
$endgroup$
– Gimgim
Jan 10 at 21:53
1
$begingroup$
Alice just adds $2$ to get $x^3+4x^2+4x+3$. Bob can't win this move because the only way to get the leading term higher is $f(xn)$ which multiplies the $1$ by a cube. He cannot produce $3$ this way, so cannot win this time. If Bob moves to $f(2n), 8x^3+16x^2+8x+3$ Alice can just add $6$, say. As long as $d gt a$ the only polynomials that Bob can win from are ones of the form $ax^3+anx^2+an^2x+an^3$. Alice just has to avoid these.
$endgroup$
– Ross Millikan
Jan 10 at 22:00
$begingroup$
Hi, Will you please explain with one of the example say for the polynomial a)?
$endgroup$
– Gimgim
Jan 10 at 21:53
$begingroup$
Hi, Will you please explain with one of the example say for the polynomial a)?
$endgroup$
– Gimgim
Jan 10 at 21:53
1
1
$begingroup$
Alice just adds $2$ to get $x^3+4x^2+4x+3$. Bob can't win this move because the only way to get the leading term higher is $f(xn)$ which multiplies the $1$ by a cube. He cannot produce $3$ this way, so cannot win this time. If Bob moves to $f(2n), 8x^3+16x^2+8x+3$ Alice can just add $6$, say. As long as $d gt a$ the only polynomials that Bob can win from are ones of the form $ax^3+anx^2+an^2x+an^3$. Alice just has to avoid these.
$endgroup$
– Ross Millikan
Jan 10 at 22:00
$begingroup$
Alice just adds $2$ to get $x^3+4x^2+4x+3$. Bob can't win this move because the only way to get the leading term higher is $f(xn)$ which multiplies the $1$ by a cube. He cannot produce $3$ this way, so cannot win this time. If Bob moves to $f(2n), 8x^3+16x^2+8x+3$ Alice can just add $6$, say. As long as $d gt a$ the only polynomials that Bob can win from are ones of the form $ax^3+anx^2+an^2x+an^3$. Alice just has to avoid these.
$endgroup$
– Ross Millikan
Jan 10 at 22:00
add a comment |
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%2f3069170%2ffor-which-of-the-starting-polynomials-can-alice-ensure-that-bob-does-not-win-in%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$
If $n$ is natural, how could he get the example you gave, with a negative coefficient $-a_2x^2$?
$endgroup$
– Lincon Ribeiro
Jan 10 at 21:18
$begingroup$
@LinconRibeiro: that was one of the options for the players, to negate the quadratic term.
$endgroup$
– Ross Millikan
Jan 10 at 21:27
$begingroup$
Are you sure you stated the problem correctly? It seems so hard for Bob to win that I would expect there to be cases where he does to make it interesting.
$endgroup$
– Ross Millikan
Jan 10 at 21:53
$begingroup$
Yes, artofproblemsolving.com/community/c6h1574839p11554312 this is the link.
$endgroup$
– Gimgim
Jan 10 at 21:54