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"

m
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
Find the set of all positive integers <math>n</math> with the property that the set <math>\{ n, n+1, n+2, n+3, n+4, n+5 \} </math> 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.
 
Find the set of all positive integers <math>n</math> with the property that the set <math>\{ n, n+1, n+2, n+3, n+4, n+5 \} </math> 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==
 
==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 <math>\{ 1, 2, 3, 4, 5, 6 \}</math>, but that does not work because only one of the numbers is a multiple of 5. So there are no such sets.
 
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 <math>\{ 1, 2, 3, 4, 5, 6 \}</math>, but that does not work because only one of the numbers is a multiple of 5. So there are no such sets.
 +
  
 
==Solution 2==
 
==Solution 2==
−
As in the previous solution, none of the six consecutive numbers can be multiples of <math>7</math>.  This means that together, they take on the values <math> \{ 1, 2, 3, 4, 5, 6, \} \mod 7</math>.  The product of all the numbers in this set, then, is <math>-1 \mod 7</math>, by [[Wilson's Theorem]].  However, <math>-1</math> is not a [[quadratic residue]] <math>\mod 7</math>, which means that we cannot partition the original set into two sets of equal product.  Thus, no such <math>n</math> exist.
+
As in the previous solution, none of the six consecutive numbers can be multiples of <math>7</math>.  This means that together, they take on the values <math> \{ 1, 2, 3, 4, 5, 6 \} \mod 7</math>.  The product of all the numbers in this set, then, is <math>-1 \mod 7</math>, by [[Wilson's Theorem]].  However, <math>-1</math> is not a [[quadratic residue]] <math>\mod 7</math>, which means that we cannot partition the original set into two sets of equal product.  Thus, no such <math>n</math> 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 <math>mod</math> (modulo).
 +
 
 +
2. I will then give another solution, which in fact, answers
 +
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.  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, which proves a more general result.
 +
 
 +
 
 +
==Solution 2 re-visited==
 +
 
 +
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>
 +
is a factor of <math>m_1m_2m_3,</math> then it must also be a factor
 +
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
 +
must be a factor of another, different number in this set.
 +
But <math>7</math> 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 <math>\{n, n+1, n+2, n+3, n+4, n+5\}</math>
 +
is divisible by <math>7</math>, the six values of <math>\{q_i, i = 1, \dots, 6\}</math>
 +
from <math>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</math> are
 +
<math>1, 2, 3, 4, 5, 6</math>.
 +
 
 +
So <math>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</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
 +
<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
 +
<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>.
 +
 
 +
So, <math>n(n+1)(n+2)(n+3)(n+4)(n+5)</math> can not be a perfect square,
 +
as it should be if <math>m_1m_2m_3 = m_4m_5m_6</math>.
 +
 
 +
 
 +
==Solution 3==
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 
==See Also==
 
==See Also==
 
{{IMO box|year=1970|num-b=3|num-a=5}}
 
{{IMO box|year=1970|num-b=3|num-a=5}}
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Revision as of 14:00, 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, answers 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. 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, which proves a more general result.


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 7$ is a factor of $m_1m_2m_3,$ then it 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$ can be 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 one $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

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=236050"