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 1

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}$ .

Solution 2

Since $n \equiv 1(\bmod k)$ for each $k$ from the set $\{5,6,7,8,9\}$ , we know that: $\begin{gathered} n-1 \equiv 0 \quad(\bmod 5) \\ n-1 \equiv 0 \quad(\bmod 6) \\ n-1 \equiv 0 \quad(\bmod 7) \\ n-1 \equiv 0 \quad(\bmod 8) \\ n-1 \equiv 0 \quad(\bmod 9) \end{gathered}$ Prime factorizations: $\begin{gathered} 5=5 \\ 6=2 \cdot 3 \\ 7=7 \\ 8=2^3 \\ 9=3^2 \end{gathered}$

The LCM is determined by taking the highest power of each prime that appears in the factorizations: $\mathrm{LCM}=2^3 \cdot 3^2 \cdot 5 \cdot 7=8 \cdot 9 \cdot 5 \cdot 7$

$\begin{gathered} 8 \cdot 9=72 \\ 72 \cdot 5=360 \\ 360 \cdot 7=2520 \end{gathered}$

Thus, the LCM of $5,6,7,8$ , and 9 is 2520 . Therefore: $n-1=2520 k$ $n=2520 k+1$

Given that the total number of candies lies between 4000 and 6000 : $4000 \leq 2520 k+1 \leq 6000$

$\begin{gathered} 3999 \leq 2520 k \leq 5999 \\ k \geq \frac{3999}{2520} \approx 1.587 \\ k \leq \frac{5999}{2520} \approx 2.380 \end{gathered}$

Since $k$ must be an integer, the possible value for $k$ is 2 . Substituting $k=2$ : $n=2520 \cdot 2+1=5041$

To find the largest number of candies per bag so that no candies are left when the total is below 4000, we consider the largest divisor of 2520 that is less than 4000 . The largest divisor of 2520 is 2520 itself (as 2520 is a factor of 5040 , and 5041 is not under 4000 ).

Thus, the largest number of candies in each bag, ensuring no candies are left, is: $\boxed{2520}$

Page

Toolbox

Search

2000 PMWC Problems/Problem T1

Contents

Problem

Solution 1

Solution 2

See Also