Polynomial (Izho)

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

Polynomial (Izho)

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Izho

The post below has been deleted. Click to close.

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

97 posts

#1 h Jan 12, 2019, 12:05 PM • 6 Y

Y by Davrbek, Mathuzb, integrated_JRC, Adventure10, Mango247, Kingsbane2139

We define two types of operation on polynomial of third degree:
a) switch places of the coefficients of polynomial(including zero coefficients), ex:
$x^3+x^2+3x-2$ => $-2x^3+3x^2+x+1$
b) replace the polynomial $P(x)$ with $P(x+1)$
If limitless amount of operations is allowed,
is it possible from $x^3-2$ to get $x^3-3x^2+3x-3$ ?

Z K Y

The post below has been deleted. Click to close.

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

1298 posts

Kayak

#2 h Jan 12, 2019, 2:09 PM • 2 Y

Y by TheMathCruncher_007, Adventure10

The answer is no, we can't. We work with the root of the polynomials:

IZhO P?, reformatted wrote:

The number $2^{\frac{1}{3}}$ is written on the board. At each step, you can replace $x \mapsto \frac{1}{x}$ or replace $x \mapsto x-1$ . After some finite number of operations, can you reach $2^{\frac{1}{3}} + 1$ ?

Note that by an easy induction, a number is reachable from $x$ iff it's of the form $[-n_1; -n_2, -n_3, -n_4, \cdots, -n_k + x]$ , where $[a_1; a_2, a_3, \cdots, a_k]$ denote the continued fraction notation. Now by another easy induction. $[-n_1; -n_2, -n_3, -n_4, \cdots, -n_k + x] = \frac{P(x)}{Q(x)}$ for some LINEAR integral polynomials $P(x), Q(x)$ .

Let $\zeta = 2^{\frac{1}{3}}$ . Then $\frac{P(\zeta)}{Q(\zeta)} = \zeta+1 \Rightarrow P(\zeta) - (\zeta+1)Q(\zeta) = 0$ , or the minimal polynomial $M(x) := x^3 - 2$ divides $R(x):= P(x) - (x+1)Q(x)$ . But then $M(x)$ has degree $3$ , and $R(x)$ has degree at max $2$ , so $R$ must be identically zero. But as $P(x), Q(x)$ are coprime, that's possible iff $P(x) = (x+1), Q(x) = 1$ .

But that's false since for $k > 1$ , $\deg[Q] > 0$ . For $k = 1$ , $P(x) = x - m$ for some $m \in \mathbb{N}$ , so we can't do it.

This post has been edited 1 time. Last edited by Kayak, Jan 12, 2019, 2:11 PM

Z K Y

The post below has been deleted. Click to close.

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

698 posts

#3 h Jan 12, 2019, 2:17 PM • 1 Y

Y by Adventure10

Kayak wrote:

IZhO P?, reformatted wrote:

The number $2^{\frac{1}{3}}$ is written on the board. At each step, you can replace $x \mapsto \frac{1}{x}$ or replace $x \mapsto x-1$ . After some finite number of operations, can you reach $2^{\frac{1}{3}} + 1$ ?

$x^3-2 \mapsto x-2$ and in this case $2^{\frac{1}{3}} \mapsto 2$

Z K Y

The post below has been deleted. Click to close.

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

1298 posts

Kayak

#4 h Jan 12, 2019, 2:19 PM • 2 Y

Y by Adventure10, Mango247

rmtf1111 wrote:

Kayak wrote:

IZhO P?, reformatted wrote:

The number $2^{\frac{1}{3}}$ is written on the board. At each step, you can replace $x \mapsto \frac{1}{x}$ or replace $x \mapsto x-1$ . After some finite number of operations, can you reach $2^{\frac{1}{3}} + 1$ ?

$x^3-2 \mapsto x-2$ and in this case $2^{\frac{1}{3}} \mapsto 2$

So what ? (Sorry if I'm misreading the question/your post)

This post has been edited 1 time. Last edited by Kayak, Jan 12, 2019, 2:19 PM

Z K Y

The post below has been deleted. Click to close.

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

698 posts

#5 h Jan 12, 2019, 2:21 PM • 4 Y

Y by AFSA, Adventure10, Mango247, Mango247

wait, does

FrenchFries356 wrote:

a) switch places of the coefficients of polynomial

mean that $p(x) \mapsto x^3p\left(\frac{1}{x}\right)$ ? I just realized that this is what the example illustrates

rip 1hr of my life

This post has been edited 1 time. Last edited by rmtf1111, Jan 12, 2019, 2:22 PM

Z K Y

The post below has been deleted. Click to close.

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

1298 posts

Kayak

#6 h Jan 12, 2019, 2:21 PM • 4 Y

Y by Adventure10, Mango247, Mango247, Mango247

rmtf1111 wrote:

wait, does

FrenchFries356 wrote:

a) switch places of the coefficients of polynomial

mean that $p(x) \mapsto x^3p\left(\frac{1}{x}\right)$ ? I just realized that this is what the example illustrates

That's what I think it does.

Z K Y

The post below has been deleted. Click to close.

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

241 posts

#7 h Jan 16, 2019, 4:59 PM • 5 Y

Y by Polynom_Efendi, Illuzion, alinazarboland, Adventure10, Mango247

We are about to find some invariant/monovariant $f(a,b,c,d)$ such that $f(a,b,c,d) \ge f(d,c,b,a) \ge f(a, 3a+b, 3a+2b+c, a+b+c+d)$ or completely vice-versa. Clearly it must have $f(a,b,c,d)=f(d,c,b,a)$ . Note that the first operation does not change the set of "inner" and "outer" terms. So we can search for $f(a,b,c,d)=g(a,d) *** h(b,c)$ , where $g,h$ are symmetric wrt variables, and *** some operation. We may put *** to be $+$ and $g,h$ constant*product, thus we can find $g(x,y)=xy, h(x,y)=-3xy$ so $f(a,3a+b,3a+2b+c,a+b+c+d)-f(a,b,c,d)= \frac{(2b+3a)^2+3a^2}{2} \ge 0$ , and at the beginning $f(1,0,0,-2)=6$ , in the end $f(1,-3,3,-3)=0$ , contradiction.

This post has been edited 1 time. Last edited by MilosMilicev, Jan 16, 2019, 6:04 PM

Z K Y

The post below has been deleted. Click to close.

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

2459 posts

#8 h Jan 20, 2019, 10:15 AM • 3 Y

Y by alinazarboland, Adventure10, Mango247

It can be restated as follows.
For any homogeneous polynomial of two variables $P(x,y)$ , we define two operations:
a) Swap $x$ and $y$ , for example $x^3+x^2y+3xy^2-2y^3$ becomes $y^3+y^2x+3yx^2-2x^3$ .
b) Replace $P(x,y)$ with $P(x+y,y)$ .
Is it possible from $x^3-2y^3$ to get $x^3-3x^2y+3xy^2-3y^3$ ?

These two transformations correspond to the following linear transformations of the variables(vector) $(x,y)$ :
$\begin{align*} x'&=y\\ y'&=x \end{align*}$ and
$\begin{align*} x'&=x-y\\ y'&=y \end{align*}$ The matrices of these linear transformations are $A:=\begin{pmatrix} 1 &-1\\0&1 \end{pmatrix}$ and $B:=\begin{pmatrix} 0&1\\1&0 \end{pmatrix}$ . Thus, we ask if it's possible with $A$ and $B$ to generate the matrix $C:=\begin{pmatrix} 1&1\\0&1 \end{pmatrix}$

It remains to see that when multiplying a matrix $X:=\begin{pmatrix} a&b\\c&d\end{pmatrix}$ by $A$ or by $B$ , the product of the elements of the last column, $bd$ , doesn't increase (Proof).
Since the corresponding product of $A$ is $-1$ and that of $B$ is $0$ , we cannot get to $C$ , which product of the terms of the last column is $1$ .

Remark.

dgrozev wrote:

...Thus, we ask if it's possible with $A$ and $B$ to generate the matrix $C$ ...

It deserves attention, since it allows us to forget about the polynomials and focus only on the linear transformations (matrices). The argument uses the specific nature of $P(x,y)=x^3-2y^3$ . It's enough to establish the following claim:
Suppose $X$ is a matrix and variables $x,y$ and $x',y'$ are connected as:
$\begin{pmatrix}x'\\y'\end{pmatrix}=X\cdot \begin{pmatrix}x\\y\end{pmatrix}$ If $P(x',y')=P(x,y),\forall x,y\in \mathbb{R}$ then $A$ is the identity matrix.

This post has been edited 2 times. Last edited by dgrozev, Jan 20, 2019, 2:17 PM
Reason: Remark

Z K Y

The post below has been deleted. Click to close.

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

3 posts

#9 h Apr 8, 2019, 6:33 PM • 2 Y

Y by Adventure10, Mango247

MilosMilicev wrote:

We are about to find some invariant/monovariant $f(a,b,c,d)$ such that $f(a,b,c,d) \ge f(d,c,b,a) \ge f(a, 3a+b, 3a+2b+c, a+b+c+d)$ or completely vice-versa. Clearly it must have $f(a,b,c,d)=f(d,c,b,a)$ . Note that the first operation does not change the set of "inner" and "outer" terms. So we can search for $f(a,b,c,d)=g(a,d) *** h(b,c)$ , where $g,h$ are symmetric wrt variables, and *** some operation. We may put *** to be $+$ and $g,h$ constant*product, thus we can find $g(x,y)=xy, h(x,y)=-3xy$ so $f(a,3a+b,3a+2b+c,a+b+c+d)-f(a,b,c,d)= \frac{(2b+3a)^2+3a^2}{2} \ge 0$ , and at the beginning $f(1,0,0,-2)=6$ , in the end $f(1,-3,3,-3)=0$ , contradiction.

nice solution..

Z K Y

The post below has been deleted. Click to close.

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

26 posts

#10 h Apr 8, 2019, 11:53 PM • 3 Y

Y by test20, Adventure10, Mango247

There’s a 3 line (short) solution using complex roots.

Z K Y

The post below has been deleted. Click to close.

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

1193 posts

#13 h Jan 2, 2022, 6:39 PM • 1 Y

Y by hakN

@above Indeed, the first operation replaces each root $x_0$ with $\frac{1}{x_0}$ and the second one replaces $x_0$ with $x_0 - 1$ . Note that $\frac{1}{a+bi} = \frac{a-bi}{a^2+b^2}$ . Therefore, if at some point a polynomial has a root with a negative real part, then after each operation this real part stays negative.

The initial polynomial has $\sqrt[3]{2}\frac{-1+i\sqrt{3}}{2}$ as a root, with negative real part. However, the roots of $x^3 - 3x^2 + 3x - 3 = (x-1)^3 - 2$ are $2+\sqrt[3]{2}$ and $2+\sqrt[3]{2}\frac{-1\pm i\sqrt{3}}{2}$ , with positive real part. Contradiction!

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a