Bulgarian National Olympiad 2018 Problem 5

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

Bulgarian National Olympiad 2018 Problem 5

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

98 posts

#1 h Apr 15, 2018, 3:30 PM • 2 Y

Y by Adventure10, Mango247

Given a polynomial $P(x)=a_{d}x^{d}+ \ldots +a_{2}x^{2}+a_{0}$ with positive integers for coefficients and degree $d\geq 2$ . Consider the sequence defined by $b_{1}=a_{0} ,b_{n+1}=P(b_{n})$ for $n \geq 1$ . Prove that for all $n \geq 2$ there exists a prime $p$ such that $p$ divides $b_{n}$ but does not divide $b_{1}b_{2} \ldots b_{n-1}$ .

This post has been edited 2 times. Last edited by Lamp909, Apr 15, 2018, 3:32 PM

Z K Y

The post below has been deleted. Click to close.

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

4071 posts

#3 h Apr 15, 2018, 7:53 PM • 2 Y

Y by Adventure10, Mango247

It's not hard to prove that: for every prime number $p$ that $p\mid b_n$ for some $n$ , there exists index $i_0$ that

$p\mid b_{i_0}$ and $p\nmid b_j$ for all $1\leq j<i_0$ , and
For all $n$ that $p\mid b_n$ , we have $i_0\mid n$ and $\nu_p (b_n)=\nu_p (b_{i_0}).$

Note that this also implies $b_m\mid b_n$ for all $m\mid n$ .
Now, back to the problem, suppose for every prime $p\mid b_n$ , there exists $1\leq i<n$ that $p\mid b_i$ .

If there exists prime number $a$ that $\nu_a (n)\geq 2$ , we get that $d\mid \frac{n}{a}$ for all proper divisor $d$ of $n$ .
This gives $\nu_p (b_{\frac{n}{a}}) =\nu_p (b_n)$ for all $p\mid b_n$ .
So, $b_{\frac{n}{a}} \geq b_n$ . But it's clear that the sequence is strictly increasing, hence contradiction, done.

If there's no such prime divisor $a$ , i.e. $n$ can be written as product of distinct prime numbers.
If $n$ is prime, we get that $\nu_p (b_1)=\nu_p (b_n)$ for all $p\mid b_n$ . So, $b_1\geq b_n$ , contradiction.
Now, we're left with the case that $n$ has two distinct prime factors, say they're $u$ and $v$ .
We get that $d\mid \frac{n}{u}$ or $d\mid \frac{n}{v}$ for all proper divisor $d$ of $n$ .
Hence, for all $p\mid b_n$ , either $\nu_p (b_{\frac{n}{u}}) =\nu_p (b_n)$ or $\nu_p (b_{\frac{n}{v}}) =\nu_p (b_n)$ .
This gives
$b_n\leq \mathrm{lcm} (b_{\frac{n}{u}} ,b_{\frac{n}{v}} )=\frac{ b_{\frac{n}{u}}b_{\frac{n}{v}}}{\gcd (b_{\frac{n}{u}},b_{\frac{n}{v}})}\leq b_{\frac{n}{u}}b_{\frac{n}{v}}.$ But it's clear that $b_{i+1}> b_i^2$ for all $i$ , so $b_n>b_{\frac{n}{u}}b_{\frac{n}{v}}$ , this contradict the above inequality, done.

This post has been edited 2 times. Last edited by ThE-dArK-lOrD, Apr 15, 2018, 7:54 PM

Z K Y

The post below has been deleted. Click to close.

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

1593 posts

#4 h Apr 16, 2018, 12:49 AM • 5 Y

Y by ThE-dArK-lOrD, Aryan-23, sabkx, Adventure10, Mango247

Just copy solution of ISL 2014 N7.

Z K Y

The post below has been deleted. Click to close.

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

64 posts

TacH

#5 h Apr 16, 2018, 5:55 AM • 2 Y

Y by Adventure10, Mango247

btw, just to give an alternate way to ThE-dArK-lOrD's sol
from
1) $p\mid b_{i_0}$ and $p\nmid b_j$ for all $1\leq j<i_0$ , and
2) For all $n$ that $p\mid b_n$ , we have $i_0\mid n$ and $\nu_p (b_n)=\nu_p (b_{i_0}).$

supposes we look at $b_n$ . for every prime $p\mid b_n$ , there exists $1\leq i<n$ that $p\mid b_i$ ,indeed $i\mid n$
we pair up each prime that divides $b_n$ with the index given by 1) condition ; note that the index divides $n$ hence, it is at most $\frac{n}{2}$
since $\nu_p (b_n)=\nu_p (b_{i_0}).$ the product of $b_i$ that include in the pairing must be not less than $b_n$
Hence, we must have $b_1b_2b_3...b_{\frac{n}{2}} \geq b_n$
but $b_{i} < b_{\frac{n}{2}}$ for $i < \frac{n}{2}$ . Thus $b_1b_2b_3...b_{\frac{n}{2}} < (b_{\frac{n}{2}})^{\frac{n}{2}}$
but $b_{i+1} \geq b_{i}^2$ . Hence $b_n > (b_{\frac{n}{2}})^{2^{\frac{n}{2}}}$
Hence $\frac{n}{2} > 2^{\frac{n}{2}}$ Which leads to a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

370 posts

#6 h May 5, 2018, 7:24 PM • 2 Y

Y by Adventure10, Mango247

Very similar to ISL 2014, N7.
It is also a generalization of 2016 China TST https://artofproblemsolving.com/community/c6h1212540p6016827

Z K Y

The post below has been deleted. Click to close.

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

308 posts

#7 h Oct 23, 2020, 9:47 AM • 1 Y

Y by leozitz

Notice that $b_n=P^n(0)$ , for convenience assume $b_0=0$ .
Suppose on the contrary that there exists $n$ such that for every prime divisor of $b_n$ is also a prime divisor of $b_{n-1}b_{n-2}...b_1$ .
CLAIM 1. For each integer $n$ we have
$b_n>b_{n-1}b_{n-2}...b_1$ Proof.
We proceed by induction, the base case is obvious, now we have
$b_n=P(b_{n-1})>b_{n-1}^2>b_{n-1}b_{n-2}...b_1$ by inductive hypothesis. $\blacksquare$
Therefore, there exists some prime $p$ such that $v_p(b_n)>v_p(b_{n-1}b_{n-2}...b_1)\qquad(1)$ Let $k$ be the smallest positive integer such that $p|b_k$ . Let $Q(x)=P^k(x)$ . From an order argument we have $k|n$ . Now notice that the coefficient of $x$ in $Q(x)$ is $0$ , so $v_p(b_{2k})=Q(b_k)=v_p(b_k)$ , and inductively we have $v_p(b_n)=v_p(b_k)$ , whcih contradicts $(1)$ , so we are done.

This post has been edited 1 time. Last edited by mathaddiction, Oct 23, 2020, 9:50 AM

Z K Y

The post below has been deleted. Click to close.

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

1193 posts

#8 h Mar 9, 2025, 11:24 PM

Y by

Very confusing formulation for me, $b_1 = a_0$ looks weird and it is hard to accept that there is no $x$ term. Anyway, a really great problem by Navid Safaei! Here is a better formulation in my opinion, and a solution:

Alternative formulation wrote:

Let $P(x)$ be a polynomial of degree at least $2$ , where the coefficient at $x$ is zero and all other coefficients are positive integers. Consider the sequence $a_1 = P(0)$ , $a_{n+1} = P(a_n)$ . Prove that for any $n\geq 2$ there exists a prime $p$ which divides $a_n$ , but does not divide any of $a_1,a_2,\ldots,a_{n-1}$ .

Let $n$ be an arbitrary index, $p$ be a prime divisor of $a_n$ and let $\nu_p(a_n) = r \geq 1$ . Then $a_{n+1} = Ka_n^2 + P(0) = Ka_n^2 + a_1$ for some integer $K$ and in particular $a_{n+1} \equiv a_1 \pmod {p^{r+1}}$ . Since $P$ is a polynomial, it follows that $P(a_{n+1}) \equiv P(a_1) \pmod {p^{r+1}}$ , i.e. $a_{n+2} \equiv a_2 \pmod {p^{r+1}}$ . Continuing inductively, we obtain $a_{n+k} \equiv a_k \pmod {p^{r+1}}$ for all $k$ . In particular, it follows that $a_n \equiv a_{sn} \pmod {p^{r+1}}$ for any positive integer $s$ . Now since $\nu_p(a_n) = r$ , it necessarily follows that $\nu_p(a_{sn}) = r$ for any $s$ .

Now suppose $n$ does not satisfy the problem condition, i.e. for any prime divisor $p$ of $a_n$ there exists an index $i \leq n-1$ such that $p$ divides $a_i$ . By the above paragraph it follows that $\nu_p(a_n) = \nu_p(a_{ni}) = \nu_p(a_i)$ , hence $a_n$ divides $a_1a_2\cdots a_{n-1}$ .

To reach a contradiction, we prove by induction that $a_n > a_1a_2\cdots a_{n-1}$ for any $n\geq 2$ . For the base case, note that $a_2 = P(a_1) \geq a_1^2 + P(0) > a_1$ . For the induction step, it suffices to prove $a_{n+1} > a_n^2$ to obtain the main inequality for $n+1$ from the main inequality for $n$ . For the latter, note similarly that $a_{n+1} = P(a_n) \geq a_n^2 + P(0) > a_n^2$ .

This post has been edited 1 time. Last edited by Assassino9931, Mar 10, 2025, 1:36 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a