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 "2000 PMWC Problems/Problem T1"

(→‎Solution)
 
Line 2: Line 2:
 
A box contains <math>4000</math> to <math>6000</math> candies. When the candies are evenly distributed to <math>5</math>, <math>6</math>, <math>7</math>, <math>8</math>, or <math>9</math> 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 <math>4000</math> in each bag so that no candies are left?
 
A box contains <math>4000</math> to <math>6000</math> candies. When the candies are evenly distributed to <math>5</math>, <math>6</math>, <math>7</math>, <math>8</math>, or <math>9</math> 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 <math>4000</math> in each bag so that no candies are left?
  
−
==Solution==
+
==Solution 1==
 
If there is always one candy left over when the candies are evenly distributed to <math>5</math>, <math>6</math>, <math>7</math>, <math>8</math>, or <math>9</math> children, then there must also be exactly one candy left over when the candies are distributed to <math>LCM(5, 6, 7, 8, 9)</math> children. Since <math>LCM(5, 6, 7, 8, 9) = 2^3 * 3^2 * 5^1 * 7^1 = 2520</math>, the total number of candies can be expressed as <math>2520n + 1</math>, where <math>n</math> is any nonnegative integer. However, we know that there are between <math>4000</math> and <math>6000</math> candies, so the only viable value for <math>n</math> is <math>2</math>, meaning the total number of candies is <math>2520(2) + 1 = 5040 + 1 = 5041</math>.  
 
If there is always one candy left over when the candies are evenly distributed to <math>5</math>, <math>6</math>, <math>7</math>, <math>8</math>, or <math>9</math> children, then there must also be exactly one candy left over when the candies are distributed to <math>LCM(5, 6, 7, 8, 9)</math> children. Since <math>LCM(5, 6, 7, 8, 9) = 2^3 * 3^2 * 5^1 * 7^1 = 2520</math>, the total number of candies can be expressed as <math>2520n + 1</math>, where <math>n</math> is any nonnegative integer. However, we know that there are between <math>4000</math> and <math>6000</math> candies, so the only viable value for <math>n</math> is <math>2</math>, meaning the total number of candies is <math>2520(2) + 1 = 5040 + 1 = 5041</math>.  
  
 
The problem then asks us to find the largest number of candies below <math>4000</math> such that the candies are evenly distributed and no candies are left over. This is equivalent to asking what the largest factor of <math>5401</math> is that is less than <math>4000</math>. Since <math>5401 = 71^2</math>, the only factors of <math>5401</math> are <math>1</math>, <math>71</math>, and <math>5401</math>. Thus the answer is <math>\boxed{71}</math>.
 
The problem then asks us to find the largest number of candies below <math>4000</math> such that the candies are evenly distributed and no candies are left over. This is equivalent to asking what the largest factor of <math>5401</math> is that is less than <math>4000</math>. Since <math>5401 = 71^2</math>, the only factors of <math>5401</math> are <math>1</math>, <math>71</math>, and <math>5401</math>. Thus the answer is <math>\boxed{71}</math>.
  
 +
==Solution 2==
 +
Since <math>n \equiv 1(\bmod k)</math> for each <math>k</math> from the set <math>\{5,6,7,8,9\}</math>, we know that:
 +
<cmath>
 +
\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}
 +
</cmath>
 +
Prime factorizations:
 +
<cmath>
 +
\begin{gathered}
 +
5=5 \\
 +
6=2 \cdot 3 \\
 +
7=7 \\
 +
8=2^3 \\
 +
9=3^2
 +
\end{gathered}
 +
</cmath>
 +
 +
The LCM is determined by taking the highest power of each prime that appears in the factorizations:
 +
<cmath>
 +
\mathrm{LCM}=2^3 \cdot 3^2 \cdot 5 \cdot 7=8 \cdot 9 \cdot 5 \cdot 7
 +
</cmath>
 +
 +
<cmath>
 +
\begin{gathered}
 +
8 \cdot 9=72 \\
 +
72 \cdot 5=360 \\
 +
360 \cdot 7=2520
 +
\end{gathered}
 +
</cmath>
 +
 +
Thus, the LCM of <math>5,6,7,8</math>, and 9 is 2520 . Therefore:
 +
<cmath>
 +
n-1=2520 k
 +
</cmath>
 +
<cmath>
 +
n=2520 k+1
 +
</cmath>
 +
 +
Given that the total number of candies lies between 4000 and 6000 :
 +
<cmath>
 +
4000 \leq 2520 k+1 \leq 6000
 +
</cmath>
 +
 +
<cmath>
 +
\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}
 +
</cmath>
 +
 +
Since <math>k</math> must be an integer, the possible value for <math>k</math> is 2 . Substituting <math>k=2</math> :
 +
<cmath>
 +
n=2520 \cdot 2+1=5041
 +
</cmath>
 +
 +
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:
 +
<cmath>
 +
\boxed{2520}
 +
</cmath>
 
==See Also==
 
==See Also==
 
Back to test: https://artofproblemsolving.com/wiki/index.php/2000_PMWC_Problems
 
Back to test: https://artofproblemsolving.com/wiki/index.php/2000_PMWC_Problems

Latest revision as of 15:44, 24 May 2024

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}\]

See Also

Back to test: https://artofproblemsolving.com/wiki/index.php/2000_PMWC_Problems

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2000_PMWC_Problems/Problem_T1&oldid=219640"