https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Donutsman&feedformat=atomAoPS Wiki - User contributions [en]2024-03-29T10:12:53ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2007_AMC_10A_Problems/Problem_23&diff=1951842007 AMC 10A Problems/Problem 232023-07-03T18:20:13Z<p>Donutsman: /* Solution 2 */</p>
<hr />
<div>== Problem ==<br />
How many [[ordered pair]]s <math>(m,n)</math> of positive [[integer]]s, with <math>m \ge n</math>, have the property that their squares differ by <math>96</math>? <br />
<br />
<math>\text{(A)}\ 3 \qquad \text{(B)}\ 4 \qquad \text{(C)}\ 6 \qquad \text{(D)}\ 9 \qquad \text{(E)}\ 12</math><br />
<br />
==Solution 1==<br />
<cmath>m^2 - n^2 = (m+n)(m-n) = 96 = 2^{5} \cdot 3</cmath> <br />
<br />
For every two factors <math>xy = 96</math>, we have <math>m+n=x, m-n=y \Longrightarrow m = \frac{x+y}{2}, n = \frac{x-y}{2}</math>. It follows that the number of ordered pairs <math>(m,n)</math> is given by the number of ordered pairs <math>(x,y): xy=96, x > y > 0</math>. There are <math>(5+1)(1+1) = 12</math> factors of <math>96</math>, which give us six pairs <math>(x,y)</math>. However, since <math>m,n</math> are positive integers, we also need that <math>\frac{x+y}{2}, \frac{x-y}{2}</math> are positive integers, so <math>x</math> and <math>y</math> must have the same [[parity]]. Thus we exclude the factors <math>(x,y) = (1,96)(3,32)</math>, and we are left with <math>4</math> pairs <math>\mathrm{(B)}</math>.<br />
==Solution 2==<br />
<br />
<br />
Similarly to the solution above, write <math>96</math> as <math>2^5\cdot3^1</math>. To find the number of distinct factors, add <math>1</math> to both exponents and multiply, which gives us <math>6\cdot2=12</math> factors. Divide by <math>2</math> since <math>m</math> must be greater than or equal to <math>n</math>. We don't need to worry about <math>m</math> and <math>n</math> being equal because <math>96</math> is not a perfect square. Finally, subtract the two cases above for the same reason to get <math>\mathrm{(B)}</math>.<br />
<br />
== Solution 3 ==<br />
Find all of the factor pairs of <math>96</math>: <math>(1,96),(2,48),(3,32),(4,24),(6,16),(8,12).</math> You can eliminate <math>(1,96)</math> and (<math>3,32)</math> because you cannot have two numbers add to be an even number and have an odd difference at the same time without them being a decimal. You only have <math>4</math> pairs left, so the answer is <math>\boxed{\textbf{(B)}\; 4}</math>.<br />
<br />
~HelloWorld21<br />
<br />
== See also ==<br />
{{AMC10 box|year=2007|ab=A|num-b=22|num-a=24}}<br />
<br />
[[Category:Introductory Number Theory Problems]]<br />
{{MAA Notice}}</div>Donutsmanhttps://artofproblemsolving.com/wiki/index.php?title=2007_AMC_10A_Problems/Problem_23&diff=1951792007 AMC 10A Problems/Problem 232023-07-03T18:18:39Z<p>Donutsman: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
How many [[ordered pair]]s <math>(m,n)</math> of positive [[integer]]s, with <math>m \ge n</math>, have the property that their squares differ by <math>96</math>? <br />
<br />
<math>\text{(A)}\ 3 \qquad \text{(B)}\ 4 \qquad \text{(C)}\ 6 \qquad \text{(D)}\ 9 \qquad \text{(E)}\ 12</math><br />
<br />
==Solution 1==<br />
<cmath>m^2 - n^2 = (m+n)(m-n) = 96 = 2^{5} \cdot 3</cmath> <br />
<br />
For every two factors <math>xy = 96</math>, we have <math>m+n=x, m-n=y \Longrightarrow m = \frac{x+y}{2}, n = \frac{x-y}{2}</math>. It follows that the number of ordered pairs <math>(m,n)</math> is given by the number of ordered pairs <math>(x,y): xy=96, x > y > 0</math>. There are <math>(5+1)(1+1) = 12</math> factors of <math>96</math>, which give us six pairs <math>(x,y)</math>. However, since <math>m,n</math> are positive integers, we also need that <math>\frac{x+y}{2}, \frac{x-y}{2}</math> are positive integers, so <math>x</math> and <math>y</math> must have the same [[parity]]. Thus we exclude the factors <math>(x,y) = (1,96)(3,32)</math>, and we are left with <math>4</math> pairs <math>\mathrm{(B)}</math>.<br />
===Solution 2===<br />
<br />
<br />
Similarly to the solution above, write <math>96</math> as <math>2^5\cdot3^1</math>. To find the number of distinct factors, add <math>1</math> to both exponents and multiply, which gives us <math>6\cdot2=12</math> factors. Divide by <math>2</math> since <math>m</math> must be greater than or equal to <math>n</math>. We don't need to worry about <math>m</math> and <math>n</math> being equal because <math>96</math> is not a perfect square. Finally, subtract the two cases above for the same reason to get <math>\mathrm{(B)}</math>.<br />
<br />
== Solution 3 ==<br />
Find all of the factor pairs of <math>96</math>: <math>(1,96),(2,48),(3,32),(4,24),(6,16),(8,12).</math> You can eliminate <math>(1,96)</math> and (<math>3,32)</math> because you cannot have two numbers add to be an even number and have an odd difference at the same time without them being a decimal. You only have <math>4</math> pairs left, so the answer is <math>\boxed{\textbf{(B)}\; 4}</math>.<br />
<br />
~HelloWorld21<br />
<br />
== See also ==<br />
{{AMC10 box|year=2007|ab=A|num-b=22|num-a=24}}<br />
<br />
[[Category:Introductory Number Theory Problems]]<br />
{{MAA Notice}}</div>Donutsmanhttps://artofproblemsolving.com/wiki/index.php?title=2007_AMC_10A_Problems/Problem_23&diff=1951732007 AMC 10A Problems/Problem 232023-07-03T18:18:11Z<p>Donutsman: /* Solution 1 */</p>
<hr />
<div>== Problem ==<br />
How many [[ordered pair]]s <math>(m,n)</math> of positive [[integer]]s, with <math>m \ge n</math>, have the property that their squares differ by <math>96</math>? <br />
<br />
<math>\text{(A)}\ 3 \qquad \text{(B)}\ 4 \qquad \text{(C)}\ 6 \qquad \text{(D)}\ 9 \qquad \text{(E)}\ 12</math><br />
<br />
==Solution 1==<br />
<cmath>m^2 - n^2 = (m+n)(m-n) = 96 = 2^{5} \cdot 3</cmath> <br />
<br />
For every two factors <math>xy = 96</math>, we have <math>m+n=x, m-n=y \Longrightarrow m = \frac{x+y}{2}, n = \frac{x-y}{2}</math>. It follows that the number of ordered pairs <math>(m,n)</math> is given by the number of ordered pairs <math>(x,y): xy=96, x > y > 0</math>. There are <math>(5+1)(1+1) = 12</math> factors of <math>96</math>, which give us six pairs <math>(x,y)</math>. However, since <math>m,n</math> are positive integers, we also need that <math>\frac{x+y}{2}, \frac{x-y}{2}</math> are positive integers, so <math>x</math> and <math>y</math> must have the same [[parity]]. Thus we exclude the factors <math>(x,y) = (1,96)(3,32)</math>, and we are left with <math>4</math> pairs <math>\mathrm{(B)}</math>.<br />
<br />
== Solution 3 ==<br />
Find all of the factor pairs of <math>96</math>: <math>(1,96),(2,48),(3,32),(4,24),(6,16),(8,12).</math> You can eliminate <math>(1,96)</math> and (<math>3,32)</math> because you cannot have two numbers add to be an even number and have an odd difference at the same time without them being a decimal. You only have <math>4</math> pairs left, so the answer is <math>\boxed{\textbf{(B)}\; 4}</math>.<br />
<br />
~HelloWorld21<br />
<br />
== See also ==<br />
{{AMC10 box|year=2007|ab=A|num-b=22|num-a=24}}<br />
<br />
[[Category:Introductory Number Theory Problems]]<br />
{{MAA Notice}}</div>Donutsmanhttps://artofproblemsolving.com/wiki/index.php?title=Chicken_McNugget_Theorem&diff=169385Chicken McNugget Theorem2022-01-05T20:11:20Z<p>Donutsman: /* Problems */</p>
<hr />
<div>The '''Chicken McNugget Theorem''' (or '''Postage Stamp Problem''' or '''Frobenius Coin Problem''') states that for any two [[relatively prime]] [[positive integer]]s <math>m,n</math>, the greatest integer that cannot be written in the form <math>am + bn</math> for [[nonnegative]] integers <math>a, b</math> is <math>mn-m-n</math>.<br />
<br />
A consequence of the theorem is that there are exactly <math>\frac{(m - 1)(n - 1)}{2}</math> positive integers which cannot be expressed in the form <math>am + bn</math>. The proof is based on the fact that in each pair of the form <math>(k, mn-m-n-k)</math>, exactly one element is expressible.<br />
<br />
== Origins ==<br />
There are many stories surrounding the origin of the Chicken McNugget theorem. However, the most popular by far remains that of the Chicken McNugget. Originally, McDonald's sold its nuggets in packs of 9 and 20. Math enthusiasts were curious to find the largest number of nuggets that could not have been bought with these packs, thus creating the Chicken McNugget Theorem (the answer worked out to be 151 nuggets). The Chicken McNugget Theorem has also been called the Frobenius Coin Problem or the Frobenius Problem, after German mathematician Ferdinand Frobenius inquired about the largest amount of currency that could not have been made with certain types of coins.<br />
<br />
<br />
<br />
<br />
<br />
==Proof Without Words==<br />
<math>\begin{array}{ccccccc}<br />
0\mod{m}&1\mod{m}&2\mod{m}&...&...&...&(m-1)\mod{m}\\<br />
\hline<br />
\cancel{0n}&1&2&&...&&m-1\\<br />
\cancel{0n+m}&...&&\vdots&&...&\\<br />
\cancel{0n+2m}&...&&\cancel{1n}&&...&\\<br />
\cancel{0n+3m}&&&\cancel{1n+m}&&\vdots&\\<br />
\cancel{0n+4m}&&&\cancel{1n+2m}&&\cancel{2n}&\\<br />
\cancel{0n+5m}&&&\cancel{1n+3m}&&\cancel{2n+m}&\\<br />
\vdots&&&\vdots&&\vdots&\\<br />
\cancel{\qquad}&\cancel{\qquad}&\cancel{ \qquad}&\cancel{ \qquad}&\mathbf{(m-1)n-m}&\cancel{\qquad }&\cancel{\qquad }\\<br />
\cancel{\qquad}&\cancel{\qquad}&\cancel{ \qquad}&\cancel{ \qquad}&\cancel{(m-1)n}&\cancel{\qquad }&\cancel{\qquad }<br />
\end{array}</math><br />
<br />
==Proof 1==<br />
<b>Definition</b>. An integer <math>N \in \mathbb{Z}</math> will be called <i>purchasable</i> if there exist nonnegative integers <math>a,b</math> such that <math>am+bn = N</math>.<br />
<br />
We would like to prove that <math>mn-m-n</math> is the largest non-purchasable integer. We are required to show that: <br />
<br />
(1) <math>mn-m-n</math> is non-purchasable<br />
<br />
(2) Every <math>N > mn-m-n</math> is purchasable<br />
<br />
Note that all purchasable integers are nonnegative, thus the set of non-purchasable integers is nonempty.<br />
<br />
<b>Lemma</b>. Let <math>A_{N} \subset \mathbb{Z} \times \mathbb{Z}</math> be the set of solutions <math>(x,y)</math> to <math>xm+yn = N</math>. Then <math>A_{N} = \{(x+kn,y-km) \;:\; k \in \mathbb{Z}\}</math> for any <math>(x,y) \in A_{N}</math>.<br />
<br />
<i>Proof</i>: By [[Bezout's Lemma]], there exist integers <math>x',y'</math> such that <math>x'm+y'n = 1</math>. Then <math>(Nx')m+(Ny')n = N</math>. Hence <math>A_{N}</math> is nonempty. It is easy to check that <math>(Nx'+kn,Ny'-km) \in A_{N}</math> for all <math>k \in \mathbb{Z}</math>. We now prove that there are no others. Suppose <math>(x_{1},y_{1})</math> and <math>(x_{2},y_{2})</math> are solutions to <math>xm+yn=N</math>. Then <math>x_{1}m+y_{1}n = x_{2}m+y_{2}n</math> implies <math>m(x_{1}-x_{2}) = n(y_{2}-y_{1})</math>. Since <math>m</math> and <math>n</math> are coprime and <math>m</math> divides <math>n(y_{2}-y_{1})</math>, <math>m</math> divides <math>y_{2}-y_{1}</math> and <math>y_{2} \equiv y_{1} \pmod{m}</math>. Similarly <math>x_{2} \equiv x_{1} \pmod{n}</math>. Let <math>k_{1},k_{2}</math> be integers such that <math>x_{2}-x_{1} = k_{1}n</math> and <math>y_{2}-y_{1} = k_{2}m</math>. Then <math>m(-k_{1}n) = n(k_{2}m)</math> implies <math>k_{1} = -k_{2}.</math> We have the desired result. <math>\square</math><br />
<br />
<b>Lemma</b>. For any integer <math>N</math>, there exists unique <math>(a_{N},b_{N}) \in \mathbb{Z} \times \{0,1,\ldots,m-1\}</math> such that <math>a_{N}m + b_{N}n = N</math>.<br />
<br />
<i>Proof</i>: By the division algorithm, there exists one and only one <math>k</math> such that <math>0 \le y-km \le m-1</math>. <math>\square</math><br />
<br />
<b>Lemma</b>. <math>N</math> is purchasable if and only if <math>a_{N} \ge 0</math>.<br />
<br />
<i>Proof</i>: If <math>a_{N} \ge 0</math>, then we may simply pick <math>(a,b) = (a_{N},b_{N})</math> so <math>N</math> is purchasable. If <math>a_{N} < 0</math>, then <math>a_{N}+kn < 0</math> if <math>k \le 0</math> and <math>b_{N}-km < 0</math> if <math>k > 0</math>, hence at least one coordinate of <math>(a_{N}+kn,b_{N}-km)</math> is negative for all <math>k \in \mathbb{Z}</math>. Thus <math>N</math> is not purchasable. <math>\square</math><br />
<br />
Thus the set of non-purchasable integers is <math>\{xm+yn \;:\; x<0,0 \le y \le m-1\}</math>. We would like to find the maximum of this set. <br />
Since both <math>m,n</math> are positive, the maximum is achieved when <math>x = -1</math> and <math>y = m-1</math> so that <math>xm+yn = (-1)m+(m-1)n = mn-m-n</math>.<br />
<br />
==Proof 2==<br />
We start with this statement taken from [[Fermat%27s_Little_Theorem#Proof_2_.28Inverses.29|Proof 2 of Fermat's Little Theorem]]:<br />
<br />
"Let <math>S = \{1,2,3,\cdots, p-1\}</math>. Then, we claim that the set <math>a \cdot S</math>, consisting of the product of the elements of <math>S</math> with <math>a</math>, taken modulo <math>p</math>, is simply a permutation of <math>S</math>. In other words, <br />
<br />
<center><cmath>S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.</cmath></center><br><br />
<br />
Clearly none of the <math>ia</math> for <math>1 \le i \le p-1</math> are divisible by <math>p</math>, so it suffices to show that all of the elements in <math>a \cdot S</math> are distinct. Suppose that <math>ai \equiv aj \pmod{p}</math> for <math>i \neq j</math>. Since <math>\text{gcd}\, (a,p) = 1</math>, by the cancellation rule, that reduces to <math>i \equiv j \pmod{p}</math>, which is a contradiction."<br />
<br />
Because <math>m</math> and <math>n</math> are coprime, we know that multiplying the residues of <math>m</math> by <math>n</math> simply permutes these residues. Each of these permuted residues is purchasable (using the definition from Proof 1), because, in the form <math>am+bn</math>, <math>a</math> is <math>0</math> and <math>b</math> is the original residue. We now prove the following lemma.<br />
<br />
<b>Lemma</b>: For any nonnegative integer <math>c < m</math>, <math>cn</math> is the least purchasable number <math>\equiv cn \bmod m</math>.<br />
<br />
<i>Proof</i>: Any number that is less than <math>cn</math> and congruent to it <math>\bmod m</math> can be represented in the form <math>cn-dm</math>, where <math>d</math> is a positive integer. If this is purchasable, we can say <math>cn-dm=am+bn</math> for some nonnegative integers <math>a, b</math>. This can be rearranged into <math>(a+d)m=(c-b)n</math>, which implies that <math>(a+d)</math> is a multiple of <math>n</math> (since <math>\gcd(m, n)=1</math>). We can say that <math>(a+d)=gn</math> for some positive integer <math>g</math>, and substitute to get <math>gmn=(c-b)n</math>. Because <math>c < m</math>, <math>(c-b)n < mn</math>, and <math>gmn < mn</math>. We divide by <math>mn</math> to get <math>g<1</math>. However, we defined <math>g</math> to be a positive integer, and all positive integers are greater than or equal to <math>1</math>. Therefore, we have a contradiction, and <math>cn</math> is the least purchasable number congruent to <math>cn \bmod m</math>. <math>\square</math><br />
<br />
This means that because <math>cn</math> is purchasable, every number that is greater than <math>cn</math> and congruent to it <math>\bmod m</math> is also purchasable (because these numbers are in the form <math>am+bn</math> where <math>b=c</math>). Another result of this Lemma is that <math>cn-m</math> is the greatest number <math>\equiv cn \bmod m</math> that is not purchasable. <math>c \leq m-1</math>, so <math>cn-m \leq (m-1)n-m=mn-m-n</math>, which shows that <math>mn-m-n</math> is the greatest number in the form <math>cn-m</math>. Any number greater than this and congruent to some <math>cn \bmod m</math> is purchasable, because that number is greater than <math>cn</math>. All numbers are congruent to some <math>cn</math>, and thus all numbers greater than <math>mn-m-n</math> are purchasable.<br />
<br />
Putting it all together, we can say that for any coprime <math>m</math> and <math>n</math>, <math>mn-m-n</math> is the greatest number not representable in the form <math>am + bn</math> for nonnegative integers <math>a, b</math>. <math>\square</math><br />
<br />
==Corollary==<br />
This corollary is based off of Proof 2, so it is necessary to read that proof before this corollary. We prove the following lemma.<br />
<br />
<b>Lemma:</b> For any integer <math>k</math>, exactly one of the integers <math>k</math>, <math>mn-m-n-k</math> is not purchasable.<br />
<br />
<i>Proof</i>: Because every number is congruent to some residue of <math>m</math> permuted by <math>n</math>, we can set <math>k \equiv cn \bmod m</math> for some <math>c</math>. We can break this into two cases.<br />
<br />
<i>Case 1</i>: <math>k \leq cn-m</math>. This implies that <math>k</math> is not purchasable, and that <math>mn-m-n-k \geq mn-m-n-(cn-m) = n(m-1-c)</math>. <math>n(m-1-c)</math> is a permuted residue, and a result of the lemma in Proof 2 was that a permuted residue is the least number congruent to itself <math>\bmod m</math> that is purchasable. Therefore, <math>mn-m-n-k \equiv n(m-1-c) \bmod m</math> and <math>mn-m-n-k \geq n(m-1-c)</math>, so <math>mn-m-n-k</math> is purchasable.<br />
<br />
<i>Case 2</i>: <math>k > cn-m</math>. This implies that <math>k</math> is purchasable, and that <math>mn-m-n-k < mn-m-n-(cn-m) = n(m-1-c)</math>. Again, because <math>n(m-1-c)</math> is the least number congruent to itself <math>\bmod m</math> that is purchasable, and because <math>mn-m-n-k \equiv n(m-1-c) \bmod m</math> and <math>mn-m-n-k < n(m-1-c)</math>, <math>mn-m-n-k</math> is not purchasable.<br />
<br />
We now limit the values of <math>k</math> to all integers <math>0 \leq k \leq \frac{mn-m-n}{2}</math>, which limits the values of <math>mn-m-n-k</math> to <math>mn-m-n \geq mn-m-n-k \geq \frac{mn-m-n}{2}</math>. Because <math>m</math> and <math>n</math> are coprime, only one of them can be a multiple of <math>2</math>. Therefore, <math>mn-m-n \equiv (0)(1)-0-1 \equiv -1 \equiv 1 \bmod 2</math>, showing that <math>\frac{mn-m-n}{2}</math> is not an integer and that <math>\frac{mn-m-n-1}{2}</math> and <math>\frac{mn-m-n+1}{2}</math> are integers. We can now set limits that are equivalent to the previous on the values of <math>k</math> and <math>mn-m-n-k</math> so that they cover all integers form <math>0</math> to <math>mn-m-n</math> without overlap: <math>0 \leq k \leq \frac{mn-m-n-1}{2}</math> and <math>\frac{mn-m-n+1}{2} \leq mn-m-n-k \leq mn-m-n</math>. There are <math>\frac{mn-m-n-1}{2}+1=\frac{(m-1)(n-1)}{2}</math> values of <math>k</math>, and each is paired with a value of <math>mn-m-n-k</math>, so we can make <math>\frac{(m-1)(n-1)}{2}</math> different ordered pairs of the form <math>(k, mn-m-n-k)</math>. The coordinates of these ordered pairs cover all integers from <math>0</math> to <math>mn-m-n</math> inclusive, and each contains exactly one not-purchasable integer, so that means that there are <math>\frac{(m-1)(n-1)}{2}</math> different not-purchasable integers from <math>0</math> to <math>mn-m-n</math>. All integers greater than <math>mn-m-n</math> are purchasable, so that means there are a total of <math>\frac{(m-1)(n-1)}{2}</math> integers <math>\geq 0</math> that are not purchasable.<br />
<br />
In other words, for every pair of coprime integers <math>m, n</math>, there are exactly <math>\frac{(m-1)(n-1)}{2}</math> nonnegative integers that cannot be represented in the form <math>am + bn</math> for nonnegative integers <math>a, b</math>. <math>\square</math><br />
<br />
==Generalization==<br />
If <math>m</math> and <math>n</math> are not relatively prime, then we can simply rearrange <math>am+bn</math> into the form<br />
<cmath>\gcd(m,n) \left( a\frac{m}{\gcd(m,n)}+b\frac{n}{\gcd(m,n)} \right)</cmath><br />
<math>\frac{m}{\gcd(m,n)}</math> and <math>\frac{n}{\gcd(m,n)}</math> are relatively prime, so we apply Chicken McNugget to find a bound<br />
<cmath>\frac{mn}{\gcd(m,n)^{2}}-\frac{m}{\gcd(m,n)}-\frac{n}{\gcd(m,n)}</cmath><br />
We can simply multiply <math>\gcd(m,n)</math> back into the bound to get<br />
<cmath>\frac{mn}{\gcd(m,n)}-m-n=\textrm{lcm}(m, n)-m-n</cmath><br />
Therefore, all multiples of <math>\gcd(m, n)</math> greater than <math>\textrm{lcm}(m, n)-m-n</math> are representable in the form <math>am+bn</math> for some positive integers <math>a, b</math>.<br />
<br />
=Problems=<br />
<br />
===Introductory===<br />
*Marcy buys paint jars in containers of <math>2</math> and <math>7</math>. What's the largest number of paint jars that Marcy can't obtain? <br />
<br />
Answer: <math>5</math> containers<br />
<br />
*Bay Area Rapid food sells chicken nuggets. You can buy packages of <math>11</math> or <math>7</math>. What is the largest integer <math>n</math> such that there is no way to buy exactly <math>n</math> nuggets? Can you Generalize ? (Source: Art of Problem Solving) <br />
<br />
Answer: <math>n=59</math> <br />
<br />
*If a game of American Football has only scores of field goals (<math>3</math> points) and touchdowns with the extra point (<math>7</math> points), then what is the greatest score that cannot be the score of a team in this football game (ignoring time constraints)?<br />
<br />
Answer: <math>11</math> points<br />
<br />
*The town of Hamlet has <math>3</math> people for each horse, <math>4</math> sheep for each cow, and <math>3</math> ducks for each person. Which of the following could not possibly be the total number of people, horses, sheep, cows, and ducks in Hamlet?<br />
<br />
<math>\textbf{(A) }41\qquad\textbf{(B) }47\qquad\textbf{(C) }59\qquad\textbf{(D) }61\qquad\textbf{(E) }66</math> (Source: [[2015 AMC 10B Problems/Problem 15|AMC 10B 2015 Problem 15]])<br />
<br />
Answer: <math>47\qquad\textbf{(B) }</math><br />
<br />
===Intermediate===<br />
*Ninety-four bricks, each measuring <math>4''\times10''\times19'',</math> are to stacked one on top of another to form a tower 94 bricks tall. Each brick can be oriented so it contributes <math>4''\,</math> or <math>10''\,</math> or <math>19''\,</math> to the total height of the tower. How many different tower heights can be achieved using all ninety-four of the bricks? (Source: [[1994 AIME Problems/Problem 11|AIME]])<br />
<br />
*Find the sum of all positive integers <math>n</math> such that, given an unlimited supply of stamps of denominations <math>5,n,</math> and <math>n+1</math> cents, <math>91</math> cents is the greatest postage that cannot be formed. (Source: [[2019 AIME II Problems/Problem 14|AIME II 2019 Problem 14]])<br />
<br />
===Olympiad===<br />
*On the real number line, paint red all points that correspond to integers of the form <math>81x+100y</math>, where <math>x</math> and <math>y</math> are positive integers. Paint the remaining integer points blue. Find a point <math>P</math> on the line such that, for every integer point <math>T</math>, the reflection of <math>T</math> with respect to <math>P</math> is an integer point of a different colour than <math>T</math>. (Source: India TST)<br />
<br />
==See Also==<br />
*[[Theorem]]<br />
*[[Prime]]<br />
<br />
[[Category:Theorems]]<br />
[[Category:Number theory]]</div>Donutsmanhttps://artofproblemsolving.com/wiki/index.php?title=2017_AMC_8_Problems/Problem_16&diff=1345932017 AMC 8 Problems/Problem 162020-10-04T16:41:49Z<p>Donutsman: /* Solution 1 */</p>
<hr />
<div>==Problem 16==<br />
<br />
In the figure below, choose point <math>D</math> on <math>\overline{BC}</math> so that <math>\triangle ACD</math> and <math>\triangle ABD</math> have equal perimeters. What is the area of <math>\triangle ABD</math>?<br />
<asy>draw((0,0)--(4,0)--(0,3)--(0,0));<br />
label("$A$", (0,0), SW);<br />
label("$B$", (4,0), ESE);<br />
label("$C$", (0, 3), N);<br />
label("$3$", (0, 1.5), W);<br />
label("$4$", (2, 0), S);<br />
label("$5$", (2, 1.5), NE);</asy><br />
<br />
<math>\textbf{(A) }\frac{3}{4}\qquad\textbf{(B) }\frac{3}{2}\qquad\textbf{(C) }2\qquad\textbf{(D) }\frac{12}{5}\qquad\textbf{(E) }\frac{5}{2}</math><br />
<br />
==Solution 1==<br />
<br />
Essentially, we see that if we draw a line from point A to imaginary point D, that line would apply to both triangles. Let us say that <math>x</math> is the length of the line from B to D. So, the perimeter of <math>\triangle{ABD}</math> would be <math>\overline{AD} + 4 + x</math>, while the perimeter of <math>\triangle{ACD}</math> would be <math>\overline{AD} + 3 + (5 - x)</math>. Notice that we can find out <math>x</math> from these two equations. We can find out that <math>x = 2</math>, and because the height of the triangles is the same, the ratio of the areas is <math>2:3</math>, so that means that the area of <math>\triangle{ABD} = \frac{2 \cdot 6}{5} = \boxed{\textbf{(D) } \frac{12}{5}}</math>.<br />
<br />
==Solution 2==<br />
<br />
We know that the perimeters of the two small triangles are <math>3+CD+AD</math> and <math>4+BD+AD</math>. Setting both equal and using <math>BD+CD = 5</math>, we have <math>BD = 2</math> and <math>CD = 3</math>. Now, we simply have to find the area of <math>\triangle ABD</math>. Since <math>\frac{BD}{CD} = \frac{2}{3}</math>, we must have <math>\frac{[ABD]}{[ACD]} = 2/3</math>. Combining this with the fact that <math>[ABC] = [ABD] + [ACD] = \frac{3\cdot4}{2} = 6</math>, we get <math>[ABD] = \frac{2}{5}[ABC] = \frac{2}{5} \cdot 6 = \boxed{\textbf{(D) } \frac{12}{5}}</math><br />
<br />
==Solution 3== <br />
<br />
Since point <math>D</math> is on line <math>BC</math>, it will split it into <math>CD</math> and <math>DB</math>. Let <math>CD = 5 - x</math> and <math>DB = x</math>. Triangle <math>CAD</math> has side lengths <math>3, 5 - x, AD</math> and triangle <math>DAB</math> has side lengths <math>x, 4, AD</math>. Since both perimeters are equal, we have the equation <math>3 + 5 - x + AD = 4 + x + AD</math>. Eliminating <math>AD</math> and solving the resulting linear equation gives <math>x = 2</math>. Draw a perpendicular from point <math>D</math> to <math>AB</math>. Call the point of intersection <math>F</math>. Because angle <math>ABC</math> is common to both triangles <math>DBF</math> and <math>ABC</math>, and both are right triangles, both are similar. The hypotenuse of triangle <math>DBF</math> is 2, so the altitude must be <math>6/5</math> Because <math>DBF</math> and <math>ABD</math> share the same altitude, the height of <math>ABD</math> therefore must be <math>6/5</math>. The base of <math>ABD</math> is 4, so <math>[ABD] = \frac{1}{2} \cdot 4 \cdot \frac{6}{5} = \frac{12}{5} \implies \boxed{\textbf{(D) } \frac{12}{5}}</math><br />
<br />
==Solution 4==<br />
Using any preferred method, realize <math>BD = 2</math>. Since we are given a 3-4-5 right triangle, we know the value of <math>\sin(\angle ABC) = \frac{3}{5}</math>. Since we are given <math>AB = 4</math>, apply the Sine Area Formula to get <math>\frac{1}{2} \cdot 4 \cdot 2 \cdot \frac{3}{5} = \boxed{\textbf{(D) } \frac{12}{5}}</math>.<br />
<br />
==See Also==<br />
{{AMC8 box|year=2017|num-b=15|num-a=17}}<br />
<br />
{{MAA Notice}}</div>Donutsmanhttps://artofproblemsolving.com/wiki/index.php?title=2016_AMC_8_Problems/Problem_25&diff=1195562016 AMC 8 Problems/Problem 252020-03-16T23:05:50Z<p>Donutsman: /* Note */</p>
<hr />
<div>A semicircle is inscribed in an isosceles triangle with base <math>16</math> and height <math>15</math> so that the diameter of the semicircle is contained in the base of the triangle as shown. What is the radius of the semicircle?<br />
<br />
<asy>draw((0,0)--(8,15)--(16,0)--(0,0));<br />
draw(arc((8,0),7.0588,0,180));</asy><br />
<br />
<math>\textbf{(A) }4 \sqrt{3}\qquad\textbf{(B) } \dfrac{120}{17}\qquad\textbf{(C) }10\qquad\textbf{(D) }\dfrac{17\sqrt{2}}{2}\qquad \textbf{(E)} \dfrac{17\sqrt{3}}{2}</math><br />
<br />
<br />
==Note==<br />
There are many solutions here, and all of them are equally good. For your own benefit, look at all of the solutions, as they employ many unique techniques to get to the final answer.<br />
<br />
==Solution 1==<br />
<asy><br />
pair A, B, C, D; <br />
A=(0,0); <br />
B=(16,0); <br />
C=(8,15); <br />
D=B/2; <br />
draw(A--B--C--cycle); <br />
draw(C--D); <br />
draw(arc(D,120/17,0,180)); <br />
draw(rightanglemark(B,D,C,25)); <br />
label("$A$",A,SW); <br />
label("$B$",B,SE); <br />
label("$C$",C,N); <br />
label("$D$",D,S); <br />
label("$8$",(A+D)/2,S);<br />
label("$15$",(C+D)/2,NE);<br />
label("$17$",(A+C)/2,W);<br />
</asy><br />
<br />
First, we draw a line perpendicular to the base of the triangle and cut the triangle in half. The base of the resulting right triangle would be 8, and the height would be 15. Using the Pythagorean theorem, we can find the length of the hypotenuse, which would be 17. Using the two legs of the right angle, we can find the area of the right triangle, <math>60</math>. <math>\frac{60}{17}</math> times <math>2</math> results in the radius, which is the height of the right triangle when using the hypotenuse as the base. The answer is <math> \boxed{\textbf{(B) }\frac{120}{17}}</math>.<br />
<br />
==Solution 2: Similar Triangles==<br />
<asy> pair A, B, C, D, E; A=(0,0); B=(16,0); C=(8,15); D=B/2; E=(64/17*8/17, 64/17*15/17); draw(A--B--C--cycle); draw(C--D); draw(D--E); draw(arc(D,120/17,0,180)); draw(rightanglemark(B,D,C,25)); draw(rightanglemark(A,E,D,25)); label("$A$",A,SW); label("$B$",B,SE); label("$C$",C,N); label("$D$",D,S); label("$E$",E,NW);</asy><br />
Let's call the triangle <math>\triangle ABC,</math> where <math>AB=16</math> and <math> AC=BC.</math> Let's say that <math>D</math> is the midpoint of <math>AB</math> and <math>E</math> is the point where <math>AC</math> is tangent to the semicircle. We could also use <math>BC</math> instead of <math>AC</math> because of symmetry.<br />
<br />
Notice that <math>\triangle ACD \cong \triangle BCD,</math> and are both 8-15-17 right triangles. We also know that we create a right angle with the intersection of the radius and a tangent line of a circle (or part of a circle). So, by <math>AA</math> similarity, <math>\triangle AED \sim \triangle ADC,</math> with <math>\angle EAD \cong \angle DAC</math> and <math> \angle CDA \cong \angle DEA.</math> This similarity means that we can create a proportion: <math>\frac{AD}{AC}=\frac{DE}{CD}.</math> We plug in <math>AD=\frac{AB}{2}=8, AC=17,</math> and <math>CD=15.</math> After we multiply both sides by <math>15,</math> we get <math>DE=\frac{8}{17} \cdot 15= \boxed{\textbf{(B) }\frac{120}{17}}.</math><br />
<br />
(By the way, we could also use <math>\triangle DEC \sim \triangle ADC.</math>)<br />
<br />
==Solution 3: Inscribed Circle==<br />
<br />
<br />
<asy> pair A, B, C, D, M; B=(0,0); D=(16,0); A=(8,15); C=(8,-15); M=D/2; draw(B--D--A--cycle); draw(A--M); draw(arc(M,120/17,0,180)); draw(rightanglemark(D,M,A,25)); draw(rightanglemark(B,M,25)); label("$B$",B,SW); label("$D$",D,SE); label("$A$",A,N); label("$M$",M,S); label("$C$",C,S); draw((0,0)--(8,-15)--(16,0)--(0,0)); draw(arc((8,0),7.0588,0,360));</asy><br />
<br />
We'll call this triangle <math>\triangle ABD</math>. Let the midpoint of base <math>BD</math> be <math>M</math>. Divide the triangle in half by drawing a line from <math>A</math> to <math>M</math>. Half the base of <math>\triangle ABD</math> is <math>\frac{16}{2} = 8</math>. The height is <math>15</math>, which is given in the question. Using the Pythagorean Triple <math>8</math>-<math>15</math>-<math>17</math>, the length of each of the legs (<math>AB</math> and <math>DA</math>) is 17.<br />
<br />
Reflect the triangle over its base. This will create an inscribed circle in a rhombus <math>ABCD</math>. Because <math>AB \cong DA</math>, <math>BC \cong CD</math>. Therefore <math>AB = BC = CD = DA</math>.<br />
<br />
The semiperimeter <math>s</math> of the rhombus is <math>\frac{AB + BC + CD + DA}{2} = \frac{(17)(4)}{2} = 34</math>. Since the area of <math>\triangle ABD</math> is <math>\frac{bh}{2}</math>, the area <math>[ABCD]</math> of the rhombus is twice that, which is <math>bh = (16)(15) = 240</math>.<br />
<br />
The [https://en.wikipedia.org/wiki/Incircle_and_excircles_of_a_triangle#Incircle Formula for the Incircle of a Quadrilateral] is <math>s</math><math>r</math> = <math>[ABCD]</math>. Substituting the semiperimeter and area into the equation, <math>34r = 240</math>. Solving this, <math>r = \frac{240}{34}</math> = <math>\boxed{\textbf{(B) }\frac{120}{17}}</math>.<br />
<br />
==Solution 4: Inscribed Circle==<br />
<br />
Noting that we have a 8-15-17 triangle, we can find <math>AE</math> and <math>CE.</math> Let <math>AE=x</math>, <math>CE=17-x.</math> Then by similar triangles (or "Altitude on Hypotenuse") we have <math>15^2=x*17.</math> Thus, <math>AE=x=225/17, CE=64/17.</math> Now again by "Altitude on Hypotenuseā€¯, <math>r=\sqrt{AE*CE}.</math> Therefore <math>r=\boxed{\textbf{(B) }\frac{120}{17}}</math>.<br />
<br />
==Solution 5: Simple Trigonometry==<br />
Note: This solution uses [http://artofproblemsolving.com/wiki/index.php?title=Trigonometry#Word Trigonometric Concepts]<br />
<asy><br />
pair A, B, C, D; <br />
A=(0,0); <br />
B=(16,0); <br />
C=(8,15); <br />
D=B/2; <br />
draw(A--B--C--cycle); <br />
draw(C--D); <br />
draw(arc(D,120/17,0,180)); <br />
draw(rightanglemark(B,D,C,25)); <br />
label("$A$",A,SW); <br />
label("$B$",B,SE); <br />
label("$C$",C,N); <br />
label("$D$",D,S); <br />
</asy><br />
<br />
Denote the bottom left vertex of the isosceles triangle to be <math>A</math><br />
<br />
Denote the bottom right vertex of the isosceles triangle to be <math>B</math><br />
<br />
Denote the top vertex of the isosceles triangle to be <math>C</math><br />
<br />
Drop an altitude from <math>C</math> to side <math>AB</math>. Denote the foot of intersection to be <math>D</math>.<br />
<br />
By the Pythagorean Theorem, <math>AC=17</math>.<br />
<br />
Now, we see that <math>\sin{A}=\frac{15}{17}</math>.<br />
<br />
This implies that <math>\sin{A}=\frac{r}{8}</math> (r=radius of semicircle).<br />
<br />
Hence, <math>r=\boxed{\textbf{(B) }\frac{120}{17}}</math>.<br />
<br />
==Solution 6: Area==<br />
<br />
<asy> pair A, B, C, D, E; A=(0,0); B=(16,0); C=(8,15); D=B/2; E=(64/17*8/17, 64/17*15/17); draw(A--B--C--cycle); draw(C--D); draw(D--E); draw(arc(D,120/17,0,180)); draw(rightanglemark(B,D,C,25)); draw(rightanglemark(A,E,D,25)); label("$A$",A,SW); label("$B$",B,SE); label("$C$",C,N); label("$D$",D,S); label("$E$",E,NW);</asy><br />
Credits for Asymptote go to whoever wrote this diagram up in Solution 2. <br />
<br />
There are two ways to find the area of <math>\triangle ABC</math>. The first way is the most obvious, and that is to multiply the base times the height (<math>16\cdot15</math>) and then divide it by two. The second way is, in a way, a little more complex. Note that <math>\triangle ACD</math> and <math>\triangle BCD</math> are congruent. This means that if we find the area of one triangle, we can just multiply it's area by 2 and we've found the area of the larger triangle <math>ABC</math>. But since we always divide by two, as it is in the formula for finding the area of a triangle, the multiply by two and divide by two cancel out, giving us that if we just multiply base times height of <math>\triangle ACD</math>, we will get the area of <math>\triangle ABC</math>.<br />
<br />
Now you might think: "But what is the other way of finding the area". Well that is <math>AC</math>, which would be the base, times <math>DE</math>, the radius, which would be the height. <br />
<br />
The first way to find the area gives us the area of the <math>\triangle ABC</math>, <math>\frac{15\cdot16}{2}=120</math>. This gives us <math>120=AC\cdot r</math> (<math>r</math> signifies radius). We can find <math>AC</math> using the Pythagorean Theorem on <math>\triangle ACD</math>. The two legs are <math>8</math> and <math>15</math>, which gives us that the hypotenuse, <math>AC</math>, is equal to <math>17</math>. <br />
<br />
Now that we have an equation with only one variable for the radius, <math>120=17r</math>, we can just solve for the radius. We get <math>r=\boxed{\textbf{(B) }\frac{120}{17}}</math>. <br />
<br />
This may seem like a lengthy explanation, but doing it yourself when you know what to do, it actually takes very little time. Try it yourself!</div>Donutsmanhttps://artofproblemsolving.com/wiki/index.php?title=2017_AMC_8_Problems/Problem_22&diff=1186212017 AMC 8 Problems/Problem 222020-03-02T01:36:23Z<p>Donutsman: /* Solution 1 */</p>
<hr />
<div>==Problem 22==<br />
<br />
In the right triangle <math>ABC</math>, <math>AC=12</math>, <math>BC=5</math>, and angle <math>C</math> is a right angle. A semicircle is inscribed in the triangle as shown. What is the radius of the semicircle?<br />
<asy><br />
draw((0,0)--(12,0)--(12,5)--(0,0));<br />
draw(arc((8.67,0),(12,0),(5.33,0)));<br />
label("$A$", (0,0), W);<br />
label("$C$", (12,0), E);<br />
label("$B$", (12,5), NE);<br />
label("$12$", (6, 0), S);<br />
label("$5$", (12, 2.5), E);</asy><br />
<br />
<math>\textbf{(A) }\frac{7}{6}\qquad\textbf{(B) }\frac{13}{5}\qquad\textbf{(C) }\frac{59}{18}\qquad\textbf{(D) }\frac{10}{3}\qquad\textbf{(E) }\frac{60}{13}</math><br />
<br />
==Solution 1==<br />
We can reflect triangle <math>ABC</math> over line <math>AC.</math> This forms the triangle <math>AB'C</math> and a circle out of the semicircle. Let us call the center of the circle <math>O.</math><br />
<asy><br />
draw((0,0)--(12,0)--(12,5)--cycle);<br />
draw((0,0)--(12,0)--(12,-5)--cycle);<br />
draw(circle((8.665,0),3.3333));<br />
label("$A$", (0,0), W);<br />
label("$C$", (12,0), E);<br />
label("$B$", (12,5), NE);<br />
label("$B'$", (12,-5), NE);<br />
label("$12$", (7, 0), S);<br />
label("$5$", (12, 2.5), E);<br />
label("$5$", (12, -2.5), E);</asy><br />
We can see that Circle <math>O</math> is the incircle of <math>AB'C.</math> We can use the formula for finding the radius of the incircle to solve this problem: Area of a triangle <math>= Semi-perimeter\cdot inradius</math> . The area of <math>AB'C</math> is <math>12\times5 = 60.</math> The semiperimeter is <math>5+13 = 18.</math> Simplifying <math>\dfrac{60}{18} = \dfrac{10}{3}.</math> Our answer is therefore <math>\boxed{\textbf{(D)}\ \frac{10}{3}}.</math><br />
<br />
Asymptote diagram by Mathandski<br />
<br />
==Solution 2==<br />
We immediately see that <math>AB=13</math>, and we label the center of the semicircle <math>O</math> And the point where the circle is tangent to the triangle <math>D</math>. Drawing radius <math>OD</math> with length <math>x</math> such that <math>OD</math> is perpendicular to <math>AB</math>, we immediately see that <math>ODB\cong OCB</math> because of <math>\operatorname{HL}</math> congruence, so <math>BD=5</math> and <math>DA=8</math>. By similar triangles <math>ODA</math> and <math>BCA</math>, we see that <math>\frac{8}{12}=\frac{x}{5}\implies 12x=40\implies x=\frac{10}{3}\implies\boxed{\textbf{(D)}\ \frac{10}{3}}</math>.<br />
<br />
==Solution 3==<br />
Let the center of the semicircle be <math>O</math>. Let the point of tangency between line <math>AB</math> and the semicircle be <math>F</math>. Angle <math>BAC</math> is common to triangles <math>ABC</math> and <math>AFO</math>. By tangent properties, angle <math>AFO</math> must be <math>90</math> degrees. Since both triangles <math>ABC</math> and <math>AFO</math> are right and share an angle, <math>AFO</math> is similar to <math>ABC</math>. The hypotenuse of <math>AFO</math> is <math>12 - r</math>, where <math>r</math> is the radius of the circle. (See for yourself) The short leg of <math>AFO</math> is <math>r</math>. Because <math>AFO</math> ~ <math>ABC</math>, we have <math>r/(12 - r) = 5/13</math> and solving gives <math>r = \boxed{\textbf{(D)}\ \frac{10}{3}}</math><br />
<br />
==Solution 4==<br />
Let the tangency point on <math>AB</math> be <math>D</math>. Note <cmath>AD = AB-BD = AB-BC = 8</cmath> By Power of a Point, <cmath>12(12-2r) = 8^2</cmath><br />
Solving for <math>r</math> gives <br />
<cmath>r = \boxed{\textbf{(D) }\frac{10}{3}}</cmath><br />
<br />
==See Also==<br />
{{AMC8 box|year=2017|num-b=21|num-a=23}}<br />
<br />
{{MAA Notice}}</div>Donutsmanhttps://artofproblemsolving.com/wiki/index.php?title=2017_AMC_8_Problems/Problem_23&diff=1186202017 AMC 8 Problems/Problem 232020-03-02T01:27:39Z<p>Donutsman: /* Problem 23 */</p>
<hr />
<div>==Problem 23==<br />
<br />
Each day for four days, Linda traveled for one hour at a speed that resulted in her traveling one mile in an integer number of minutes. Each day after the first, her speed decreased so that the number of minutes to travel one mile increased by <math>5</math> minutes over the preceding day. Each of the four days, her distance traveled was also an integer number of miles. What was the total number of miles for the four trips?<br />
<br />
<math>\textbf{(A) }10\qquad\textbf{(B) }15\qquad\textbf{(C) }25\qquad\textbf{(D) }50\qquad\textbf{(E) }82</math><br />
<br />
==Solution==<br />
<br />
It is well known that <math>\text{Distance}=\text{Speed} \cdot \text{Time}</math>. In the question, we want distance. From the question, we have that the time is <math>60</math> minutes or <math>1</math> hour. By the equation derived from <math>\text{Distance}=\text{Speed} \cdot \text{Time}</math>, we have <math>\text{Speed}=\frac{\text{Distance}}{\text{Time}}</math>, so the speed is <math>1</math> mile per <math>x</math> minutes. Because we want the distance, we multiply the time and speed together yielding <math>60\text{ mins}\cdot \frac{1\text{ mile}}{x\text{ mins}}</math>. The minutes cancel out, so now we have <math>\dfrac{60}{x}</math> as our distance for the first day. The distance for the following days are:<br />
<cmath>\dfrac{60}{x},\dfrac{60}{x+5},\dfrac{60}{x+10},\dfrac{60}{x+15}</cmath><br />
We know that <math>x,x+5,x+10,x+15</math> are all factors of <math>60</math>, therefore, <math>x=5</math> because the factors have to be in an arithmetic sequence with the common difference being <math>5</math> and <math>x=5</math> is the only solution.<br />
<cmath>\dfrac{60}{5}+\dfrac{60}{10}+\dfrac{60}{15}+\dfrac{60}{20}=12+6+4+3=\boxed{\textbf{(C)}\ 25}</cmath><br />
<br />
==See Also==<br />
{{AMC8 box|year=2017|num-b=22|num-a=24}}<br />
<br />
{{MAA Notice}}</div>Donutsman