Local Mathematical Competitions

In the sequel we will consider $P$ being made of the primes $1<p_1<p_2<\cdots <p_k$, with $k=|P|\ge 1$.

a. By the Chinese Remainder Theorem there will exist some $a\in \mathbb{N}$ such that $a\equiv -i(\mathrm{mod}{p}_i)$, hence $p_i\mid a+i$. Then the set $\{a+i;i=1,2,\dots ,k\}$ of $k$ consecutive integers has the desired property, hence $m(P)\ge k$. When $\min P>|P|$, within any set of $|P|+1$ consecutive integers at most one is divisible by any $p\in P$, hence by the Pigeonhole Principle there will be one not divisible by any of the primes in $P$. On the other hand, when $\min P\le |P|$, we will make again use of the Chinese Remainder Theorem, so there will exist some $a\in \mathbb{N}$ such that $a\equiv -r_i(\mathrm{mod}{p}_i)$, hence $p_i\mid a+r_i$, where $\{r_i;i=1,2,\dots ,k\}=\{1,2,\dots ,k\}$ and the extra requirement that $r_1=k+1-p_1$. It follows that the set $\{a+i;i=1,2,\dots ,k,k+1\}$ of $k+1$ consecutive integers has the desired property, hence $m(P)\ge k+1>|P|$.

b. Now, let a set made of $m$ consecutive integers have the desired property. For any $\varnothing \ne I\subseteq \{1,2,\dots ,k\}$, the number $N(I)$ of its elements which are divisible by ${\prod }_{i\in I}{p}_i$ will satisfy the inequality $$\frac{m}{{\prod }_{i\in I}{p}_i}-1<\lfloor \frac{m}{{\prod }_{i\in I}{p}_i}\rfloor \le N(I)\le \lceil \frac{m}{{\prod }_{i\in I}{p}_i}\rceil <\frac{m}{{\prod }_{i\in I}{p}_i}+1.$$ Then, by the Principle of Inclusion/Exclusion, one has $$m=\sum _{i=1}^k(-1{)}^{i+1}\sum _{|I|=i}N(I)<\sum _{i=1}^k(\genfrac{}{}{0ex}{}{k}{i})+m\sum _{i=1}^k(-1{)}^{i+1}\sum _{|I|=i}\frac{1}{{\prod }_{i\in I}{p}_i}.$$ The first term is clearly equal to $2^k-1$, while the second is equal to $$m\left(1-\prod _{i=1}^k\left(1-\frac{1}{p_i}\right)\right)\le m\left(1-\prod _{i=1}^k\left(1-\frac{1}{i+1}\right)\right)=m-\frac{m}{k+1},$$ therefore $m<(k+1)(2^k-1)$, and so will be $m(P)$.

---

Alternative solution.

Alternative Solution (ii). (F. Chindea)

Not only an elegant alternative approach, but vastly improving on the required bound. Start by proving the following

LEMMA. If the integer arithmetic sequences $\{m{n}_j{\}}_{m\in \mathbb{Z}}$, $1\le j\le 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 ${\omega }_j=e^{n_j}$ be a primitive root of unity. Then $n_j\mid m$ if and only if ${\omega }_j^m=1$, hence $m$ is divisible by at least one $n_j$ if and only if $0={\prod }_{j=1}^k(1-{\omega }_j^m)={\sum }_{\varnothing \subseteq S\subseteq [k]}(-1{)}^{|S|}{e}^{2m\pi i{\sum }_{j\in S}\frac{1}{n_j}}$. Denote ${\alpha }_S=(-1{)}^{|S|}$, $z_S=e^{2\pi i{\sum }_{j\in S}\frac{1}{n_j}}$, $u_m={\sum }_{\varnothing \subseteq S\subseteq [k]}{\alpha }_S{z}_S^m$.

Consider the polynomial $f(x)={\prod }_{\varnothing \subseteq S\subseteq [k]}(x-z_S)={\sum }_{j=0}^{2^k}{c}_j{x}^j$, of degree $\mathrm{deg}f=2^k$, and with $c_{2^k}=1$, $|c_0|={\prod }_{\varnothing \subseteq S\subseteq [k]}|z_S|=1$. Then ${\alpha }_S{z}_S^{b}f(z_S)=0$ for any integer $b$, hence $$0=\sum _{\varnothing \subseteq S\subseteq [k]}{\alpha }_S{z}_S^{b}f(z_S)=\sum _{j=0}^{2^k}{c}_j\sum _{\varnothing \subseteq S\subseteq [k]}{\alpha }_S{z}_S^{b+j}=\sum _{j=0}^{2^k}{c}_j{u}_{b+j}.$$ Assume the $2^k$ consecutive integers $a+1,\dots ,a+2^k$ are covered, so, according with the above, $u_{a+1}=\cdots =u_{a+2^k}=0$. Since $c_0\ne 0$ and $c_{2^k}\ne 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). $\square$

Now, in our case, if we assume $m(P)\ge 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|}$.