If $k$ and $n$ are positive integers , and $k \leq n$ , let $M(n,k)$ denote the least common multiple of the numbers $n , n-1 , \ldots , n-k+1$.Let $f(n)$ be the largest positive integer $ k \leq n$ such that $M(n,1)<M(n,2)<\ldots <M(n,k)$ . Prove that : (a) $f(n)<3\sqrt{n}$ for all positive integers $n$ . (b) If $N$ is a positive integer , then $f(n) > N$ for all but finitely many positive integers $n$.
Problem
Source: Romania TST 2015 Day 3 Problem 3
Tags: least common multiple, function, Romanian TST, number theory, RIP
05.06.2015 08:49
It may even be proven that (a') $f(n) < 2\sqrt{n}$ for all positive integers $n$.
05.06.2015 12:13
I suppose in b) it should be $N$ instead of $M$. a)Let $n=m^2+d$.Now,$M(n,k)>M(n,k-1)$ when there is a number $p^a$ that divides $n-k+1$ but doesn' t divide any of the numbers $n-k+2,...n$.Now,it is logic to pick a number of the form $ab$ where $a$ and $b$ are relatively prime and close,so pick $n-k+1=m(m-1)$.Now,$M(n,k-1)$ is divisble with both $m$ and $m-1$ cause there are $m^2$ and $(m-1)(m+1)$.Now,$k=d+m<=3m<=3\sqrt{n}$. b)Let $s$ be the number of primes in the interval $1,2,...N$ and we prove this is true for all $n>N^s+N$.Suppose opposite,let $M(n,k)=M(n,k-1)$ where $k<=N$.Now,if we pick any $p^a$ that exactly divides $n-k+1$,we have that among numbers $n-k+2,...n$ there is a number divisble with $p^a$,which means $p^a<N$.Now,we have at most $s$ primes less than $N$,so there must exist a $p^a$ which is at least $N$,which is a contradiction.
11.05.2016 18:38
a) Suppose $f(n)\ge 3\sqrt{n}$. Note that $n-3\left \lfloor \sqrt{n} \right \rfloor+1<\left \lfloor \sqrt{n} \right \rfloor \left (\left \lfloor \sqrt{n} \right \rfloor-1 \right ) <n$ and $$ \left \lfloor \sqrt{n} \right \rfloor \left (\left \lfloor \sqrt{n} \right \rfloor-1 \right ) <(\left \lfloor \sqrt{n} \right \rfloor+1)(\left \lfloor \sqrt{n} \right \rfloor-1)<n,\ \left \lfloor \sqrt{n} \right \rfloor \left (\left \lfloor \sqrt{n} \right \rfloor-1 \right ) < \left ( \left \lfloor \sqrt{n} \right \rfloor \right )^2\le n$$Denote $\left \lfloor \sqrt{n} \right \rfloor \left (\left \lfloor \sqrt{n} \right \rfloor-1 \right ) =a$. We have that $M(n,n-a)<M(n,n-a+1)$ because $n-a+1<3\sqrt{n}$. Note that $M(n,n-a)=[n,n-1,...,a+1]$, so it contains both $(\left \lfloor \sqrt{n} \right \rfloor+1)(\left \lfloor \sqrt{n} \right \rfloor-1)$ and $ \left ( \left \lfloor \sqrt{n} \right \rfloor \right )^2$, so $a$ divides $M(n,n-a)$. But then we would have$M(n,n-a)=[M(n,n-a),a]=M(n,n-a+1)>M(n,n-a)$, contradiction. b) I claim that $f(n)>N$ for any $n>N!+N$. Note that if $M(n,k)=M(n,k+1)$, then $n-k$ divides the lcm of $n,n-1,...,n-k+1$ which divides $n\cdot (n-1)...\cdot (n-k+1)$, so $n-k$ divides $k!$. But this can't be the case for $k\le N$ as $n-k\ge n-N>N!\ge k!$, so $f(n)>N$.