Romanian Masters in mathematics 2010 Day 1 Problem 1

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

Romanian Masters in mathematics 2010 Day 1 Problem 1

G H J

Reveal topic tags

modular arithmetic

combinatorics proposed

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.

3130 posts

#1 h Apr 25, 2010, 8:41 AM • 5 Y

Y by anantmudgal09, Davi-8191, Adventure10, Mango247, kiyoras_2001

For a finite non empty set of primes $P$ , let $m(P)$ denote the largest possible number of consecutive positive integers, each of which is divisible by at least one member of $P$ .

(i) Show that $|P|\le m(P)$ , with equality if and only if $\min(P)>|P|$ .

(ii) Show that $m(P)<(|P|+1)(2^{|P|}-1)$ .

(The number $|P|$ is the size of set $P$ )

Dan Schwarz, Romania

Z K Y

The post below has been deleted. Click to close.

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

204 posts

lasha

#2 h May 9, 2010, 8:52 PM • 1 Y

Y by Adventure10

I just managed to solve part a). Assume we have primes $p_1, p_2, ... , p_n$ and $n$ consecutive integers $x+1,x+2,...,x+n$ such that each of this $n$ numbers has a divisor among primes $p_i, 1\leq{i}\leq{n}$ . Consider new (n+1)-tuples: ${x+Np_1p_2...p_n+i|1\leq{i}\leq{n}}$ , where $N$ is any positive integer. Easy to prove that we can find such $N$ that $x+Np_1p_2...p_n$ is divisible by $p_{n+1}$ , for any new prime in the set, as the numbers $Np_1p_2...p_n$ , where $1\leq{N}\leq{p_{n+1}}$ , give any remainder exactly once modulo $p_{n+1}$ . Clearly, we have a basis for this induction conjecture. Hence, we have the way to construct $n$ consecutive integers, satisfying the given conditions. It immediately follow that $m(p)\geq{|P|}$ , q.e.d.
P.S. Sorry, I don't have enough time to post the proof of the second part of question a). I will post it tomorrow if no one else does

Z K Y

The post below has been deleted. Click to close.

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

29 posts

tianc

#3 h May 10, 2010, 3:55 AM • 2 Y

Y by Adventure10, Mango247

Could you tell me the problem of yesterday?Thank you.

Z K Y

The post below has been deleted. Click to close.

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

207 posts

#4 h May 10, 2010, 6:27 PM • 3 Y

Y by miaoxiaodai, Adventure10, math90

This is already solved on the forum (see the discussion on the contest's topic of this year). One can prove that $m(P) < 2^{|P|}$ (this is the solution to be found at the link above):

Solution for b) wrote:

Start with

Lemma.
If the integer arithmetic sequences $\{ mn_j \}_{m \in \mathbb{Z}}$ , $1 \leq j \leq k$ , are such that they cover $2^k$ consecutive integers, then they cover $\mathbb{Z}$ .

(Particular case of a Crittenden & Vanden Eynden Theorem)

Proof.
Let $\displaystyle \omega_j = \textrm{e}^{\frac {2\pi \textrm{i}} {n_j}}$ be a primitive root of unity. Then $n_j \mid m$ if and only if $\displaystyle \omega_j^m = 1$ , hence $m$ is divisible by at least one $n_j$ if and only if
$\displaystyle 0 = \prod_{j = 1}^k(1 - \omega_j^m) = \sum_{\emptyset \subseteq S \subseteq [k]} ( - 1)^{|S|}\textrm{e}^{2m\pi\textrm{i}\sum_{j \in S} \frac {1} {n_j}}$ . Denote $\alpha_S = ( - 1)^{|S|}$ , $z_S = \textrm{e}^{2\pi\textrm{i}\sum_{j \in S} \frac {1} {n_j}}$ , $\displaystyle u_m = \sum_{\emptyset \subseteq S \subseteq [k]} \alpha_Sz_S^m$ .

Consider now the polynomial $\displaystyle f(x) = \prod_{\emptyset \subseteq S \subseteq [k]} (x - z_S) = \sum_{j = 0}^{2^k} c_jx^j$ , of degree $\deg f = 2^k$ , and with $c_{2^k} = 1$ , $\displaystyle |c_0| = \prod_{\emptyset \subseteq S \subseteq [k]} |z_S| = 1$ . Then $\alpha_Sz_S^bf(z_S) = 0$ for any integer $b$ , hence
$\displaystyle 0 = \sum_{\emptyset \subseteq S \subseteq [k]} \alpha_Sz_S^bf(z_S) = \sum_{j = 0}^{2^k} c_j \sum_{\emptyset \subseteq S \subseteq [k]} \alpha_Sz_S^{b + j} = \sum_{j = 0}^{2^k} c_ju_{b + j}.$
Assume the $2^k$ consecutive integers $a + 1, \ldots, a + 2^k$ are covered, so, according with the above, $u_{a + 1} = \cdots = u_{a + 2^k} = 0$ . Since $c_0 \neq 0$ and $c_{2^k} \neq 0$ , by simple induction one gets $u_b = 0$ for any integer $b$ (a linear recurrence relation of order $2^k$ containing $2^k$ consecutive null terms generates an all-null sequence). $\blacksquare$

Now, in our case, if we assume $m(P) \geq 2^{|P|}$ , then the $|P|$ arithmetic sequences given by $\{ mp \}_{m \in \mathbb{Z}}$ , $p \in P$ , will cover $2^k$ consecutive integers, hence they will cover $\mathbb{Z}$ . But clearly a large enough prime $q$ is not divisible by any $p \in P$ , so this is absurd, therefore $m(P) < 2^{|P|}$ .

Bibliography

Richard K. Guy, Unsolved Problems in Number Theory E23
Zhi-Wei Sun, Arithmetic Properties of Periodic Maps (with an extensive bibliography of its own).

Z K Y

The post below has been deleted. Click to close.

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

280 posts

#5 h May 10, 2010, 7:35 PM • 2 Y

Y by Adventure10, Mango247

I'll also try a.)

Let $s = |P|$ . We proceed by constructing $s$ consecutive integers which are each divisible by a prime in $P$ . Indeed, the following system has a solution, according to Chinese Remainder Theorem:
$x+1 \equiv 0 \pmod {p_1}$
$x+2 \equiv 0 \pmod {p_2}$
...
$x+s \equiv 0 \pmod {p_s}$

Second part:
Suppose we have $s < \min(P)$ and that we have $s+1$ consecutive integers all divisible by some $p_i$ : $x, x+1, x+2, ... , x+s$ . Let $p_1 = \min(P)$ .

For each $p_i$ , it can only divide at most one of the above-mentioned integers. For if it divides $x+a$ and $x+b$ then it also divides $|a-b| \leq s < p_1$ , a contradiction (since $p_1$ is the smallest prime in $P$ ).
So $m(P) \leq s$ . But it's been shown that $m(P) \geq s$ , so $m(P) = s$ .

Now suppose we have $s \geq \min(P)$ . We will show $s+1$ consecutive integers such that each is divisible by a prime in $P$ , which then establishes $m(P) > s$ .
Let $k = \min(P)$ .
Again, we set up a system of equations as described above, but we choose the ordering of $p_i$ s such that $p_k = k$ . The rest can be arbitrary ordering. This is always possible if $s \geq k$ .
According to CRT, there is a solution of $s$ consecutive integers that satisfy the above system of equations. But then we also have $x = x+k - k$ divisible by $p_k = k$ . So together with $x$ , they form $s+1$ consecutive integers.

Z K Y

The post below has been deleted. Click to close.

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

19 posts

#6 h Feb 6, 2011, 1:18 AM • 3 Y

Y by iarnab_kundu, Adventure10, Mango247

Letter $b$ :

Let $M+1, M+2,...,M+m$ be consecutive integers, each multiple of some $p_i$ , $n=|P|$ , $Q = p_1p_2...p_n$ . The number of multiples of some $p_i$ between $M+1$ and $M+m$ is $m$ , since they are all multiples, but by the PIE it is also:

$\displaystyle\sum_{d|Q, d>1}\left\lfloor\dfrac{M+m}{d}\right\rfloor(-\mu(d)) - \displaystyle\sum_{d|Q, d>1}\left\lfloor\dfrac{M}{d}\right\rfloor(-\mu(d))$

For every $k$ , we have $\dfrac{m}{k} - 1 < \left\lfloor\dfrac{M+m}{k}\right\rfloor - \left\lfloor\dfrac{M}{k}\right\rfloor < \dfrac{m}{k} + 1$ , so we have:

$m=\displaystyle\sum_{d|Q, d>1}\mu(d)\left(\left\lfloor\dfrac{M}{d}\right\rfloor - \left\lfloor\dfrac{M+m}{d}\right\rfloor\right) =\displaystyle\sum_{d|Q, d>1, \mu(d)=1}\left(\left\lfloor\dfrac{M}{d}\right\rfloor - \left\lfloor\dfrac{M+m}{d}\right\rfloor\right) + \displaystyle\sum_{d|Q, d>1, \mu(d)=-1}\left(\left\lfloor\dfrac{M+m}{d}\right\rfloor - \left\lfloor\dfrac{M}{d}\right\rfloor\right) < \displaystyle\sum_{d|Q, d>1, \mu(d)=1}\left(1-\dfrac{m}{d}\right) + \displaystyle\sum_{d|Q, d>1, \mu(d)=-1}\left(1+\dfrac{m}{d}\right) = \left(\displaystyle\sum_{d|Q, d>1}1\right) - m\left(\displaystyle\sum_{d|Q, d>1}\dfrac{\mu(d)}{d}\right) = 2^n-1 - m\left[\left(\displaystyle\prod_{i}1-\dfrac{1}{p_i}\right) - 1\right]$

$\Longrightarrow m < 2^n-1+m-m\left(\displaystyle\prod_{i}1-\dfrac{1}{p_i}\right) \Longleftrightarrow m < \dfrac{2^n - 1}{\left(\displaystyle\prod_{i}1-\dfrac{1}{p_i}\right)}$

So we need $\dfrac{1}{\left(\displaystyle\prod_{i}1-\dfrac{1}{p_i}\right)} \le n+1 \Longleftrightarrow \dfrac{1}{n+1} \le \left(\displaystyle\prod_{i}1-\dfrac{1}{p_i}\right)$

Now $f(x) = 1 - \dfrac{1}{x}$ is increasing, and assuming $p_1 < p_2 < ... < p_n$ , we have $p_i \ge i+1$ , so $\left(\displaystyle\prod_{i}1-\dfrac{1}{p_i}\right) \ge \left(\displaystyle\prod_{i}1-\dfrac{1}{i+1}\right) = \left(\displaystyle\prod_{i}\dfrac{i}{i+1}\right) = \dfrac{1}{2}\dfrac{2}{3}...\dfrac{n}{n+1} = \dfrac{1}{n+1}$ , and we're done.

Z K Y

The post below has been deleted. Click to close.

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

1980 posts

#7 h Sep 22, 2015, 6:11 AM • 2 Y

Y by Adventure10, Mango247

Hint:
a.) Use CRT
b.) Use Inclusion/exclusion principle.

Z K Y

The post below has been deleted. Click to close.

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

3070 posts

#8 h Nov 8, 2016, 5:59 AM • 8 Y

Y by tenplusten, huricane, AlastorMoody, hellomath010118, Kobayashi, Adventure10, Mango247, signifance

$\textbf{Part (i)}:$
Suppose the elements of $P$ are $p_1,p_2,\cdots ,p_{|P|}$ . To show $|P|<m(P)$ , we need to find $|P|$ consecutive numbers each of which is divisible by some $p_i$ . But this is easy: we can try to solve the system: $\begin{align*} x+1&\equiv 0\pmod{p_1}\\ x+2&\equiv 0\pmod{p_2}\\ &\vdots\\ x+|P|&\equiv 0\pmod{p_{|P|}}\end{align*}$ But this has a solution because of ~~Cathode Ray Tube~~ Chinese Remainder Theorem.

Now for the equality case. For the if part, note that if $\min (P)>|P|$ , and equality in $|P|\le m(P)$ does not hold, then that means there is a set of $|P|+1$ consecutive numbers each divisible by some $p_i$ . Since there are more numbers than there are primes, Pigeonhole principle says some $p_i$ must divide two of those consecutive numbers, and hence also their difference, which cannot exceed $|P|$ . This forces $p_i\le |P|\implies \min (P)\le p_i\le |P|$ , contradicting the hypothesis.

It remains to prove the converse, and we would be done with part(i). That is, we need to show $\min(P)>|P|$ implies equality. We'll show the contrapositive. Suppose we have $\min(P)\le |P|$ instead. Say WLOG $p_1\le |P|$ . We again set up a system of equations:
$\begin{align*} x+1&\equiv 0\pmod{p_1}\\ x+2&\equiv 0\pmod{p_2}\\ &\vdots\\ x+p_1&\equiv 0\pmod{p_{p_1}}\\ x+p_1+2&\equiv 0\pmod{p_{p_i+1}}\\ &\vdots\\ x+|P|+1&\equiv 0\pmod{p_{|P|}}\end{align*}$ This system consists of all equations of the form $x+i\equiv 0\pmod{p_i}$ for $i\in\{1,\cdots ,p_1\}$ , then skips $x+p_1+1$ altogether, and continues as $x+i\equiv 0\pmod{p_{i-1}}$ for $i\in\{p_1+1,\cdots ,|P|\}$ . This has a solution $x$ by CRT again. So the numbers $x+1,x+2,\cdots x+p_1,x+p_1+2,\cdots x+|P|$ are all forced to divisible by some $p_i$ , and the number $x+p_1+1$ is automatically divisible by $p_1$ because $x+1\equiv 0\pmod{p_1}$ . Thus we ended up with $|P|+1$ consecutive numbers with the desired properties, which shows $m(P)\ge |P|+1$ , and so the equality in $|P|\le m(P)$ cannot hold. This settles part (i) . $\blacksquare$

$\textbf{Part (ii)}$

First of all, a notation thing: for a set $S$ , and a positive integer $k$ , $\left|\Large\substack{S\\ \sim \\ k}\right|$ is the number of elements in $S$ divisible by $k$ . Note that if $S$ is a set of consecutive integers, then $\left|\Large\substack{S\\ \sim \\ k}\right|=\left\lfloor\frac{|S|}{k}\right\rfloor\text{ or }\left\lfloor\frac{|S|}{k}\right\rfloor+1$ , depending on $S$ . This in particular gives us the bounds $\left|\Large\substack{S\\ \sim \\ k}\right|\le \frac{|S|}{k}+1$ and $\left|\Large\substack{S\\ \sim \\ k}\right|\ge \frac{|S|}{k}-1$ ; these will be of use to us later on.

Now, let $|P|=m,m(P)=N,$ and $S=$ a set of $N$ consecutive integers each divisible by some element of $P$ . Also, as before, say the elements of $P$ are $p_1,p_2,\cdots ,p_m$ . Now if $\Large\smiley$ denotes the set of integers within $S$ that are divisible by none of the $p_i$ 's, we must have $\left| \Large\smiley\right|=0$ . But we can compute $\left| \Large\smiley\right|$ in another way: the Principle of Inclusion and Exclusion, which yields:
$\begin{align*}0=\left| \Large\smiley\right| & =|S|-\sum_{1\le i\le m}\left|\Large\substack{S\\ \sim \\ {p_i}}\right|+\sum_{1\le i<j\le m}\left|\Large\substack{S\\ \sim \\ {p_ip_j}}\right|-\sum_{1\le i<j<k\le m}\left|\Large\substack{S\\ \sim \\ {p_ip_jp_k}}\right|+\cdots\\ &\ge N-\sum_{1\le i\le m}\left(\frac{N}{p_i}+1\right)+\sum_{1\le i<j\le m}\left(\frac{N}{p_ip_j}-1\right)-\sum_{1\le i<j<k\le m}\left(\frac{N}{p_ip_jp_k}+1\right)+\cdots\\ &= N-\sum_{1\le i\le m}\frac{N}{p_i}+\sum_{1\le i<j\le m}\frac{N}{p_ip_j}-\sum_{1\le i<j<k\le m}\frac{N}{p_ip_jp_k}+\cdots\\ &\quad\quad-\left( \binom{m}{1}+\binom{m}{2}+\binom{m}{3}+\cdots\right)\\ &=N\prod_{i=1}^{m} \left(1-\frac{1}{p_i}\right)-(2^m-1)\\ \implies m(P)&=N\le \frac{2^m-1}{\prod_{i=1}^{m} \left(1-\frac{1}{p_i}\right)}.\end{align*}$ It remains to show $\frac{1}{\prod_{i=1}^{m} \left(1-\frac{1}{p_i}\right)}<|P|+1=m+1\iff \prod_{i=1}^m \frac{p_i}{p_i-1}<m+1$ , which follows from easy induction. Thus, we are (finally!) done. $\blacksquare$

This post has been edited 1 time. Last edited by Ankoganit, Nov 8, 2016, 6:03 AM

Z K Y

The post below has been deleted. Click to close.

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

1963 posts

ABCDE

#9 h Feb 14, 2018, 2:05 AM • 3 Y

Y by JG666, Adventure10, Mango247

(i) We can easily construct $|P|$ consecutive integers, each one of which is divisible by an element of $P$ , by the Chinese Remainder Theorem. In the case of $\min(P)>|P|$ , this is the best we can do, as among any $|P|$ consecutive integers at most one of them is divisible by $p$ for every $p\in P$ . Conversely, if $\min(P)\le|P|$ we can cover two integers and exhibit $|P|+1$ consecutive integers.

(ii) We will show that among any $N=(|P|+1)(2^{|P|}-1)$ consecutive integers there will be at least one relatively prime to $p_1p_2\cdots p_{|P|}$ , the product of the elements of $P$ . Indeed, note that the number of such integers is at most $N+\sum_{S\subset\{1,2,\ldots,|P|\}}(-1)^{|S|}\left\lfloor\frac{N}{\prod_{i\in S}p_i}\right\rceil$ , where the expression is a floor if $S$ has an even number of elements and a ceiling otherwise. This count is by the Principle of Inclusion and Exclusion. Bounded from below, we may get rid of the floors and ceilings at a cost of $1$ for each floor/ceiling, resulting in the number of relatively prime integers being strictly more than $N\prod\frac{p_i-1}{p_i}-(2^{|P|}-1)$ . Now note that $\prod\frac{p_i-1}{p_i}>\frac12\cdot\frac23\cdots\frac{|P|}{|P|+1}=\frac1{|P|+1}$ , from which we conclude that there are more than $\frac{N}{|P|+1}-(2^{|P|}-1)=0$ numbers not divisible by any element of $P$ , as desired.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a