Difference between revisions of "2018 AMC 8 Problems/Problem 1"

Revision as of 16:31, 18 April 2020

Problem 1

An amusement park has a collection of scale models, with a ratio $1: 20$ , of buildings and other sights from around the country. The height of the United States Capitol is 289 feet. What is the height in feet of its duplicate to the nearest whole number?

$\textbf{(A) }14\qquad\textbf{(B) }15\qquad\textbf{(C) }16\qquad\textbf{(D) }18\qquad\textbf{(E) }20$

Solution 1

You can set up a ratio: $\frac{1}{20}=\frac{x}{289}$ . Cross multiplying, you get $20x=289$ . You divide by $20$ on each side to get $x=14.45$ . The closest integer is $\boxed{\textbf{(A)}14}$

Solution 2

You can just do $\frac{289}{20}$ and round your answer to get $\boxed{\textbf{(A)}14}$ . It is basically Solution 1 without the ratio calculation, which might not be necessary.

Solution 3

Solved with [b] tworigami, JetC, pretzel, realquarterb, AIME12345, jskalarickal, niyu, ntboiii, kevinmathz, lilypads, ddonk, sadkid, aaa12, byungshinfighters, mrsyallapragada, franchester, ingenio, GameMaster402, anish9876, mira74, SD2014, stroller, AOPS12142015, huangyi_99, sriraamster, TheUltimate123, vedant10, kothasuhas, budu, One-And-A-Half-Genius, Radio2, and mathfun5[/b]

A beautiful problem.

Recall a [b]contraction[/b] from a metric space $f: M \rightarrow M$ is a function such that for some constant $k < 1$ and all $x,y \in M$ , we have $d(f(x), f(y)) \leq kd(x,y)$

[b][color=#f00]Lemma 1:[/color][/b] Suppose that $f: M \rightarrow M$ is a contraction and that the metric space $M$ is complete. Then $f$ has a unique fixed point $p$ , and for any $x \in M$ , the iterate $f^n(x) = f \circ f \circ \dots \circ f(x)$ converges to $p$ as $n \rightarrow \infty$ .

[i]Proof:[/i] Choose any $x_0 \in M$ and define $x_n = f^n(x_0)$ . We claim that for all $n \in \mathbb{N}$ we have $d(x_n, x_{n+1}) \leq k^nd(x_0, x_1)$ which is immediate by the well ordering principle on $\mathbb{N^{+}}$ . Now, we claim that the sequence $(x_n)$ is Cauchy. For any $\varepsilon > 0$ , choose $N$ so that $\frac{k^N}{1-k}d(x_0, x_1) < \varepsilon$ If $N \leq m \leq n$ , we have \begin{align*} d(x_m, x_n) &\leq d(x_m, x_{m+1}) + d(x_{m+1}, x_{m+2}) + \dots + d(x_{n-1}, x_n)\\ &\leq k^md(x_0, x_1) + k^{m+1}d(x_0, x+1) + \dots + k^{n-1}d(x_0, x_1)\\ &= k^m(1+k + \dots + k^{n-m-1})d(x_0, x_1) \\ &\leq k^N \sum_{l =0}^{\infty} k^ld(x_0, x_1) = \frac{k^N}{1-k}d(x_0, x_1) < \varepsilon \end{align*} It is left as an exercise for the reader to show that this is equivalent to the usual definition of Cauchy, and we conclude $(x_n)$ is Cauchy. As $M$ is complete, the limit of the sequence $x_n$ is some $p$ which is contained in $M$ . For $n$ large, $x_n$ and $x_{n+1}$ lie in the $\varepsilon-$ neighborhood of $p$ , and since $\varepsilon$ was arbitrary, this gives that $f(p) = p$ as desired. Uniqueness is clear. $\square$

[b][color=#f00]Lemma 2:[/color][/b] We claim that the function $f: \mathbb{R} \rightarrow \mathbb{R}$ defined by $f(x) = \frac{x-289}{20}+14$ is a contraction. [i]Proof:[/i] Let $x, y \in \mathbb{R}$ and let $k = \frac{1}{20}$ . We have $d(f(x), f(y)) = d\left(\frac{x-289}{20}, \frac{y-289}{20}\right) = \frac{x-y}{20} \leq \frac{1}{20}d(x,y) =kd(x,y)$ as desired. $\square$

We thus find that $f$ has a unique fixed point, in particular when $x = \frac{-9}{19}$ . Because $\left(\frac{-9}{19}\right) = \left(\frac{-1}{19}\right)\left(\frac{3}{19}\right)\left(\frac{3}{19}\right) = (-1)(-1)(-1) = 1$ by Legendre symbol, we find that $\left|f\left(\frac{-9}{19}\right)-14\right| = \left|\frac{\frac{-9}{19}-289}{20}-14+14\right| = \left| -\frac{275}{19}\right| = \frac{275}{19}$ . We need one final lemma about the existence and uniqueness of decimal representations of the reals:

[b][color=#f00]Lemma 3:[/color][/b] The real numbers correspond bijectively to decimal expansions not terminating in an infinite string of nines.

[i]Proof:[/i] We outline the proof as follows: Given $x\in\mathbb R$ (with $\mathbb R$ defined using Dedekind cuts), we define a decimal expansion $N.x_1x_2\ldots$ , where $N$ is the largest integer $\le x$ , $x_1$ is the largest integer $\le 10(x-N)$ , $x_2$ is the largest integer $\le 100(x-(N+x_1/10))$ , and so on.

We show

[i][color=#00f](i)[/color][/i] Each $x_k$ is a digit between 0 and 9, [i][color=#00f](ii)[/color][/i] For each $k$ there is $\ell\ge k$ so that $x_\ell\neq9$ , and then [i][color=#00f](iii)[/color][/i] Conversely, that for any such expansion $N.x_1x_2\ldots$ not terminating in an infinite string of nines, the set $\{N, N+\frac{x_1}{10}, N+\frac{x_1}{10}+\frac{x_2}{100},\cdots\}$ is bounded and its least upper bound is a real number $x$ with decimal expansion $N.x_1x_2 \dots$

[i][color=#00f]Proof of (i):[/color][/i] Consider the decimal expansion $N.x_1x_2\dots$ . Because $N$ is the largest number $\leq x$ , $0 \leq .x_1x_2\dots <1$ , so $0 \leq 10(x-N) < 10$ , and $0 \leq x_1 \leq 9$ . Assume $x_i \in [0,9]$ for $1\leq i \leq k$ . Now consider the number $x_k.x_{k+1}x_{k+2} \dots$ . By the above, this implies $x_{k+1} \in [0, 9]$ .

[i][color=#00f]Proof of (ii):[/color][/i] We want each real number to have a unique decimal representation. Let $S = \{k \in \mathbf{N} : \not\exists l \geq k$ such that $x_l \neq 9 \}$ . Assume for the sake of contradiction that this set is nonempty. Then take $k' \in S$ as the minimal element of $S$ by WOP. Then, \begin{align*}

   x &= N.x_1x_2\dots x_{k-1}999\dots \\
   x' &= N.x_1x_2\dots (x_{k-1}+1)000 \dots

\end{align*} where $x < x'$ . By continuity we can pick some $x''$ such that $x < x'' < x'$ . But there clearly cannot be a decimal between $x$ and $x'$ , so $x=x'$ . This contradicts the definition of $x$ (ie $x_k$ is $\left \lfloor 10^k(x-(N+\frac{x_1}{10}+\dots+\frac{x_{k-1}}{10^{k-1}}))\right \rfloor$ , so $S$ is empty and $\forall k \in \mathbf{N}, \exists l \geq k$ such that $x_l \neq 9$ .

[i][color=#00f]Proof of (iii):[/color][/i] We want to show $\forall \epsilon > 0, \exists N$ such that $n \geq N \implies |a_n-x| < \epsilon$ . This is equivalent to $|\frac{x_{n+1}}{10^{n+1}} + \frac{x_{n+2}}{10^{n+2}}+\dots| \leq |\frac{9}{10^{N+1}}+\frac{9}{10^{N+2}}+\dots| \leq \frac{1}{10^N} < \epsilon$ . We can take $N = \left\lceil \frac{\ln{\epsilon}}{\ln{10}} \right\rceil$ for example, so $\lim_{n \rightarrow \infty}{a_n} = x$ .

We conclude that the real numbers correspond bijectively to decimal expansions not terminating in an infinite string of nines. $\square$

Using the constructive method given in [b] [color=#f00]Lemma 3[/color][/b], it is straightforward (and left as an exercise) to compute $\frac{275}{19} = 14.4736842\dots \approx 14 \rightarrow \boxed{\textbf{(A) }14}$ and we are done. $\blacksquare$ [/quote]

@@ Line 14: / Line 14: @@
 You can just do <math>\frac{289}{20}</math> and round your answer to get <math>\boxed{\textbf{(A)}14}</math>.
 It is basically Solution 1 without the ratio calculation, which might not be necessary.
+==Solution 3==
+Solved with [b] tworigami, JetC, pretzel, realquarterb, AIME12345, jskalarickal, niyu, ntboiii, kevinmathz, lilypads, ddonk, sadkid, aaa12, byungshinfighters, mrsyallapragada, franchester, ingenio, GameMaster402, anish9876, mira74, SD2014, stroller, AOPS12142015, huangyi_99, sriraamster, TheUltimate123, vedant10, kothasuhas, budu, One-And-A-Half-Genius, Radio2, and mathfun5[/b]
+-----
+A beautiful problem.
+Recall a [b]contraction[/b] from a metric space <math> f: M \rightarrow M</math> is a function such that for some constant <math>k < 1</math> and all <math>x,y \in M</math>, we have <cmath>d(f(x), f(y)) \leq kd(x,y)</cmath>
+[b][color=#f00]Lemma 1:[/color][/b] Suppose that <math>f: M \rightarrow M</math> is a contraction and that the metric space <math>M</math> is complete. Then <math>f</math> has a unique fixed point <math>p</math>, and for any <math>x \in M</math>, the iterate <math>f^n(x) = f \circ f \circ \dots \circ f(x)</math> converges to <math>p</math> as <math>n \rightarrow \infty</math>.
+[i]Proof:[/i] Choose any <math>x_0 \in M</math> and define <math>x_n = f^n(x_0)</math>. We claim that for all <math>n \in \mathbb{N}</math> we have <cmath>d(x_n, x_{n+1}) \leq k^nd(x_0, x_1)</cmath> which is immediate by the well ordering principle on <math>\mathbb{N^{+}}</math>. Now, we claim that the sequence <math>(x_n)</math> is Cauchy. For any <math>\varepsilon > 0</math>, choose <math>N</math> so that <cmath>\frac{k^N}{1-k}d(x_0, x_1) < \varepsilon</cmath> If <math>N \leq m \leq n</math>, we have
+\begin{align*}
+d(x_m, x_n) &\leq d(x_m, x_{m+1}) + d(x_{m+1}, x_{m+2}) + \dots + d(x_{n-1}, x_n)\\
+&\leq k^md(x_0, x_1) + k^{m+1}d(x_0, x+1) + \dots + k^{n-1}d(x_0, x_1)\\
+&= k^m(1+k + \dots + k^{n-m-1})d(x_0, x_1) \\
+&\leq k^N \sum_{l =0}^{\infty} k^ld(x_0, x_1) = \frac{k^N}{1-k}d(x_0, x_1) < \varepsilon
+\end{align*} It is left as an exercise for the reader to show that this is equivalent to the usual definition of Cauchy, and we conclude <math>(x_n)</math> is Cauchy. As <math>M</math> is complete, the limit of the sequence <math>x_n</math> is some <math>p</math> which is contained in <math>M</math>. For <math>n</math> large, <math>x_n</math> and <math>x_{n+1}</math> lie in the <math>\varepsilon-</math>neighborhood of <math>p</math>, and since <math>\varepsilon</math> was arbitrary, this gives that <math>f(p) = p</math> as desired. Uniqueness is clear. <math>\square</math>
+-----
+[b][color=#f00]Lemma 2:[/color][/b] We claim that the function <math>f: \mathbb{R} \rightarrow \mathbb{R}</math> defined by <math>f(x) = \frac{x-289}{20}+14</math> is a contraction.
+[i]Proof:[/i] Let <math>x, y \in \mathbb{R}</math> and let <math>k = \frac{1}{20}</math>. We have <cmath>d(f(x), f(y)) = d\left(\frac{x-289}{20}, \frac{y-289}{20}\right) = \frac{x-y}{20} \leq \frac{1}{20}d(x,y) =kd(x,y)</cmath> as desired. <math>\square</math>
+-----
+We thus find that <math>f</math> has a unique fixed point, in particular when <math>x = \frac{-9}{19}</math>.
+Because <math>\left(\frac{-9}{19}\right) = \left(\frac{-1}{19}\right)\left(\frac{3}{19}\right)\left(\frac{3}{19}\right) = (-1)(-1)(-1) = 1</math> by Legendre symbol, we find that <math>\left|f\left(\frac{-9}{19}\right)-14\right| = \left|\frac{\frac{-9}{19}-289}{20}-14+14\right| = \left| -\frac{275}{19}\right| = \frac{275}{19}</math>.
+We need one final lemma about the existence and uniqueness of decimal representations of the reals:
+-----
+[b][color=#f00]Lemma 3:[/color][/b] The real numbers correspond bijectively to decimal expansions not terminating in an infinite string of nines.
+[i]Proof:[/i] We outline the proof as follows: Given <math>x\in\mathbb R</math> (with <math>\mathbb R</math> defined using Dedekind cuts), we define a decimal expansion <math>N.x_1x_2\ldots</math>, where <math>N</math> is the largest integer <math>\le x</math>, <math>x_1</math> is the largest integer <math>\le 10(x-N)</math>, <math>x_2</math> is the largest integer <math>\le 100(x-(N+x_1/10))</math>, and so on.
+We show
+[i][color=#00f](i)[/color][/i] Each <math>x_k</math> is a digit between 0 and 9,
+[i][color=#00f](ii)[/color][/i] For each <math>k</math> there is <math>\ell\ge k</math> so that <math>x_\ell\neq9</math>, and then
+[i][color=#00f](iii)[/color][/i] Conversely, that for any such expansion <math>N.x_1x_2\ldots</math> not terminating in an infinite string of nines, the set<cmath>\{N, N+\frac{x_1}{10}, N+\frac{x_1}{10}+\frac{x_2}{100},\cdots\}</cmath>
+is bounded and its least upper bound is a real number <math>x</math> with decimal expansion <math>N.x_1x_2 \dots</math>
+[i][color=#00f]Proof of (i):[/color][/i] Consider the decimal expansion <math>N.x_1x_2\dots</math>. Because <math>N</math> is the largest number <math>\leq x</math>, <math>0 \leq .x_1x_2\dots <1</math>, so <math>0 \leq 10(x-N) < 10</math>, and <math>0 \leq x_1 \leq 9</math>. Assume <math>x_i \in [0,9]</math> for <math>1\leq i \leq k</math>. Now consider the number <math>x_k.x_{k+1}x_{k+2} \dots</math>. By the above, this implies <math>x_{k+1} \in [0, 9]</math>.
+[i][color=#00f]Proof of (ii):[/color][/i] We want each real number to have a unique decimal representation. Let <math>S = \{k \in \mathbf{N} : \not\exists l \geq k</math> such that <math>x_l \neq 9 \}</math>. Assume for the sake of contradiction that this set is nonempty. Then take <math>k' \in S</math> as the minimal element of <math>S</math> by WOP. Then,
+\begin{align*}
+    x &= N.x_1x_2\dots x_{k-1}999\dots \\
+    x' &= N.x_1x_2\dots (x_{k-1}+1)000 \dots
+\end{align*}
+where <math>x < x'</math>. By continuity we can pick some <math>x''</math> such that <math>x < x'' < x'</math>. But there clearly cannot be a decimal between <math>x</math> and <math>x'</math>, so <math>x=x'</math>. This contradicts the definition of <math>x</math> (ie <math>x_k</math> is <math>\left \lfloor 10^k(x-(N+\frac{x_1}{10}+\dots+\frac{x_{k-1}}{10^{k-1}}))\right \rfloor</math>, so <math>S</math> is empty and <math>\forall k \in \mathbf{N}, \exists l \geq k</math> such that <math>x_l \neq 9</math>.
+[i][color=#00f]Proof of (iii):[/color][/i] We want to show <math>\forall \epsilon > 0, \exists N</math> such that <math>n \geq N \implies |a_n-x| < \epsilon</math>. This is equivalent to <math>|\frac{x_{n+1}}{10^{n+1}} + \frac{x_{n+2}}{10^{n+2}}+\dots| \leq |\frac{9}{10^{N+1}}+\frac{9}{10^{N+2}}+\dots| \leq \frac{1}{10^N} < \epsilon</math>. We can take <math>N = \left\lceil \frac{\ln{\epsilon}}{\ln{10}} \right\rceil</math> for example, so <math>\lim_{n \rightarrow \infty}{a_n} = x</math>.
+We conclude that the real numbers correspond bijectively to decimal expansions not terminating in an infinite string of nines. <math>\square</math>
+-----
+Using the constructive method given in [b] [color=#f00]Lemma 3[/color][/b], it is straightforward (and left as an exercise) to compute <cmath>\frac{275}{19} = 14.4736842\dots \approx 14 \rightarrow \boxed{\textbf{(A) }14}</cmath> and we are done. <math>\blacksquare</math>[/quote]
 ==See Also==

2018 AMC 8 (Problems • Answer Key • Resources)
Preceded by First Problem	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AJHSME/AMC 8 Problems and Solutions

Page

Toolbox

Search