2017 China TSTST 1 Day 2 Problem 6

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

2017 China TSTST 1 Day 2 Problem 6

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2017 China TSTST 1 Day 2 Problem 6

The post below has been deleted. Click to close.

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

29 posts

#1 h Mar 7, 2017, 3:32 PM • 8 Y

Y by laegolas, baopbc, 62861, anantmudgal09, Ankoganit, Gaussian_cyber, Adventure10, Mango247

For a given positive integer $n$ and prime number $p$ , find the minimum value of positive integer $m$ that satisfies the following property: for any polynomial $f(x)=(x+a_1)(x+a_2)\ldots(x+a_n)$ ( $a_1,a_2,\ldots,a_n$ are positive integers), and for any non-negative integer $k$ , there exists a non-negative integer $k'$ such that $v_p(f(k))<v_p(f(k'))\leq v_p(f(k))+m.$ Note: for non-zero integer $N$ , $v_p(N)$ is the largest non-zero integer $t$ that satisfies $p^t\mid N$ .

This post has been edited 1 time. Last edited by djmathman, Jul 26, 2017, 10:34 PM
Reason: cleaned up wording

Z K Y

The post below has been deleted. Click to close.

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

889 posts

#3 h Mar 17, 2017, 10:36 AM • 2 Y

Y by Adventure10, Mango247

Sorry, I misread the problem...

This post has been edited 1 time. Last edited by toto1234567890, Mar 18, 2017, 1:32 AM

Z K Y

The post below has been deleted. Click to close.

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

364 posts

#4 h Mar 17, 2017, 5:35 PM • 3 Y

Y by adityaguharoy, Adventure10, Mango247

That is not right. The answer should be $n + v_p(n!)$ .

Z K Y

The post below has been deleted. Click to close.

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

259 posts

#6 h Mar 17, 2017, 7:47 PM • 2 Y

Y by Adventure10, Mango247

Can anyone solve this problem?

Z K Y

The post below has been deleted. Click to close.

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

bobthesmartypants

4337 posts

bobthesmartypants

#7 h Mar 23, 2017, 2:54 PM • 2 Y

Y by me9hanics, Adventure10

I've seen the expression $n+v_p(n!)$ once too many times for this expression to just be a coincidental result, especially in China TST problems... am I just crazy?

Z K Y

The post below has been deleted. Click to close.

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

64 posts

#8 h Mar 25, 2017, 2:05 PM • 1 Y

Y by Adventure10

i solved this like this:
step 1: first set a claim about n<=t and say you are gonna prove it for n=t+1 (i am talking about induction)
step 2: prove that if a1~a(t+1) isn't all same for mod p, it is smaller than n+vp(n)
step 3: so you get a1~a(t+1) is all same as (p-a) for mod p (0<=a<p) --> you get vp(f(x))=0 or else
step 4: let x=a+py --> you can set y to be s (mod p) where s is least most number (mod p) among (a(i)+a)/p
step 5: set algorithym for step 2~4 same to use it for y and (a(i)+a)/p

Z K Y

The post below has been deleted. Click to close.

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

113 posts

#9 h Apr 7, 2017, 2:56 AM • 1 Y

Y by Adventure10

How to guess the number n+vp(n!)??? Oh my god ??

Z K Y

The post below has been deleted. Click to close.

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

Pikachu05072001

20 posts

Pikachu05072001

#10 h Apr 7, 2017, 3:24 AM • 2 Y

Y by Adventure10, Mango247

Let ai =pi we get m >= n +vp(n!)

Z K Y

The post below has been deleted. Click to close.

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

Pikachu05072001

20 posts

Pikachu05072001

#11 h Apr 7, 2017, 4:51 AM • 4 Y

Y by dalarin01, kwanglee123456, levimpcbranco, Adventure10

My solution
Let ai =pi and chose k isnot divided by p
So k' is divided by p . $k'=py$
and $v_p(f(k)) = n+(y+1)(y+2).......(y+n) >= n+v_p(n!)$
=> $m >= n+v_p(n!)$
We will prove by induction
Lemma
Let $b_1 ; b_2 ; ................ ; b_n$ are n positive interger number
then there exist k such that
$v_p(b_1+k)(b_2+k).................(b_n+k) <= v_p(n!)$
Prove the lemma by induction
n = 1
suppose that 1<=k<=n-1 are true
suppose with n are false
take k=0
$v_p(b_1.b_2.............b_n)>=v_p(n!)$
suppose $b_{i1} ; b_{i2}.........................; b_{im}$ are divided by p
if m = n take k=1
if m < n
by induction
there exist k such that $v_p(b_{i1}+k) (b_{i2}+k).........................(b_{im}+k)<= v_p(m!)$
=> $m + v_p(m!)>v_p(n!)$
=> m> n/p
take k from 0 to p-1 => contraction
Suppose f(k) is divided by p
$(k+a_1)(k+a_2).................(k+a_n)$ is divide by p
suppose $a_{i1}+k ; a_{i2}+k ......... a_{im}+k$ is divided by p
Lett max $v_p(a_i+k)=t$
supose $a_{ji} = p^t.b_j$ i = 1 to q
chose k' = p^t.z+k such that max $v_p(z+b_j)=1$
if f(k) is not divided by p
$(k+a_1)(k+a_2).............(k+a_n)$ is not divided by p
take $a_{i1};a_{i2} ............a_{im}$ is the longest sequence are congruent mod p
so by induction we have QED
so take $a_i = b_i.p-q$
take k' = kp+q
use the lemma we have QED

This post has been edited 3 times. Last edited by Pikachu05072001, Nov 2, 2017, 4:56 PM

Z K Y

The post below has been deleted. Click to close.

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

776 posts

#12 h Apr 7, 2017, 4:56 AM • 1 Y

Y by Adventure10

Wonderful

Z K Y

The post below has been deleted. Click to close.

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

33 posts

#13 h Oct 24, 2017, 12:35 PM • 2 Y

Y by Adventure10, Mango247

Umm, sorry, but I can't understand when f(k) is divided by p. if we chose k' like that, then why it satisfy the condition of the problem?
I think the point of that case is Vp(f(k'))>Vp(f(k)). I proved Vp(f(k'))≤Vp(f(k))+m but I can't proof that only Vp(f(k'))≥Vp(f(k)).

Z K Y

The post below has been deleted. Click to close.

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

Pikachu05072001

20 posts

Pikachu05072001

#14 h Oct 27, 2017, 8:26 AM • 3 Y

Y by MathLife00, Adventure10, Mango247

@above
because $v_p(k'+a_i) >= v_p(k+a_i)$ => $v_p(f(k')) > v_p(f(k))$

Z K Y

The post below has been deleted. Click to close.

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

33 posts

#15 h Oct 27, 2017, 10:22 AM • 2 Y

Y by Adventure10, Mango247

Ohh, thanks.

Z K Y

The post below has been deleted. Click to close.

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

33 posts

#16 h Oct 30, 2017, 10:26 AM • 1 Y

Y by Adventure10

Pikachu05072001 wrote:

@above
because $v_p(k'+a_i) >= v_p(k+a_i)$ => $v_p(f(k')) > v_p(f(k))$

I think, you had been mistake. a_ji is not p^t.b_j but a_ji +k. If then, you may change k' = p^t.z +k.
Then, by lemma there's z such that Vp(f(k'))≤Vp(f(k))+v_p(m!). But, we don't know the lower bound because $ v_p(b_1+k)(b_2+k).................(b_n+k) is could 0. (k is z, in this case) So we can't solve with your ways.

I proved this case using the second case. If we suppose k' like that, our claim is change to second case with k=0. Because q<=n, the proof is complete. It's easy.

If I wrong?

This post has been edited 2 times. Last edited by MathLife00, Oct 30, 2017, 10:56 AM

Z K Y

The post below has been deleted. Click to close.

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

1593 posts

#17 h Mar 18, 2018, 10:54 AM • 6 Y

Y by BSWJY, Tawan, Aryan-23, sabkx, Adventure10, Mango247

Very nice problem. I add my solution.

The answer is $\boxed{n+\nu_p(n!)}$ . To show that $m\ge n+\nu_p(n!)$ is necessary (which is the important motivation), take
$f(x)=(x+p)(x+2p)...(x+np).$ and $k=1$ . It's easy to see that whenever $p$ divides $f(k')$ then $p\mid k'$ . Letting $k' = pr$ , we notices that
$f(k') = p^n(r+1)(r+2)...(r+n)\implies p^nn!\mid f(k')$ so $m\ge n+\nu_p(n!)$ as desired.

Now we show that $m=n+\nu_p(n!)$ works. We first prove the following lemma which is a special case of this problem.

Lemma : Let $n,a_1, a_2,...,a_n\in\mathbb{Z}^+$ then there exists a positive integer $x$ such that the quantity
$f(x)=(x+a_1)(x+a_2)...(x+a_n)$ is divisible by $p$ but not $p^{n+\nu_p(n!)+1}$ .

Proof : We claim that we can pick $x\pmod{p^i}$ so that $p^i$ divides at most $\left\lfloor\frac{n}{p^{i-1}}\right\rfloor$ by induction on $i$ . The base case $i=1$ is clear. (Note that we can even pick $x\equiv -a_1\pmod p$ .)

Suppose that we have picked $x\pmod{p^{i-1}}$ . Let $x+b_1, x+b_2,...,x+b_k$ be those which is divisible by $p^{i-1}$ where $k\le \left\lfloor\frac{n}{p^{i-2}}\right\rfloor$ . By pigeonhole, there exists residue class $y\pmod p$ which contains at most $\left\lfloor\frac{k}{p}\right\rfloor = \left\lfloor\frac{n}{p^{i-1}}\right\rfloor$ of numbers
$\frac{x+b_1}{p^{i-1}}, \frac{x+b_2}{p^{i-1}},...,\frac{x+b_k}{p^{i-1}}$ hence picking $x\pmod{p^i} = yp^{i-1}+x$ satisfies inductive condition. This process repeats until there are no terms divisible by $p^i$ so
$\nu_p(f(x)) \le n + \left\lfloor\frac{n}{p}\right\rfloor + \left\lfloor\frac{n}{p^2}\right\rfloor + ... = n+\nu_p(n!)$ hence we are done. $\blacksquare$

Back to the main problem. Fix any $k\in\mathbb{Z}^+$ and let $c_i = \nu_p(x+a_i)$ . WLOG $c_1\ge c_2\ge ...\ge c_n$ . By suitable translation we can assume that $a_1=0$ . Pick $k'=p^{c_1}r$ for suitable $r$ . We see that
$f(k') = p^{\nu_p(f(k))}\cdot r\left(p^{c_1-c_2}\cdot r + \frac{a_2}{p^{c_2}}\right)\left(p^{c_1-c_3}\cdot r + \frac{a_3}{p^{c_3}}\right)...\left(p^{c_1-c_n}\cdot r + \frac{a_n}{p^{c_n}}\right)$ Note that if $c_1>c_i$ for some $i$ , then $p^{c_j} \| a_j$ for any $j\ge i$ so the later $n-i+1$ brackets never divisible by $p$ . Thus we can ignore them and induct down on $n$ .

Otherwise, $c_1=c_2=...=c_n = c$ which implies
$f(k') = p^{\nu_p(f(k)) } \cdot r\left( r + \frac{a_2}{p^{c}}\right)\left( r + \frac{a_3}{p^{c}}\right)...\left( r + \frac{a_n}{p^{c}}\right)$ By lemma, we can pick $r$ so that $\nu_p$ of the right product is not exceed $n+\nu_p(n!)$ and greater than $0$ hence we are done.

This post has been edited 3 times. Last edited by MarkBcc168, Apr 28, 2021, 7:26 AM

Z K Y

The post below has been deleted. Click to close.

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

571 posts

#18 h Mar 18, 2018, 5:41 PM • 2 Y

Y by Adventure10, Mango247

Is there any $p$ -adic interpretation of this problem?

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a