2000 PMWC Problems/Problem T1

Problem

A box contains $4000$ to $6000$ candies. When the candies are evenly distributed to $5$ , $6$ , $7$ , $8$ , or $9$ children, there is always one candy left. If the candies are packaged into small bags each having the same number of candies, what is the largest number of candies below $4000$ in each bag so that no candies are left?

Solution

If there is always one candy left over when the candies are evenly distributed to $5$ , $6$ , $7$ , $8$ , or $9$ children, then there must also be exactly one candy left over when the candies are distributed to $LCM(5, 6, 7, 8, 9)$ children. Since $LCM(5, 6, 7, 8, 9) = 2^3 * 3^2 * 5^1 * 7^1 = 2520$ , the total number of candies can be expressed as $2520n + 1$ , where $n$ is any nonnegative integer. However, we know that there are between $4000$ and $6000$ candies, so the only viable value for $n$ is $2$ , meaning the total number of candies is $2520(2) + 1 = 5040 + 1 = 5041$ .

The problem then asks us to find the largest number of candies below $4000$ such that the candies are evenly distributed and no candies are left over. This is equivalent to asking what the largest factor of $5401$ is that is less than $4000$ . Since $5401 = 71^2$ , the only factors of $5401$ are $1$ , $71$ , and $5401$ . Thus the answer is $\boxed{71}$ .

Page

Toolbox

Search

2000 PMWC Problems/Problem T1

Problem

Solution

See Also