Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1967 IMO Problems/Problem 3"

m
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
 +
For any <math>m, n</math>, <math>c_m - c_n = m(m+1) - n(n+1) = m^2 + m - n^2 - n = (m+n)(m-n) + m - n = (m+n+1)(m-n)</math>.
 +
 +
We can therefore write the product in the problem as follows:
 +
 +
<cmath>(c_{m+1}-c_k)(c_{m+2}-c_k)\cdots (c_{m+n}-c_k)</cmath>
 +
<cmath> = (\prod_{a = 1}^n m+a+k+1)(\prod{a = 1}^n m+a-k).</cmath>
 +
 +
But, the product of any <math>n</math> consecutive integers is divisible by <math>n!</math>. We can prove this as follows:
 +
 +
<cmath>(t-n+1)(t-n+2) \cdots (t) = \frac{(t+n)!}{t!} = n! \frac{(t+n)!}{t!n!} = n! {t+n}\choose{t}.</cmath>
 +
 +
Therefore, <math>(\prod_{a = 1}^n m+a-k)</math> is divisible by <math>n!</math>, and <math>(m+k+1)(\prod_{a = 1}^n m+a+k+1)</math> is divisible by <math>(n+1)!</math>. However, we are told that <math>m+k+1</math> is prime and therefore it is not divisible by any of the numbers <math>1</math> through <math>n+1</math>. Therefore, <math>(\prod_{a = 1}^n m+a+k+1)</math> is divisible by <math>(n+1)!</math>.
 +
 +
Finally, it is clear that <math>(c_{m+1}-c_k)(c_{m+2}-c_k)\cdots (c_{m+n}-c_k)</math> is divisible by <math>n!(n+1)! = (1 \cdot 2)(2 \cdot 3)(3 \cdot 4) \cdots (n \cdot (n+1)) = c_1c_2\cdots c_n</math>. <math>\square</math>
 +
 +
~mathboy100
 +
 +
==Solution 2==
 
We have that <math>c_1c_2c_3...c_n=n!(n+1)!</math>
 
We have that <math>c_1c_2c_3...c_n=n!(n+1)!</math>
  

Revision as of 22:22, 12 December 2022

Problem

Let $k, m, n$ be natural numbers such that $m+k+1$ is a prime greater than $n+1.$ Let $c_s=s(s+1).$ Prove that the product \[(c_{m+1}-c_k)(c_{m+2}-c_k)\cdots (c_{m+n}-c_k)\] is divisible by the product $c_1c_2\cdots c_n$.

Solution

For any $m, n$, $c_m - c_n = m(m+1) - n(n+1) = m^2 + m - n^2 - n = (m+n)(m-n) + m - n = (m+n+1)(m-n)$.

We can therefore write the product in the problem as follows:

\[(c_{m+1}-c_k)(c_{m+2}-c_k)\cdots (c_{m+n}-c_k)\] \[= (\prod_{a = 1}^n m+a+k+1)(\prod{a = 1}^n m+a-k).\]

But, the product of any $n$ consecutive integers is divisible by $n!$. We can prove this as follows:

\[(t-n+1)(t-n+2) \cdots (t) = \frac{(t+n)!}{t!} = n! \frac{(t+n)!}{t!n!} = n! {t+n}\choose{t}.\]

Therefore, $(\prod_{a = 1}^n m+a-k)$ is divisible by $n!$, and $(m+k+1)(\prod_{a = 1}^n m+a+k+1)$ is divisible by $(n+1)!$. However, we are told that $m+k+1$ is prime and therefore it is not divisible by any of the numbers $1$ through $n+1$. Therefore, $(\prod_{a = 1}^n m+a+k+1)$ is divisible by $(n+1)!$.

Finally, it is clear that $(c_{m+1}-c_k)(c_{m+2}-c_k)\cdots (c_{m+n}-c_k)$ is divisible by $n!(n+1)! = (1 \cdot 2)(2 \cdot 3)(3 \cdot 4) \cdots (n \cdot (n+1)) = c_1c_2\cdots c_n$. $\square$

~mathboy100

Solution 2

We have that $c_1c_2c_3...c_n=n!(n+1)!$

and we have that $c_a-c_b=a^2-b^2+a-b=(a-b)(a+b+1)$

So we have that $(c_{m+1}-c_k)(c_{m+2}-c_k)\ldots(c_{m+n}-c_k)=\frac{(m+n-k)!}{(m-n)!}\frac{(m+n+k+1)!}{(m+k+1)!}$ We have to show that:

$\frac{(c_{m+1}-c_k)(c_{m+2}-c_k)\ldots(c_{m+n}-c_k)}{n!(n+1)!}=\frac{(m+n-k)!}{(m-n)!n!}\frac{(m+n+k+1)!}{(m+k)!(n+1)!} \frac 1{m+k+1}$ is an integer

But $\frac{(m+n-k)!}{(m-n)!n!}=\binom {m+n-k}n$ is an integer and ${(m+n+k+1)!}{(m+k)!(n+1)!} \frac 1{m+k+1}=\binom {m+n+k+1}{n+1}\frac 1{m+k+1}$ is an integer because $m+k+1|m+n+k+1!$ but does not divide neither $n+1!$ nor $m+n!$ because $m+k+1$ is prime and it is greater than $n+1$ (given in the hypotesis) and $m+n$.

The above solution was posted and copyrighted by Simo_the_Wolf. The original thread can be found here: [1]

See Also

1967 IMO (Problems) • Resources
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1967_IMO_Problems/Problem_3&oldid=183914"