# IMO problems

#### melese

##### Member
I will post several problems that I find interesting.

1. Prove that for any natural number $n$, the number $\displaystyle\binom{2n}{n}$ divides the least common multiple of the numbers $1,2,...,2n-1,2n$.

መለሰ

#### chisigma

##### Well-known member
I will post several problems that I find interesting.

1. Prove that for any natural number $n$, the number $\displaystyle\binom{2n}{n}$ divides the least common multiple of the numbers $1,2,...,2n-1,2n$.

መለሰ
By definition is...

$\displaystyle \binom{2 n}{n} = \frac{(2n)!}{(n!)^{2}}$ (1)

... and if You remember the formula connecting lcm and gcd...

$\displaystyle \text{lcm} (a_{1},a_{2},...,a_{k}) = \frac{a_{1} \cdot a_{2} ... a_{k}}{\text{gcd} (a_{1},a_{2},...,a_{k})}$ (2)

... You obtain...

$\displaystyle \text{lcm} (1, 2, ..., 2 n -1, 2 n) = \frac{(2n)!}{\text{gcd} (1, 2, ..., 2 n -1, 2 n)}$ (3)

Now comparing (1) and (3), because $\displaystyle \text{gcd} (1, 2, ..., 2 n -1, 2 n)$ divides $\displaystyle (n!)^{2}$, it follows that $\displaystyle \binom{2 n}{n}$ divides $\displaystyle \text{lcm} (1, 2, ..., 2 n -1, 2 n)$...

Kind regards

$\chi$ $\sigma$

#### caffeinemachine

##### Well-known member
MHB Math Scholar
By definition is...

$\displaystyle \binom{2 n}{n} = \frac{(2n)!}{(n!)^{2}}$ (1)

... and if You remember the formula connecting lcm and gcd...

$\displaystyle \text{lcm} (a_{1},a_{2},...,a_{k}) = \frac{a_{1} \cdot a_{2} ... a_{k}}{\text{gcd} (a_{1},a_{2},...,a_{k})}$ (2)

... You obtain...

$\displaystyle \text{lcm} (1, 2, ..., 2 n -1, 2 n) = \frac{(2n)!}{\text{gcd} (1, 2, ..., 2 n -1, 2 n)}$ (3)

Now comparing (1) and (3), because $\displaystyle \text{gcd} (1, 2, ..., 2 n -1, 2 n)$ divides $\displaystyle (n!)^{2}$, it follows that $\displaystyle \binom{2 n}{n}$ divides $\displaystyle \text{lcm} (1, 2, ..., 2 n -1, 2 n)$...

Kind regards

$\chi$ $\sigma$
Hello chisigma,

I think you have committed a mistake in (2) above.

Take for example $k=3, a_1=3, a_2=5, a_3=15$.

#### jakncoke

##### Active member
Hello chisigma,

I think you have committed a mistake in (2) above.

Take for example $k=3, a_1=3, a_2=5, a_3=15$.

yes Lcm(a,b,c) = Lcm(a,lcm(b,c))

the above formula that chi mentioned only works for 2 numbers at a time.
lcm(a,b) = $\frac{|ab|}{gcd(a,b)}$

#### caffeinemachine

##### Well-known member
MHB Math Scholar
I have tried my best to type my solution out here but it doesn't compile for reasons I am not aware of. I have uploaded a pdf file which contains my solution.

#### Attachments

• 129.2 KB Views: 6

#### melese

##### Member
I have tried my best to type my solution out here but it doesn't compile for reasons I am not aware of. I have uploaded a pdf file which contains my solution.
My version is essentially the same.

Let $\nu_p(m)$, be the largest exponent of a prime $p$ appearing in the prime-factorization of the positive integer $m$.

Then, $\displaystyle\nu(\binom{2n}{n})=\nu(\frac{(2n)!}{n!n!})=\nu((2n)!)-\nu(n!)-\nu(n!)=\nu((2n)!)-2\nu(n!)$.
Now, due to Legendre*,$\displaystyle\nu((2n)!)-2\nu(n!)=\sum_{i\geq1}\lfloor \frac{2n}{p^i}\rfloor-2\sum_{i\geq1}\lfloor \frac{n}{p^i}\rfloor=\sum_{i\geq1}(\lfloor \frac{2n}{p^i}\rfloor-2\lfloor\frac{n}{p^i}\rfloor)=\sum_{i=1}^{k}( \lfloor \frac{2n}{p^i}\rfloor-2\lfloor\frac{n}{p^i}\rfloor)\leq\sum_{i=1}^{k}1=k$, where $p^k\leq2n<p^{k+1}$. (I relied on claim1).

But $k$ is exactly the $\nu_p$ of $l=lcm(1,2,...,2n-1,2n)$. We've shown $\displaystyle\nu_p(l)\geq\nu(\binom{2n}{n})$

*The expresstion $\displaystyle \sum_{i\geq0}\lfloor\frac{m}{p^i}\rfloor$ counts the exponent of a prime $p$ that appearing in $m!$. (the terms eventually are all zero)

መለሰ

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Hello melese,

Was this an IMO Problem? If yes which year did it it appear in the IMO?

#### melese

##### Member
Hello melese,

Was this an IMO Problem? If yes which year did it it appear in the IMO?
This one was proposed by Bulgaria (it says BGR 1), in 1984. But it was one of the longlisted problems, so it wasn't at the contest itself.

I will from now on try to give more details of this nature.

መለሰ