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 "1970 IMO Problems/Problem 4"
 
(One intermediate revision by the same user not shown)
Line 19: Line 19:
 
students who know nothing more than the notion of <math>mod</math> (modulo).
 
students who know nothing more than the notion of <math>mod</math> (modulo).
  
−
2. I will then give another solution, which in fact, answers
+
2. I will then give another solution, which in fact, proves
 
a more difficult problem: the product of six consecutive
 
a more difficult problem: the product of six consecutive
 
integers can not be a perfect square.
 
integers can not be a perfect square.
Line 28: Line 28:
 
As of December 2024 there are several solutions presented
 
As of December 2024 there are several solutions presented
 
in this discussion (I can make sense of two of them), as
 
in this discussion (I can make sense of two of them), as
−
well as two references.  The references are
+
well as two references to publications where the problem
 +
is solved.  The references are
 
https://www.jstor.org/stable/2635974?seq=1 (to a journal
 
https://www.jstor.org/stable/2635974?seq=1 (to a journal
 
article of 1874) and http://www.renyi.hu/~p_erdos/1939-03.pdf
 
article of 1874) and http://www.renyi.hu/~p_erdos/1939-03.pdf
−
to a paper from 1939, which proves a more general result.
+
to a paper from 1939.  This second paper proves a more
 +
general statement: a product of any number of consecutive
 +
integers can not be a perfect square.
  
  
Line 37: Line 40:
  
 
Let <math>\{m_1, m_2, m_3\}</math> and <math>\{m_4, m_5, m_6\}</math> be a partition
 
Let <math>\{m_1, m_2, m_3\}</math> and <math>\{m_4, m_5, m_6\}</math> be a partition
−
of <math>\{n, n+1, n+2, n+3, n+4, n+5\}</math>.  If a number <math>p \ge 7</math>
+
of <math>\{n, n+1, n+2, n+3, n+4, n+5\}</math>.  If a number <math>p \ge 4</math>
−
is a factor of <math>m_1m_2m_3,</math> then it must also be a factor
+
is a factor of <math>m_1m_2m_3,</math> then <math>p</math> must also be a factor
 
of <math>m_4m_5m_6</math>.  In particular, if <math>7</math> is a factor of one
 
of <math>m_4m_5m_6</math>.  In particular, if <math>7</math> is a factor of one
 
of the numbers in <math>\{n, n+1, n+2, n+3, n+4, n+5\}</math>, then it
 
of the numbers in <math>\{n, n+1, n+2, n+3, n+4, n+5\}</math>, then it
Line 55: Line 58:
  
 
On the other hand, if <math>m</math> is an integer, then <math>m^2 \mod 7</math>
 
On the other hand, if <math>m</math> is an integer, then <math>m^2 \mod 7</math>
−
can be one of <math>0, 1, 2, 4</math>.  Indeed let <math>m = 7p + q</math> with
+
is one of <math>0, 1, 2, 4</math>.  Indeed let <math>m = 7p + q</math> with
 
<math>q \in \{0, 1, 2, 3, 4, 5, 6\}</math>.  Calculating <math>m^2</math>, we
 
<math>q \in \{0, 1, 2, 3, 4, 5, 6\}</math>.  Calculating <math>m^2</math>, we
−
see that the result will be a multiple of <math>7</math> plus one
+
see that the result will be a multiple of <math>7</math> plus
 
<math>0, 1, 4, 9, 16, 25, 36</math>, which are
 
<math>0, 1, 4, 9, 16, 25, 36</math>, which are
 
<math>0, 1, 4, 2, 2, 4, 1 \mod 7</math>, none of which is <math>6 \mod 7</math>.
 
<math>0, 1, 4, 2, 2, 4, 1 \mod 7</math>, none of which is <math>6 \mod 7</math>.
Line 67: Line 70:
 
==Solution 3==
 
==Solution 3==
  
 +
If <math>\{n, n+1, n+2, n+3, n+4, n+5\}</math> can be partitioned in two
 +
sets <math>\{m_1, m_2, m_3\}</math> and <math>\{m_4, m_5, m_6\}</math> such that
 +
<math>m_1m_2m_3 = m_4m_5m_6</math> then <math>N = n(n+1)(n+2)(n+3)(n+4)(n+5)</math>
 +
must be a perfect square.  To shorten the text, when a number
 +
<math>N</math> is a perfect square, we'll write <math>N = \square</math>.  Se we
 +
want to prove a more difficult problem, namely
 +
<math>N = n(n+1)(n+2)(n+3)(n+4)(n+5) \ne \square</math>.  Assume for
 +
the sake of reaching a contradiction that <math>N = \square</math>.
 +
 +
Regroup the factors of <math>N</math> and do some multiplications.  We
 +
get <math>(n^2 + 5n)[(n^2 + 5n) + 4][(n^2 + 5n) + 6] = \square</math>.
 +
Denote <math>m = n^2 + 5n</math>.  We have <math>m(m+4)(m+6) = \square</math>.
 +
Let <math>m = p^2q</math>, such that all the prime factors of <math>q</math> are at
 +
power <math>1</math> (in other words, <math>p^2</math> is the product of all the
 +
prime factors of <math>m</math> at an even power, and <math>q</math> is the product
 +
of all the remaining prime factors of <math>m</math>).
 +
 +
Then, we have <math>q(p^2q + 4)(p^2q + 6) = \square</math>.  Multiplying,
 +
we get that <math>q(Aq + 24) = \square</math> for some number <math>A</math>
 +
(in fact <math>A = p^4q + 10p^2</math>).  Note that if a prime <math>a</math>
 +
is a factor of <math>q</math>, then it is a factor of the right hand
 +
side <math>\square</math>, so <math>a^2</math> is a factor of the right hand
 +
side <math>\square</math>, so <math>a^2</math> is a factor of <math>q(Aq + 24)</math>, so
 +
<math>a</math> is a factor of <math>Aq + 24</math>, so <math>a</math> is a factor of <math>24</math>.
 +
This implies that <math>a = 2</math> or <math>a = 3</math>, which in its turn
 +
implies that <math>q = 2</math>, or <math>q = 3</math> or <math>q = 6</math> (since <math>q</math> has
 +
its factors at power <math>1</math>).
 +
 +
We will continue the proof by contradiction by taking
 +
three cases (for <math>q = 2, 3, 6</math>), and showing that none of
 +
the following three statements can be true:
 +
<math>2(2p^2 + 4)(2p^2 + 6) = \square</math>,
 +
<math>3(3p^2 + 4)(3p^2 + 6) = \square</math>,
 +
<math>6(6p^2 + 4)(6p^2 + 6) = \square</math>.
 +
 +
Case 1: <math>2(2p^2 + 4)(2p^2 + 6) = \square</math> becomes
 +
<math>2(p^2 + 2)(p^2 + 3) = \square</math>.  Note that <math>p^2 + 2</math>
 +
and <math>p^2 + 3</math> have no common factors (since they differ
 +
by <math>1</math>) so either
 +
 +
Case 1.1: <math>p^2 + 2 = \square</math> and <math>2(p^2 + 3) = \square</math>
 +
 +
or
 +
 +
Case 1.2: <math>2(p^2 + 2) = \square</math> and <math>p^2 + 3 = \square</math>
 +
 +
Case 1.1 is impossible because <math>p^2 + 2 = \square</math> is
 +
impossible (because two squares differ by more than <math>2</math>).
 +
 +
Case 1.2 implies <math>p = 1</math>, because only the squares <math>1</math>
 +
and <math>4</math> differ by <math>3</math> (all higher squares differ by more
 +
than <math>3</math>).  But if <math>p = 1</math> the other condition in case
 +
1.2 becomes <math>2(1 + 2) = \square</math>, which is false.
 +
 +
So Case 1 is impossible.
 +
 +
Case 2: The condition becomes <math>(3p^2 + 4)(p^2 + 2) = \square</math>.
 +
We consider two sub-cases corresponding to <math>p = </math> odd or <math>p = </math>
 +
even.
 +
 +
Case 2.1: When <math>p =</math> odd, <math>3p^2 + 4</math> and <math>p^2 + 2</math> have no common
 +
factors because <math>3p^2 + 4</math> and <math>3(p^2 + 2) = 3p^2 + 6</math> have no
 +
common factors (because we have two odd numbers which differ by
 +
<math>2</math>).  So we must have <math>3p^2 + 4 = \square</math> and
 +
<math>p^2 + 2 = \square</math>.  But this is impossible because of the latter
 +
condition.
 +
 +
Case 2.2: If <math>p =</math> even, let <math>p = 2r</math>.  The condition becomes
 +
<math>2(3r^2 + 1)(2r^2 + 1) = \square</math>.  Note that <math>3r^2 + 1</math> and
 +
<math>2r^2 + 1</math> have no common factors (because their multiples by
 +
<math>2</math> and <math>3</math> are <math>6r^2 + 2</math> and <math>6r^2 + 3</math> which differ by <math>1</math>).
 +
 +
Case 2.2.1: Take the sub-sub-case <math>2(3r^2 + 1) = \square</math> and
 +
<math>2r^2 + 1 = \square</math>.  The first condition implies that we
 +
must have <math>3r^2 + 1 = 2a^2</math> for some <math>a</math>, or
 +
<math>3(r^2 + 1) = 2(a^2 + 1)</math>.  But this is impossible, since
 +
<math>a^2 + 1</math> can not be a multiple of <math>3</math>.  (Indeed, take <math>a = 3b</math>,
 +
<math>a = 3b + 1</math>, <math>a = 3b + 2</math>; <math>a^2 = 0 \mod 3</math> or <math>a^2 = 1 \mod 3</math>).
 +
 +
Case 2.2.2: Take the sub-sub-case <math>3r^2 + 1 = \square</math> and
 +
<math>2(2r^2 + 1) = \square</math>.  The second condition is impossible
 +
because <math>2(2r^2 + 1)</math> has exactly <math>2^1</math> as a factor, so it
 +
can not be a square.
 +
 +
Case 3: <math>6(6p^2 + 4)(6p^2 + 6) = \square</math> becomes
 +
<math>2(3p^2 + 2)(p^2 + 1) = \square</math>.  We see that <math>3p^2 + 2</math>
 +
and <math>p^2 + 1</math> have no common factors since <math>3p^2 + 2</math> and
 +
<math>3(p^2 + 1) = 3p^2 + 3</math> differ by <math>1</math>.  So we have
 +
 +
Case 3.1: <math>2(3p^2 + 2) = \square</math> and <math>p^2 + 1 = \square</math>.
 +
This case is impossible, since the latter condition is
 +
impossible (because two squares differ by more than <math>1</math>).
  
 +
Case 3.2: <math>3p^2 + 2 = \square</math> and <math>2(p^2 + 1) = \square</math>.
 +
The first condition implies <math>3(p^2 + 1) = a^2 + 1</math>, but this
 +
is impossible since as we saw in Case 2.2.2, <math>a^2 + 1</math> can
 +
not be a multiple of <math>3</math>.
  
 +
We looked at all possible cases, and they were impossible,
 +
so <math>N = n(n+1)(n+2)(n+3)(n+4)(n+5)</math> can not be a perfect square.
  
 +
[Solution by pf02, December 2024]
  
  

Latest revision as of 19:44, 2 December 2024

Problem

Find the set of all positive integers $n$ with the property that the set $\{ n, n+1, n+2, n+3, n+4, n+5 \}$ can be partitioned into two sets such that the product of the numbers in one set equals the product of the numbers in the other set.


Solution

The only primes dividing numbers in the set can be 2, 3 or 5, because if any larger prime was a factor, then it would only divide one number in the set and hence only one product. Three of the numbers must be odd. At most one of the odd numbers can be a multiple of 3 and at most one can be a multiple of 5. The other odd number cannot have any prime factors. The only such number is 1, so the set must be $\{ 1, 2, 3, 4, 5, 6 \}$, but that does not work because only one of the numbers is a multiple of 5. So there are no such sets.


Solution 2

As in the previous solution, none of the six consecutive numbers can be multiples of $7$. This means that together, they take on the values $\{ 1, 2, 3, 4, 5, 6 \} \mod 7$. The product of all the numbers in this set, then, is $-1 \mod 7$, by Wilson's Theorem. However, $-1$ is not a quadratic residue $\mod 7$, which means that we cannot partition the original set into two sets of equal product. Thus, no such $n$ exist.


Remarks (added by pf02, December 2024)

1. I will re-write Solution 2 without making references to Wilson's Theorem or quadratic residue. Beautiful as they are, they are not needed here, so I think it is worth re-writing this elegant proof so that it can be understood by students who know nothing more than the notion of $mod$ (modulo).

2. I will then give another solution, which in fact, proves a more difficult problem: the product of six consecutive integers can not be a perfect square.

3. Just as a matter of general interest, the more difficult problem is the subject of a discussion at https://math.stackexchange.com/questions/90894/product-of-six-consecutive-integers-being-a-perfect-square . As of December 2024 there are several solutions presented in this discussion (I can make sense of two of them), as well as two references to publications where the problem is solved. The references are https://www.jstor.org/stable/2635974?seq=1 (to a journal article of 1874) and http://www.renyi.hu/~p_erdos/1939-03.pdf to a paper from 1939. This second paper proves a more general statement: a product of any number of consecutive integers can not be a perfect square.


Solution 2 re-visited

Let $\{m_1, m_2, m_3\}$ and $\{m_4, m_5, m_6\}$ be a partition of $\{n, n+1, n+2, n+3, n+4, n+5\}$. If a number $p \ge 4$ is a factor of $m_1m_2m_3,$ then $p$ must also be a factor of $m_4m_5m_6$. In particular, if $7$ is a factor of one of the numbers in $\{n, n+1, n+2, n+3, n+4, n+5\}$, then it must be a factor of another, different number in this set. But $7$ can be a factor of at most one of six consecutive integers, so it is a factor of none of them.

Since none of the numbers in $\{n, n+1, n+2, n+3, n+4, n+5\}$ is divisible by $7$, the six values of $\{q_i, i = 1, \dots, 6\}$ from $n = q_1 \mod 7, n_1 = q_2 \mod 7, n_2 = q_3 \mod 7, n_3 = q_4 \mod 7, n_4 = q_5 \mod 7, n_5 = q_6 \mod 7$ are $1, 2, 3, 4, 5, 6$.

So $n(n+1)(n+2)(n+3)(n+4)(n+5) = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 720 = 6 \mod 7$.

On the other hand, if $m$ is an integer, then $m^2 \mod 7$ is one of $0, 1, 2, 4$. Indeed let $m = 7p + q$ with $q \in \{0, 1, 2, 3, 4, 5, 6\}$. Calculating $m^2$, we see that the result will be a multiple of $7$ plus $0, 1, 4, 9, 16, 25, 36$, which are $0, 1, 4, 2, 2, 4, 1 \mod 7$, none of which is $6 \mod 7$.

So, $n(n+1)(n+2)(n+3)(n+4)(n+5)$ can not be a perfect square, as it should be if $m_1m_2m_3 = m_4m_5m_6$.


Solution 3

If $\{n, n+1, n+2, n+3, n+4, n+5\}$ can be partitioned in two sets $\{m_1, m_2, m_3\}$ and $\{m_4, m_5, m_6\}$ such that $m_1m_2m_3 = m_4m_5m_6$ then $N = n(n+1)(n+2)(n+3)(n+4)(n+5)$ must be a perfect square. To shorten the text, when a number $N$ is a perfect square, we'll write $N = \square$. Se we want to prove a more difficult problem, namely $N = n(n+1)(n+2)(n+3)(n+4)(n+5) \ne \square$. Assume for the sake of reaching a contradiction that $N = \square$.

Regroup the factors of $N$ and do some multiplications. We get $(n^2 + 5n)[(n^2 + 5n) + 4][(n^2 + 5n) + 6] = \square$. Denote $m = n^2 + 5n$. We have $m(m+4)(m+6) = \square$. Let $m = p^2q$, such that all the prime factors of $q$ are at power $1$ (in other words, $p^2$ is the product of all the prime factors of $m$ at an even power, and $q$ is the product of all the remaining prime factors of $m$).

Then, we have $q(p^2q + 4)(p^2q + 6) = \square$. Multiplying, we get that $q(Aq + 24) = \square$ for some number $A$ (in fact $A = p^4q + 10p^2$). Note that if a prime $a$ is a factor of $q$, then it is a factor of the right hand side $\square$, so $a^2$ is a factor of the right hand side $\square$, so $a^2$ is a factor of $q(Aq + 24)$, so $a$ is a factor of $Aq + 24$, so $a$ is a factor of $24$. This implies that $a = 2$ or $a = 3$, which in its turn implies that $q = 2$, or $q = 3$ or $q = 6$ (since $q$ has its factors at power $1$).

We will continue the proof by contradiction by taking three cases (for $q = 2, 3, 6$), and showing that none of the following three statements can be true: $2(2p^2 + 4)(2p^2 + 6) = \square$, $3(3p^2 + 4)(3p^2 + 6) = \square$, $6(6p^2 + 4)(6p^2 + 6) = \square$.

Case 1: $2(2p^2 + 4)(2p^2 + 6) = \square$ becomes $2(p^2 + 2)(p^2 + 3) = \square$. Note that $p^2 + 2$ and $p^2 + 3$ have no common factors (since they differ by $1$) so either

Case 1.1: $p^2 + 2 = \square$ and $2(p^2 + 3) = \square$

or

Case 1.2: $2(p^2 + 2) = \square$ and $p^2 + 3 = \square$

Case 1.1 is impossible because $p^2 + 2 = \square$ is impossible (because two squares differ by more than $2$).

Case 1.2 implies $p = 1$, because only the squares $1$ and $4$ differ by $3$ (all higher squares differ by more than $3$). But if $p = 1$ the other condition in case 1.2 becomes $2(1 + 2) = \square$, which is false.

So Case 1 is impossible.

Case 2: The condition becomes $(3p^2 + 4)(p^2 + 2) = \square$. We consider two sub-cases corresponding to $p =$ odd or $p =$ even.

Case 2.1: When $p =$ odd, $3p^2 + 4$ and $p^2 + 2$ have no common factors because $3p^2 + 4$ and $3(p^2 + 2) = 3p^2 + 6$ have no common factors (because we have two odd numbers which differ by $2$). So we must have $3p^2 + 4 = \square$ and $p^2 + 2 = \square$. But this is impossible because of the latter condition.

Case 2.2: If $p =$ even, let $p = 2r$. The condition becomes $2(3r^2 + 1)(2r^2 + 1) = \square$. Note that $3r^2 + 1$ and $2r^2 + 1$ have no common factors (because their multiples by $2$ and $3$ are $6r^2 + 2$ and $6r^2 + 3$ which differ by $1$).

Case 2.2.1: Take the sub-sub-case $2(3r^2 + 1) = \square$ and $2r^2 + 1 = \square$. The first condition implies that we must have $3r^2 + 1 = 2a^2$ for some $a$, or $3(r^2 + 1) = 2(a^2 + 1)$. But this is impossible, since $a^2 + 1$ can not be a multiple of $3$. (Indeed, take $a = 3b$, $a = 3b + 1$, $a = 3b + 2$; $a^2 = 0 \mod 3$ or $a^2 = 1 \mod 3$).

Case 2.2.2: Take the sub-sub-case $3r^2 + 1 = \square$ and $2(2r^2 + 1) = \square$. The second condition is impossible because $2(2r^2 + 1)$ has exactly $2^1$ as a factor, so it can not be a square.

Case 3: $6(6p^2 + 4)(6p^2 + 6) = \square$ becomes $2(3p^2 + 2)(p^2 + 1) = \square$. We see that $3p^2 + 2$ and $p^2 + 1$ have no common factors since $3p^2 + 2$ and $3(p^2 + 1) = 3p^2 + 3$ differ by $1$. So we have

Case 3.1: $2(3p^2 + 2) = \square$ and $p^2 + 1 = \square$. This case is impossible, since the latter condition is impossible (because two squares differ by more than $1$).

Case 3.2: $3p^2 + 2 = \square$ and $2(p^2 + 1) = \square$. The first condition implies $3(p^2 + 1) = a^2 + 1$, but this is impossible since as we saw in Case 2.2.2, $a^2 + 1$ can not be a multiple of $3$.

We looked at all possible cases, and they were impossible, so $N = n(n+1)(n+2)(n+3)(n+4)(n+5)$ can not be a perfect square.

[Solution by pf02, December 2024]


See Also

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