Competition problem — Number theory

Library / /82 of 87

Number theory Difficulty 6.9 National Olympiad Prove it Austria

Max has $2015$ jars labelled with the numbers $1$ to $2015$ and an unlimited supply of coins. Consider the following starting configurations:

a. All jars are empty.

b. Jar $1$ contains $1$ coin, jar $2$ contains $2$ coins, and so on, up to jar $2015$ which contains $2015$ coins.

c. Jar $1$ contains $2015$ coins, jar $2$ contains $2014$ coins, and so on, up to jar $2015$ which contains $1$ coin.

Now Max selects in each step a number $n$ from $1$ to $2015$ and adds $n$ coins to each jar except to the jar $n$ .

Determine for each starting configuration in (a), (b), (c), if Max can use a finite, strictly positive number of steps to obtain an equal number of coins in each jar.

(Birgit Vera Schmidt)

Solution

Max can achieve his goal in all three cases by the procedures described below. Let $N = 2015$ be the number of jars.

a. Let Max select jar $j$ exactly $\left(\frac{N!}{j}\right)$ times. Then jar $j$ will contain
$\sum_{k \neq j} k \cdot \frac{N!}{k} = (N-1) \cdot N!$
coins which does not depend on $j$ as desired and has clearly needed at least one step.

b. Let Max select each jar $j$ exactly once. Then jar $j$ will contain $j + \sum_{k \neq j} k = \sum_k k$ coins which does not depend on $j$ as desired.

c. Let Max select jar $j$ exactly $\left(\frac{N!}{j} - 1\right)$ times. Then jar $j$ will contain
$N + 1 - j + \sum_{k \neq j} k \cdot \left( \frac{N!}{k} - 1 \right) = N + 1 - j + \sum_{k \neq j} (N! - k) = (N - 1)N! + (N + 1) - \sum_k k$
coins which does not depend on $j$ as desired.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.