Game of Polynomials

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Game of Polynomials

G H J

Reveal topic tags

Combinatorial games

L

G H BBookmark kLocked kLocked NReply

Source: Tournament of Towns 2016 Fall Tour, A Senior, Problem #6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1980 posts

#1 h Apr 22, 2017, 7:14 PM • 7 Y

Y by Wave-Particle, Ankoganit, dgrozev, Adventure10, Mango247, TheHimMan, ohiorizzler1434

Petya and Vasya play the following game. Petya conceives a polynomial $P(x)$ having integer coefficients. On each move, Vasya pays him a ruble, and calls an integer $a$ of his choice, which has not yet been called by him. Petya has to reply with the number of distinct integer solutions of the equation $P(x)=a$ . The game continues until Petya is forced to repeat an answer. What minimal amount of rubles must Vasya pay in order to win?

(Anant Mudgal)

(Translated from here.)

This post has been edited 2 times. Last edited by anantmudgal09, Feb 5, 2018, 1:11 PM
Reason: Titular reference to "Game of Thrones"

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3070 posts

#2 h Apr 23, 2017, 11:41 AM • 9 Y

Y by anantmudgal09, Vietnamisalwaysinmyheart, Vrangr, hansu, Wizard_32, kamatadu, Adventure10, Ru83n05, EvansGressfield

This is a very cute problem, so let's hope I got this right for Anant's sake

We claim that Vasya could do with $4$ rubles. We'll use the following notation: for an integer $a$ , $n(a)$ is the number of distinct integer roots of $P(x)=a$ . We'll first prove a lemma:

Lemma: If $P(x)=a$ has $3$ or more distinct integer root for some $P(x)\in\mathbb Z[x]$ and $a\in \mathbb Z$ , then both the equations $P(x)=a+1$ and $P(x)=a-1$ have no integer root.
Proof: We can shift the origin appropriately and assume WLOG $a=0$ . Then $P(x)=(x-a_1)^{b_1}(x-a_2)^{b_2}(x-a_3)^{b_3}Q(x)$ for integers $a_i$ 's , $b_i$ 's and $Q\in\mathbb Z[x]$ . Here $a_i$ 's are all distinct and $b_i$ 's are all positive. Then to have $|P(x)|=1$ , we'll need $(x-a_i)=\pm 1$ for each $i$ ; but by PHP, this is impossible with distinct $a_i$ 's. This proves our lemma. $\square$

Now for the main problem. We'll first show that Vasya can win in at most $4$ moves. Let Vasya call the integers $0,-1,+1$ in the first three moves. If $n(0)\ge 3$ , then $n(1)=n(-1)=0$ by the lemma and Vasya wins. If one of $n(1)$ and $n(-1)$ is $\ge 3$ , say WLOG $n(1)=3$ ; then Vasya can call $2$ in the next move and win, because then $n(0)=n(2)=0$ by our lemma. So suppose $n(0), n(1),n(-1)$ are all $\le 2$ . If some of two these were equal, Vasya would've won already, so let's say $n(0),n(-1),n(1)$ are $0,1,2$ in some order. Then at least one of $n(1)$ and $n(-1)$ is nonzero; say WLOG $n(1)\ne 0$ . Then let Vasya call $2$ in the fourth move. $n(2)$ can't be $\ge 3$ , or we would have $n(1)=0$ ; so $n(2)\in\{0,1,2\}$ , so it has to collide with one of $n(0),n(1),n(-1)$ , letting Vasya win.

Now it remains to show that Vasya can't be sure of winning in $3$ moves or less. Indeed, we may WLOG assume the first integer called by Vasya is $0$ . Then if he calls the integers $a$ and $b$ in the next two moves and hopes to win, then Petya could smash his hopes by conceiving the polynomial $P(x)\equiv -a(x-1)(x-3)\left( (x-2)^2\left(x^{2016}+|b|+2017^{2017}\right)+1\right).$ Indeed, $P(x)=0$ has two roots $1$ and $3$ ; $P(x)=a$ has only one root $2$ , because $P(x)=a\implies |(x-1)(x-3)|=1\implies x=2;$ and $P(x)=b$ has no roots at all, because for $x\not\in \{1,2,3\}$ , we have $|P(x)|>b$ . Thus we're done. $\blacksquare$

This post has been edited 2 times. Last edited by Ankoganit, Apr 23, 2017, 11:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2463 posts

#3 h Apr 23, 2017, 1:08 PM • 3 Y

Y by anantmudgal09, Adventure10, Mango247

@Anant Mudgal: Not that it matters, but Petya and Vasya are russian male names. So- him/his.

I suppose your original statement was different, but the russians change it in their Petya/Vasya game style ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1980 posts

#4 h Apr 23, 2017, 1:17 PM • 3 Y

Y by Ankoganit, Adventure10, Mango247

dgrozev wrote:

@Anant Mudgal: Not that it matters, but Petya and Vasya are russian male names. So- him/his.

I suppose your original statement was different, but the russians change it in their Petya/Vasya game style ?

Thanks for pointing, I had this misconception for a while

. As you said, my original formulation involved Alice and Bob, which was taken as it is in the English version. Interestingly, I didn't pose it in the form of a game involving money, but it looks like Russian paper setters are fond of it.

@Ankoganit, that's almost the same idea I had in mind (except my phrasing of the key lemma wasn't as tidy). I had a different construction though; and it turns out that the contestants gave many other constructions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2463 posts

#5 h Apr 23, 2017, 1:39 PM • 17 Y

Y by BartSimpsons, anantmudgal09, Ankoganit, Tintarn, rafayaashary1, 62861, claserken, InCtrl, tarzanjunior, Wizard_32, AlastorMoody, starchan, Assassino9931, Adventure10, Mango247, Supercali, kiyoras_2001

anantmudgal09 wrote:

...Interestingly, I didn't pose it in the form of a game involving money, but it looks like Russian paper setters are fond of it.

Don't worry, it could have been... glasses of vodka.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1980 posts

#6 h Apr 23, 2017, 1:44 PM • 2 Y

Y by Adventure10, Mango247

...........

This post has been edited 1 time. Last edited by anantmudgal09, Feb 2, 2020, 3:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3070 posts

#7 h Apr 23, 2017, 1:47 PM • 9 Y

Y by anantmudgal09, rafayaashary1, biomathematics, Wizard_32, AlastorMoody, kamatadu, anurag27826, Adventure10, Mango247

Who said he's gonna drink it?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1980 posts

#8 h Apr 23, 2017, 2:01 PM • 4 Y

Y by rafayaashary1, Ankoganit, Wizard_32, Adventure10

I'll post my solution for the part about construction. Proof for sufficiency of $4$ moves is the same as in post #2.

WLOG, assume Vasya is done in $3$ moves (for lesser number, he simply asks random questions to reach $3$ ). Petra replies with $1,2,0$ in this order. To see his answers are consistent, let $m, n, l$ be the numbers asked by Vasya in this order. Then, for $P(X) \overset{\text{def}}{:=} tX^4+(n-m-t)X^2+m,$ where $t$ is a positive integer, so that $P$ is increasing over positive integers. We have $P(0)=m$ and $P(\pm 1)=n$ and $P(2)>\operatorname{max}\{m, n, l \}$ so we are done.

This post has been edited 1 time. Last edited by anantmudgal09, Feb 2, 2020, 3:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

primesarespecial

364 posts

primesarespecial

#9 h Jan 21, 2022, 7:23 AM

Y by

The minimum number of rubles Vasya needs to pay is $4$ .
We divide into two cases.Firstly Vasya asks $0$ .
If $P$ does not have an integer root,then let Vasya ask integers $d>1$ and $d+1$ .We must have solutions to $P(x)=d,d+1$ ,otherwise we are done.
Let $a_1<a_2,..<a_r$ and $b_1<b_2...<b_k$ be such that $P(a_i)=d,P(b_i)=d+1$ .WLOG,assume $r>k>0$ ,since $b_i -a_j|1$ ,for any $i,j$ ,we can conclude that for this to be true, $r=2,k=1$ and we have $a_2=a_1+2,b_1=a_1+1$ .Now,if Vasya asks $d-1$ ,we can conclude by the same logic for $d-1,d$ that $P(x)=d-1$ has no solutions and we are done in at most $4$ moves.

Now,if $P$ has an integer root,then we can be done by Vasya asking $0,1,-1,-2$ or $0,1,-1,2$ (depending on whether $P(x)-1$ or $P(x)+1$ has no integer roots),by the same logic in the first case.

Now,we give a construction where $3$ fails.Let Vasya ask $a<b<c$ .
Then Petya conceives $P(x)=(a-b)(x+1)(x+3)+a$ ,for which $P(x)=a,b,c$ has $2,1,0$ solutions respectively.

This post has been edited 2 times. Last edited by primesarespecial, Jan 21, 2022, 7:24 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#10 h Dec 19, 2022, 3:22 AM

Y by

The answer is $4$ rubles.

We first outline a strategy for Vasya to win by paying only four rubles. He begins by querying $0$ .
If Petya's response is $\geq 2$ , then by shifting WLOG let $P(x)=x(x-r)Q(x)$ where $Q$ is an arbitrary integer polynomial (possibly constant), and $r>0$ . He then queries $1$ and $-1$ . Note that for a response to be nonzero, we must have $x,x-r \in \{-1,1\}$ simultaneously. Since $r>0$ this forces $r=2$ and $x=1$ , in which case one answer is zero and the other is one. In this case (since in the other case our responses are 2, 0, 0 and Vasya wins by paying three rubles), query $2$ , which forces $x,x-2 \in \{-1,1,-2,2\}$ if the answer is nonzero. $x=1$ fails because $P(1)=1$ , and $x \in \{-1,-2.2\}$ fail because then $x-2 \not \in \{-1,1,-2,2\}$ , so Petya answers zero and thus repeats a prior answer.
If Petya's response is $0$ or $1$ , then Vasya queries $1000$ . If the response to that query is $\geq 2$ , Vasya then queries $999$ and $1001$ . By our previous result (shifted appropriately), if the responses to these two queries are different then they are $0$ and $1$ , so there is a repeat. On the other hand, if the response to our $1000$ query is $1$ or $0$ (the opposite of what the first response is), then query $10000$ . If the response to that is $0$ or $1$ we're done, and if it's $\geq 2$ then query $10001$ which for similar reasons as before must either be $0$ or $1$ . In any case, a response is repeated, and Vasya pays at most four rubles.

Now we prove that Vasya cannot win by paying three rubles. Note that the only information Vasya gains at the conclusion of each query is the response to the previous, so let's say that Petya is feeling nice and decides to tell Vasya beforehand that his answers to the first and second queries will be $2$ and $1$ respectively. However, this action isn't only done out of charity—now that Vasya cannot gain new information based on responses, Petya asks Vasya to write down his three queries beforehand. Despite this, Vasya's task is still made easier. However, Petya still cannot get Vasya to repeat an answer in the first three queries.
By shifting, WLOG let the first query be $0$ , the second one be $a$ , and the third one be $b$ . If Petya then selects the polynomial
$P(x)=-ax(x-2)(|b|(x(x-1)(x-2))^2+1).$ $P(x)=0$ then has solutions $0,2$ , $P(x)=a$ has $1$ as the only solution, since we would require $x,x-2 \in \{-1,1\}$ which forces $x=1$ . Finally, $P(x)=b$ has no solutions because the absolute value of the last factor is always greater than $|b|$ unless $x \in \{0,1,2\}$ , but these cases have already been handled and don't satisfy $P(x)=b$ . Thus the response to the third query will be $0$ , and Vasya will have to pay an additional ruble (at least) to get a repeat. We are done. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Dec 19, 2022, 3:25 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8866 posts

#11 h Jul 6, 2023, 6:52 AM

Y by

The answer is $4$ guesses.

Strategy: The key is the following claim.

Claim. For some integer polynomial $P$ , if $P(x) = a$ has at least $3$ solutions for some integer $a$ , then $P(x) = a\pm 1$ has no integer solutions.

Proof. Write $P(x) = (x-x_1)(x-x_2)(x-x_3)R(x) + a$ for integers $x_1, x_2, x_3$ and integer polynomial $R$ . For $P(x) = a \pm 1$ , $(x-x_1)(x-x_2)(x-x_3) = \pm 1$ , but this is impossible as the $x_i$ are distinct. $\blacksquare$

Now Vasya guesses $a = 0$ first. If Petya responds with any integer at least $3$ , Vasya can guess $a = 1$ and $a=-1$ and be sure that both answers will be $0$ .

If Petya responds with $1$ or $2$ , then Vasya may guess $1$ and $-1$ , knowing he will receive answers in $\{0, 1, 2\}$ . If both guesses reveal $0$ , he wins. Otherwise, suppose the answer to $1$ was nonzero; then Vasya can guess $2$ as well. Then by Pigeonhole, two of the four answers will be identical.

If Petya responds with $0$ , Vasya can again guess $1$ and $-1$ ; if one of them is zero, Petya wins; otherwise, the same Pigeonhole argument applies.

Bound: We show Vasya cannot win in three moves. Indeed, let his first three guesses be $a, b, c$ integers. Without loss of generality assume $a<b<c$ (the order of the guesses doesn't matter). Petya can pick the polynomial $P(x) = a+(c-a)(x-x_1)(x-(x_1+2))$ for some integer $x_1$ . Then $P(x) = a$ has two solutions, $P(x) = c$ has precisely one, and as the second term is at least $c-a$ when it is positive, $P(x) = b$ has no solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4188 posts

#12 h Aug 8, 2024, 11:15 PM

Y by

The answer is $4$ .

To show that $3$ is not enough, suppose Vasya queries $a,b,c$ for $a>b>c$ . Then, the polynomial $(a-b)x^2+b$ attains $a$ at $x=\pm 1$ , $b$ at $x=0$ , and $c$ never. Thus, Vasya does not win.

We claim that querying $0,1,2,3$ is sufficent, that is, no integer polynomial attains $0,1,2,3$ each a different number of times.

The key idea is to use the fact that $a-b|P(a)-P(b)$ . Consider the sequence $\dots,P(-2),P(-1),P(0),\dots$ . Suppose this sequence has $0,1,2,3$ each a different number of times. All instances of $0$ and all instances of $1$ must be adjacent, and same with all other consecutive pairs.

Some number has to happen at least $3$ times. If $1$ happens 3 times, then no position is adjacent to all three 1s, so $0$ and $2$ can never occur, contradiction. Same thing happens if $2$ happens at least $3$ times. Thus, WLOG assume $0$ happens at least $3$ times (3 is the same). Then $1$ can never occur, since no position is adjacent to all three $0$ s.

Therefore, at least one of $2$ and $3$ must appear at least twice, and the other must appear at least once. If $2$ appears at least twice, then the $3$ must be adjacen to both $2$ s, which forces $232$ . However, since $a-b\mid P(a)-P(b)$ , $0$ s must be within 2 spots of all $2$ s, but there is nowhere for $0$ s to go after $232$ , contradiction. If we had $323$ instead, we only have two spots that are valid spots for $0$ s, but there are $3$ of them, contradiction. Thus we are done.

Remark: The main idea of this problem is to invoke $a-b\mid P(a)-P(b)$ to restrict where outputs can lie. The key observation is that, if the polynomial is only required to have rational coefficents, then Petya can just interpolate through whatever Vasya queries, thus he cannot win. The key feature of integer polynomials that distinguishes it from rational ones is $a-b\mid P(a)-P(b)$ which is why we use it here.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1745 posts

OronSH

#13 h Oct 25, 2024, 11:51 PM

Y by

Answer: $4$ . Vasya calls $0$ . If it is $\ge 2$ , he calls $1,2,-1$ . If $1$ returns $\ge 1$ , then if $P(a)=P(b)=0$ and $P(c)=1$ , then $a-c,b-c\mid 1$ so $a,c,b$ are consecutive and in particular $c$ is unique so $1$ returns $1$ . Next if $P(d)=2$ , then $a-d,b-d\mid 2$ with $a-b=2$ so $d=c$ , contradiction, so $2$ returns $0$ , and similarly so does $-1$ . If $1$ returns $0$ and $2$ returns $1$ , then similarly $-1$ returns $0$ . Otherwise $1,2$ both return $0$ .

If $0$ returns $\le 1$ , then he calls $1,2,3$ . If $1$ is $\ge 2$ , then similarly either $2,3$ return the same value or $2,3$ return $0,1$ , one of which returns the same as $0$ . If $1$ is $\le 1$ but $2$ returns $\ge 2$ , then similarly $3$ returns either $0,1$ which returns the same as either $0$ or $1$ . If $0,1,2$ return $\le 1$ then two are the same.

To show $4$ is minimum, if Vasya calls $a,b,c$ , we claim Petya can return $2,1,0$ respectively, since Petya has $P(x)=(a-b)x^2+b$ if $a$ is not between $b$ and $c$ , and $P(x)=(a-b)x^{2\left\lfloor\log_4\frac{c-b}{a-b}\right\rfloor+2}+b$ otherwise.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

758 posts

#14 h Apr 28, 2025, 6:06 PM

Y by

Subjective Difficulty Rating

Attachments:

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a