Difference between revisions of "1967 IMO Problems/Problem 6"
Line 32: | Line 32: | ||
<math>k = 1, 2, \dots, (n - 1)</math>, and <math>m_{n - 1} = n</math>, and <math>n > 1</math>. | <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 | Simplify the recursive relation and get | ||
− | <math>m_k = \frac{6}{7}m_{k - 1} - \frac{6}{7}k</math>. | + | <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 | ||
+ | series formed by the geometric series | ||
+ | <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> | ||
+ | and the arithmetic series | ||
+ | <math>\{\ 1, 2, \dots, (n - 2), (n - 1)\ \}</math>. The formula for the sum of the | ||
+ | terms of such series 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 series, and | ||
+ | using <math>m_{n - 1} = n</math>, we get | ||
+ | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Revision as of 16:59, 24 August 2024
In a sports contest, there were medals awarded on
successive days
. On the first day, one medal and
of the remaining
medals
were awarded. On the second day, two medals and
of the now remaining
medals were awarded; and so on. On the n-th and last day, the remaining
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 plus one is not a "clever method". And, note
that when the author says "arrive at the answer of
", they mean
"the contest lasted for
days, and
medals were awarded".
Below, I will give another solution, which is more in the spirit and style of contemporary problem solving.
Solution 2
Denote . Let
be the number of medals left on day
after the medals for the day have been awarded. The problem says
that
for
, and
, and
.
Simplify the recursive relation and get
.
We will now get an explicit formula for .
. . . . . . . .
To put it in a shorter way,
(The reader who is not happy with having obtained this result by having
observed the pattern for can easily verify it by induction.)
Note that the sum in the equality above is the sum of the arithmetic-geometric
series formed by the geometric series
and the arithmetic series
. The formula for the sum of the
terms of such series 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 series, and
using , we get
TO BE CONTINUED. SAVING MID WAY, SO I DON'T LOOS WORK DONE SO FAR.
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 |