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
m
 
(10 intermediate revisions by 2 users not shown)
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> = \left(\prod_{a = 1}^n m+a+k+1\right)\left(\prod{a = 1}^n m+a-k\right).</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)\left(\prod_{a = 1}^n m+a+k+1\right)</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)) = </math><math>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>
  
Line 14: Line 33:
  
 
The above solution was posted and copyrighted by Simo_the_Wolf. The original thread can be found here: [https://aops.com/community/p392191]  
 
The above solution was posted and copyrighted by Simo_the_Wolf. The original thread can be found here: [https://aops.com/community/p392191]  
 +
 +
 +
==Remark and correction (added by pf02, September 2024)==
 +
 +
1.  The two solutions are essentially the same.  They are
 +
just different expressions of the same idea.  Unfortunately,
 +
both are written very sloppily, but the interested reader
 +
can easily correct the mistakes, improve on the arguments,
 +
and make sense of the proofs.
 +
 +
2.  Both solutions are incomplete.  They both assume (without
 +
saying it) that <math>m + 1 > k</math>.  Maybe the problem meant to say
 +
this, but it didn't, so we have to see what happens if
 +
<math>m + 1 \le k</math>.  There are two cases:
 +
 +
First, assume <math>m + 1 \le k \le m + n</math>.  In this case,
 +
<math>(c_{m + 1} - c_k)(c_{m + 2} - c_k) \cdots (c_{m + n} - c_k) = 0</math>,
 +
and we can say that <math>0</math> is divisible by anything.
 +
 +
Next, assume <math>m + n < k</math>.  In this case, each factor of the
 +
first product is negative, and we will consider the product
 +
 +
<math>P = (c_k - c_{m + 1})(c_k - c_{m + 2}) \cdots (c_k - c_{m + n})</math>
 +
 +
for the sake of working with positive factors.  <math>P</math> differs from
 +
the product in the problem by at most a sign, so it is enough to
 +
show that <math>P</math> is divisible by <math>c_1c_2 \cdots c_n</math>.
 +
 +
The proof of this fact goes along the same lines as the proof when
 +
<math>m + 1 > k</math>.  We will give the proof for the sake of having a
 +
complete, properly written proof.
 +
 +
Using <math>p(p + 1) - q(q + 1) = (p + q + 1)(p - q)</math> we get that
 +
<math>c_1c_2 \cdots c_n = (n + 1)! \cdot n!</math>.  We also get that
 +
<math>P = \prod_{p = 1}^n (k + m + p + 1) \cdot \prod_{p = 1}^n (k - m - p)</math>.
 +
 +
We have that <math>n!\ |\ \prod_{p = 1}^n (k - m - p)</math> (i.e. the product is
 +
divisible by the factorial) because
 +
 +
<math>\frac{\prod_{p = 1}^n (k - m - p)}{n!} =
 +
\frac{(k - m - 1)!}{(k - m - 1 - n)! \cdot n!} = {k - m - 1 \choose n}</math>
 +
 +
which is an integer.  (Note that this all makes sense because we
 +
are in the case when <math>m + n < k</math>.)
 +
 +
Let us now show that <math>(n + 1)!\ |\ \prod_{p = 1}^n (k + m + p + 1)</math>.
 +
Let <math>P_1 = \prod_{p = 1}^n (k + m + p + 1)</math>.  We have that
 +
 +
<math>\frac{(k + m + 1) \cdot P_1}{(n + 1)!} =
 +
\frac{(k + m + 1) \cdot \prod_{p = 1}^n (k + m + p + 1)}{(n + 1)!} =
 +
\frac{\prod_{p = 0}^n (k + m + p + 1)}{(n + 1)!} =
 +
\frac{(k + m + n + 1)!}{(k + m)! \cdot (n + 1)!} =
 +
{k + m + n + 1 \choose n + 1}</math>
 +
 +
which is an integer.
 +
So <math>(n + 1)!\ |\ (k + m + 1) \cdot P_1</math>.  But none of the factors
 +
of <math>(n + 1)!</math> is a divisor of <math>(k + m + 1)</math> because <math>(k + m + 1)</math>
 +
is prime, and <math>n + 1 < k + m + 1</math>.  So
 +
<math>P_1 = \prod_{p = 1}^n (k + m + p + 1)</math> must be divisible by
 +
<math>(n + 1)!</math>.
 +
  
 
==See Also==
 
==See Also==
  
 
{{IMO box|year=1967|num-b=2|num-a=4}}
 
{{IMO box|year=1967|num-b=2|num-a=4}}

Latest revision as of 16:39, 7 September 2024

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)\] \[= \left(\prod_{a = 1}^n m+a+k+1\right)\left(\prod{a = 1}^n m+a-k\right).\]

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)\left(\prod_{a = 1}^n m+a+k+1\right)$ 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]


Remark and correction (added by pf02, September 2024)

1. The two solutions are essentially the same. They are just different expressions of the same idea. Unfortunately, both are written very sloppily, but the interested reader can easily correct the mistakes, improve on the arguments, and make sense of the proofs.

2. Both solutions are incomplete. They both assume (without saying it) that $m + 1 > k$. Maybe the problem meant to say this, but it didn't, so we have to see what happens if $m + 1 \le k$. There are two cases:

First, assume $m + 1 \le k \le m + n$. In this case, $(c_{m + 1} - c_k)(c_{m + 2} - c_k) \cdots (c_{m + n} - c_k) = 0$, and we can say that $0$ is divisible by anything.

Next, assume $m + n < k$. In this case, each factor of the first product is negative, and we will consider the product

$P = (c_k - c_{m + 1})(c_k - c_{m + 2}) \cdots (c_k - c_{m + n})$

for the sake of working with positive factors. $P$ differs from the product in the problem by at most a sign, so it is enough to show that $P$ is divisible by $c_1c_2 \cdots c_n$.

The proof of this fact goes along the same lines as the proof when $m + 1 > k$. We will give the proof for the sake of having a complete, properly written proof.

Using $p(p + 1) - q(q + 1) = (p + q + 1)(p - q)$ we get that $c_1c_2 \cdots c_n = (n + 1)! \cdot n!$. We also get that $P = \prod_{p = 1}^n (k + m + p + 1) \cdot \prod_{p = 1}^n (k - m - p)$.

We have that $n!\ |\ \prod_{p = 1}^n (k - m - p)$ (i.e. the product is divisible by the factorial) because

$\frac{\prod_{p = 1}^n (k - m - p)}{n!} = \frac{(k - m - 1)!}{(k - m - 1 - n)! \cdot n!} = {k - m - 1 \choose n}$

which is an integer. (Note that this all makes sense because we are in the case when $m + n < k$.)

Let us now show that $(n + 1)!\ |\ \prod_{p = 1}^n (k + m + p + 1)$. Let $P_1 = \prod_{p = 1}^n (k + m + p + 1)$. We have that

$\frac{(k + m + 1) \cdot P_1}{(n + 1)!} = \frac{(k + m + 1) \cdot \prod_{p = 1}^n (k + m + p + 1)}{(n + 1)!} = \frac{\prod_{p = 0}^n (k + m + p + 1)}{(n + 1)!} = \frac{(k + m + n + 1)!}{(k + m)! \cdot (n + 1)!} = {k + m + n + 1 \choose n + 1}$

which is an integer. So $(n + 1)!\ |\ (k + m + 1) \cdot P_1$. But none of the factors of $(n + 1)!$ is a divisor of $(k + m + 1)$ because $(k + m + 1)$ is prime, and $n + 1 < k + m + 1$. So $P_1 = \prod_{p = 1}^n (k + m + p + 1)$ must be divisible by $(n + 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=226722"