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 6"
m
 
(5 intermediate revisions by 2 users not shown)
Line 5: Line 5:
 
medals were awarded. How many days did the contest last, and how many
 
medals were awarded. How many days did the contest last, and how many
 
medals were awarded altogether?
 
medals were awarded altogether?
 +
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
 
 
This is not a particularly elegant solution, but if you start from 1 and go all the way in a clever method, by only guessing those that are 1 more than a multiple of 7, you arrive at the answer of 36.
 
This is not a particularly elegant solution, but if you start from 1 and go all the way in a clever method, by only guessing those that are 1 more than a multiple of 7, you arrive at the answer of 36.
 +
 +
 +
==Comment (added by pf02, August 2024)==
 +
 +
Indeed, as the author says, the above is not an elegant solution.  Also,
 +
it does not give any insight into the uniqueness of the answer to the
 +
problem.  I would also comment that choosing to verify the statement
 +
only for multiples of <math>7</math> plus one is not a "clever method", it is
 +
quite an obvious thing to do.  And, note that when the author says
 +
"arrive at the answer of <math>36</math>", they mean "the contest lasted for
 +
<math>6</math> days, and <math>36</math> medals were awarded".
 +
 +
Below, I will give another solution, which is more in the spirit and
 +
style of contemporary problem solving.
 +
 +
 +
==Solution 2==
 +
 +
Denote <math>m_0 = m</math>.  Let <math>m_k</math> be the number of medals left on day <math>k</math>
 +
after the medals for the day have been awarded.  The problem says
 +
that <math>m_k = m_{k-1} - k - \frac{m_{k-1} - k}{7}</math> for
 +
<math>k = 1, 2, \dots, (n - 1)</math>, and <math>m_{n - 1} = n</math>, and <math>n > 1</math>.
 +
Simplify the recursive relation and get
 +
<math>m_k = \frac{6}{7}m_{k - 1} - \frac{6}{7}k</math>.
 +
 +
We will now get an explicit formula for <math>m_k</math>.
 +
 +
<math>m_1 = \frac{6}{7}m - \frac{6}{7} \cdot 1</math>
 +
 +
<math>m_2 = \frac{6}{7}m_1 - \frac{6}{7} \cdot 2 =
 +
\left(\frac{6}{7}\right)^2m - \left(\frac{6}{7}\right)^2 \cdot 1 - \frac{6}{7} \cdot 2</math>
 +
 +
<math>m_3 = \frac{6}{7}m_2 - \frac{6}{7} \cdot 3 =
 +
\left(\frac{6}{7}\right)^3m - \left(\frac{6}{7}\right)^3 \cdot 1 -
 +
\left(\frac{6}{7}\right)^2 \cdot 2 + \frac{6}{7} \cdot 3</math>
 +
 +
. . . . . . . .
 +
 +
<math>m_{n - 1} = \frac{6}{7}m_{n - 2} - \frac{6}{7} \cdot (n - 1) =
 +
\left(\frac{6}{7}\right)^{n - 1}m - \left(\frac{6}{7}\right)^{n - 1} \cdot 1 -
 +
\left(\frac{6}{7}\right)^{n - 2} \cdot 2 - \dots - \left(\frac{6}{7}\right)^2 \cdot (n - 2) -
 +
\frac{6}{7} \cdot (n - 1)</math>
 +
 +
To put it in a shorter way,
 +
 +
<math>m_{n - 1} = \left(\frac{6}{7}\right)^{n - 1}m - \sum_{k = 1}^{n - 1} \left(\frac{6}{7}\right)^{n - k} \cdot k</math>
 +
 +
(The reader who is not happy with having obtained this result by having
 +
observed the pattern for <math>m_k</math> can easily verify it by induction.)
 +
 +
Note that the sum in the equality above is the sum of the arithmetic-geometric
 +
sequence formed by the geometric progression
 +
<math>\{\ \left(\frac{6}{7}\right)^{n - 1}, \left(\frac{6}{7}\right)^{n - 2}, \dots,
 +
\left(\frac{6}{7}\right)^2, \frac{6}{7}\ \}</math>
 +
(with common ratio <math>\frac{7}{6}</math> (note that the progression starts from a
 +
number smaller than <math>1</math> and is increasing)), and the arithmetic progression
 +
<math>\{\ 1, 2, \dots, (n - 2), (n - 1)\ \}</math> (with common difference <math>1</math>).  The
 +
formula for the sum of the terms of such sequences is reasonably well known
 +
(and not difficult to prove)
 +
(see for example [[Arithmetico-geometric_series]] or
 +
https://en.wikipedia.org/wiki/Arithmetico-geometric_sequence).
 +
 +
Applying the formula for the sum of the arithmetic-geometric sequence, and
 +
using the fact that <math>m_{n - 1} = n</math>, we get
 +
 +
<math>n = \left(\frac{6}{7}\right)^{n - 1}m -
 +
\frac{\left(\frac{6}{7}\right)^{n - 1} \cdot 1 - 1 \cdot n}{1 - \frac{7}{6}}
 +
-\frac{\frac{7}{6}}{\left(1 - \frac{7}{6}\right)^2} \left(\left(\frac{6}{7}\right)^{n - 1} - 1 \right)</math>
 +
 +
Now do all the simplifications, and rearrange terms.  We have
 +
 +
<math>m - 36 = 7(n - 6) \left(\frac{7}{6}\right)^{n - 1}</math>
 +
 +
In order for <math>m</math> to be an integer, we have to have that
 +
<math>\frac{n - 6}{6^{n - 1}}</math> is an integer.  This is clearly
 +
not the case when <math>n = 2, 3, 4, 5</math>.  It is an integer
 +
when <math>n = 6</math>, in which case <math>m = 36</math>.  The fraction is
 +
not an integer for <math>n = 7</math>, and even less so for <math>n > 7</math>
 +
since the exponential at the denominator increases much
 +
faster than the linear function at the numerator.
 +
 +
Thus, <math>m = 36, n = 6</math> is the only solution to the problem.
 +
 +
(Solution by pf02, August 2024)
 +
 +
 
== See Also == {{IMO box|year=1967|num-b=5|after=Last Question}}
 
== See Also == {{IMO box|year=1967|num-b=5|after=Last Question}}

Latest revision as of 19:35, 24 August 2024

In a sports contest, there were $m$ medals awarded on $n$ successive days $(n > 1)$. On the first day, one medal and $\frac{1}{7}$ of the remaining $m - 1$ medals were awarded. On the second day, two medals and $\frac{1}{7}$ of the now remaining medals were awarded; and so on. On the n-th and last day, the remaining $n$ medals were awarded. How many days did the contest last, and how many medals were awarded altogether?


Solution

This is not a particularly elegant solution, but if you start from 1 and go all the way in a clever method, by only guessing those that are 1 more than a multiple of 7, you arrive at the answer of 36.


Comment (added by pf02, August 2024)

Indeed, as the author says, the above is not an elegant solution. Also, it does not give any insight into the uniqueness of the answer to the problem. I would also comment that choosing to verify the statement only for multiples of $7$ plus one is not a "clever method", it is quite an obvious thing to do. And, note that when the author says "arrive at the answer of $36$", they mean "the contest lasted for $6$ days, and $36$ medals were awarded".

Below, I will give another solution, which is more in the spirit and style of contemporary problem solving.


Solution 2

Denote $m_0 = m$. Let $m_k$ be the number of medals left on day $k$ after the medals for the day have been awarded. The problem says that $m_k = m_{k-1} - k - \frac{m_{k-1} - k}{7}$ for $k = 1, 2, \dots, (n - 1)$, and $m_{n - 1} = n$, and $n > 1$. Simplify the recursive relation and get $m_k = \frac{6}{7}m_{k - 1} - \frac{6}{7}k$.

We will now get an explicit formula for $m_k$.

$m_1 = \frac{6}{7}m - \frac{6}{7} \cdot 1$

$m_2 = \frac{6}{7}m_1 - \frac{6}{7} \cdot 2 = \left(\frac{6}{7}\right)^2m - \left(\frac{6}{7}\right)^2 \cdot 1 - \frac{6}{7} \cdot 2$

$m_3 = \frac{6}{7}m_2 - \frac{6}{7} \cdot 3 = \left(\frac{6}{7}\right)^3m - \left(\frac{6}{7}\right)^3 \cdot 1 - \left(\frac{6}{7}\right)^2 \cdot 2 + \frac{6}{7} \cdot 3$

. . . . . . . .

$m_{n - 1} = \frac{6}{7}m_{n - 2} - \frac{6}{7} \cdot (n - 1) = \left(\frac{6}{7}\right)^{n - 1}m - \left(\frac{6}{7}\right)^{n - 1} \cdot 1 - \left(\frac{6}{7}\right)^{n - 2} \cdot 2 - \dots - \left(\frac{6}{7}\right)^2 \cdot (n - 2) - \frac{6}{7} \cdot (n - 1)$

To put it in a shorter way,

$m_{n - 1} = \left(\frac{6}{7}\right)^{n - 1}m - \sum_{k = 1}^{n - 1} \left(\frac{6}{7}\right)^{n - k} \cdot k$

(The reader who is not happy with having obtained this result by having observed the pattern for $m_k$ can easily verify it by induction.)

Note that the sum in the equality above is the sum of the arithmetic-geometric sequence formed by the geometric progression $\{\ \left(\frac{6}{7}\right)^{n - 1}, \left(\frac{6}{7}\right)^{n - 2}, \dots, \left(\frac{6}{7}\right)^2, \frac{6}{7}\ \}$ (with common ratio $\frac{7}{6}$ (note that the progression starts from a number smaller than $1$ and is increasing)), and the arithmetic progression $\{\ 1, 2, \dots, (n - 2), (n - 1)\ \}$ (with common difference $1$). The formula for the sum of the terms of such sequences is reasonably well known (and not difficult to prove) (see for example Arithmetico-geometric_series or https://en.wikipedia.org/wiki/Arithmetico-geometric_sequence).

Applying the formula for the sum of the arithmetic-geometric sequence, and using the fact that $m_{n - 1} = n$, we get

$n = \left(\frac{6}{7}\right)^{n - 1}m - \frac{\left(\frac{6}{7}\right)^{n - 1} \cdot 1 - 1 \cdot n}{1 - \frac{7}{6}} -\frac{\frac{7}{6}}{\left(1 - \frac{7}{6}\right)^2} \left(\left(\frac{6}{7}\right)^{n - 1} - 1 \right)$

Now do all the simplifications, and rearrange terms. We have

$m - 36 = 7(n - 6) \left(\frac{7}{6}\right)^{n - 1}$

In order for $m$ to be an integer, we have to have that $\frac{n - 6}{6^{n - 1}}$ is an integer. This is clearly not the case when $n = 2, 3, 4, 5$. It is an integer when $n = 6$, in which case $m = 36$. The fraction is not an integer for $n = 7$, and even less so for $n > 7$ since the exponential at the denominator increases much faster than the linear function at the numerator.

Thus, $m = 36, n = 6$ is the only solution to the problem.

(Solution by pf02, August 2024)


See Also

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