Welcome to our community

Be a part of something great, join today!

IMO problems

melese

Member
Feb 24, 2012
27
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
Feb 13, 2012
1,704
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
Mar 10, 2012
834
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$.

Reply.
 

jakncoke

Active member
Jan 11, 2013
68
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$.

Reply.
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
Mar 10, 2012
834
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

melese

Member
Feb 24, 2012
27
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
Mar 10, 2012
834
Hello melese,

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

melese

Member
Feb 24, 2012
27
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.

መለሰ