We use marriage theorem, choose $t$ of our numbers and suppose their product only has $t-1$ primes, then we can easily see some of them divides the product of the others, but this implies some of them divides a number smaller than $n!$, however they are all greater than $n^n$

I don't understand that. Why a number dividing the product of t-1 others should divide something smaller than n! ? Obviously we can take any number, however large, and find anothers with product divisible by it... By the way, I don't know any solution of this problem really using marriage lemma (though the temptation is strong; in fact, the only participant of the olympiad who solved the problem managed to insert this lemma into his solution. It was funny to outline a large part of his solution which could be deleted with no harm at all.) So, I'd be really glad to hear a solution using the lemma.

Here is my solution. First the numbers m+i which have at least n prime divisors are no problem because we can always take one prime divisor which is not already taken. Now for the other numbers of the form m+i which have n-1 or smaller number of prime divisors. Let $m+i=p_{1}^{a_{1}}.p_{2}^{a_{2}}...p_{k}^{a_{k}}$ where $k\leq n-1$. Now for this nubmer choose $p_{i}$ such that $p_{i}^{a_{i}}$ is maximal. The claim is that this primes are all different. Suppose p is chosen for m+i and m+j. And let $p^{a}$ and $p^{b}$ divides m+i and m+j respectively. WLOG $a\geq b$. So $p^{b}$ divides $m+j-(m+i)\leq n-1$. But since p is chosen that way we have $p^{b}\geq \sqrt[n-1]{m+j}\geq n$ This contradiction proves the statement.

By the way the general statement (with no $m>n^{n-1}$) is Grimm hypothesis and i think it is still open question. If you are interesting in this kind of questions look here: http://www.math.spbu.ru/user/aih/papers/grimm.zip

My solution(I holp it is correct): Let $q_{1},...q_{k}$ be all the primes not greater than $n$ then Let $q_{i}^{\alpha_{i}}\parallel LCM[1,2,...,n]$ Define $f: \{m+1,...m+n\}: \to P$ as the following: if $m+l=\prod_{i=1}^{k}{q_{i}^{\beta_{i}}}*q,q_{i}\not |q$ Then 1) $f(l)=$one of the prime fractor of $q$,when $q>1$ 2) $f(l)=q_{t}$ when $q=1$ and $\beta_{t}>\alpha_{t}$(for some $t$) and it is easy to check that if $\beta_{t}\leq \alpha_{t},\forall t$ and $q=1$,then $m+l\leq n^{k}\leq n^{n-1}$ (becuase$q_{t}^{\alpha_{t}}\leq n$) so there are only two case 1),2) and we easily check that $f(1),...f(n)$ are distinct( if $f(i)=f(j)=q_{u}$ then $q_{u}^{\alpha_{u}+1}|(m+i)-(m+j)$ but $q_{u}^{\alpha_{u}+1}>n$ contradition.) Edit: I don't know why if no$m>n^{n}-1$ it is still true? if $m+1=2,m+3=4$ then there is no two distinct prime which divide $m+1$ and $m+4$?I

Hawk Tiger, for the general statement you must have all m+1,m+2..m+n be composite and here m+1=2 is prme, so this is not counterexample for Grim's hypothesis.

Baronov wrote: Hawk Tiger, for the general statement you must have all m+1,m+2..m+n be composite and here m+1=2 is prme, so this is not counterexample for Grim's hypothesis. Thanks.And I think my proof do not need all the mumber is not a prime.

Baronov wrote: Here is my solution. First the numbers m+i which have at least n prime divisors are no problem because we can always take one prime divisor which is not already taken. Now for the other numbers of the form m+i which have n-1 or smaller number of prime divisors. Let $ m + i = p_{1}^{a_{1}}.p_{2}^{a_{2}}...p_{k}^{a_{k}}$ where $ k\leq n - 1$. Now for this nubmer choose $ p_{i}$ such that $ p_{i}^{a_{i}}$ is maximal. The claim is that this primes are all different. Suppose p is chosen for m+i and m+j. And let $ p^{a}$ and $ p^{b}$ divides m+i and m+j respectively. WLOG $ a\geq b$. So $ p^{b}$ divides $ m + j - (m + i)\leq n - 1$. But since p is chosen that way we have $ p^{b}\geq \sqrt [n - 1]{m + j}\geq n$ This contradiction proves the statement. By the same method we can prove that the statement is true for all $ m\geq (n-1)!$

ciprian wrote: It is known that $m$ and $n$ are positive integers, $m > n^{n-1}$, and all the numbers $m+1, m+2, \dots, m+n$ are composite. Prove that there exist such different primes $p_1,p_2, \dots, p_n$ that $p_k$ divides $m+k$ for $k = 1,2, \dots, n$. Proposed by C. A. Grimm Recall that in the expression $p^a$, $a$ is called the exponent, $p$ the base and $p^a$ is called a power. With this terminology, we proceed as follows: Define $f(\ell)$ as the largest prime power dividing $\ell$, i.e., if $$\ell=q_1^{\alpha_1}\dots q_s^{\alpha_s}$$then $$f(\ell)=\operatorname{max}\left(q_1^{\alpha_1},\dots, q_s^{\alpha_s}\right)$$Set $p_i=f(m+i)$ for $1 \le i \le n$. If all the bases are different, we are done. Otherwise, there exists an index $j$ such that $p_j=f(m+a)=f(m+b)$. If at least one of $m+a$ or $m+b$ has more than $(n-1)$ distinct prime divisors, then we may replace $p_j$ for that number by some prime number other than those in $\{p_1,\dots,p_n\}$. If neither does, then $$n<\sqrt[n-1]{m}<\min \left(\sqrt[n-1]{m+a},\sqrt[n-1]{m+b}\right)<p_j^{\min(v_{p_j}(m+a),v_{p_j}(m+b))} \mid |(m+a)-(m+b)|<n$$and we get the desired contradiction!