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 "2007 AIME I Problems/Problem 5"

m (→‎Solution 1: breakup long eqn)
m (→‎Solution 3)
 
(18 intermediate revisions by 14 users not shown)
Line 1: Line 1:
 +
__TOC__
 +
 
== Problem ==
 
== Problem ==
 
The formula for converting a Fahrenheit temperature <math>F</math> to the corresponding Celsius temperature <math>C</math> is <math>C = \frac{5}{9}(F-32).</math>  An integer Fahrenheit temperature is converted to Celsius, rounded to the nearest integer, converted back to Fahrenheit, and again rounded to the nearest [[integer]].
 
The formula for converting a Fahrenheit temperature <math>F</math> to the corresponding Celsius temperature <math>C</math> is <math>C = \frac{5}{9}(F-32).</math>  An integer Fahrenheit temperature is converted to Celsius, rounded to the nearest integer, converted back to Fahrenheit, and again rounded to the nearest [[integer]].
Line 4: Line 6:
 
For how many integer Fahrenheit temperatures between 32 and 1000 inclusive does the original temperature equal the final temperature?
 
For how many integer Fahrenheit temperatures between 32 and 1000 inclusive does the original temperature equal the final temperature?
  
−
__TOC__
 
 
== Solution ==
 
== Solution ==
 
=== Solution 1 ===
 
=== Solution 1 ===
 
Examine <math>F - 32</math> modulo 9.
 
Examine <math>F - 32</math> modulo 9.
  
−
*If <math>\displaystyle F - 32 \equiv 0 \pmod{9}</math>, then we can define <math>9x = F - 32</math>. This shows that <math>F = \left[\frac{9}{5}\left[\frac{5}{9}(F-32)\right] + 32\right] \Longrightarrow F = \left[\frac{9}{5}(5x) + 32\right] \Longrightarrow F = 9x + 32</math>. This case works.
+
*If <math>F - 32 \equiv 0 \pmod{9}</math>, then we can define <math>9x = F - 32</math>. This shows that <math>F = \left[\frac{9}{5}\left[\frac{5}{9}(F-32)\right] + 32\right] \Longrightarrow F = \left[\frac{9}{5}(5x) + 32\right] \Longrightarrow F = 9x + 32</math>. This case works.
−
* If <math>\displaystyle F - 32 \equiv 1 \pmod{9}</math>, then we can define <math>9x + 1 = F - 32</math>. This shows that <math>F = \left[\frac{9}{5}\left[\frac{5}{9}(F-32)\right] + 32\right] \Longrightarrow F = \left[\frac{9}{5}(5x + 1) + 32\right] \Longrightarrow</math><math>F = \left[9x + \frac{9}{5}+ 32 \right] \Longrightarrow F = 9x + 34</math>. So this case doesn't work.  
+
* If <math>F - 32 \equiv 1 \pmod{9}</math>, then we can define <math>9x + 1 = F - 32</math>. This shows that <math>F = \left[\frac{9}{5}\left[\frac{5}{9}(F-32)\right] + 32\right] \Longrightarrow F = \left[\frac{9}{5}(5x + 1) + 32\right] \Longrightarrow</math><math>F = \left[9x + \frac{9}{5}+ 32 \right] \Longrightarrow F = 9x + 34</math>. So this case doesn't work.  
  
−
Generalizing this, we define that <math>9x + k = F - 32</math>. Thus, <math>F = \left[\frac{9}{5}\left[\frac{5}{9}(9x + k)\right] + 32\right] \Longrightarrow F = \left[\frac{9}{5}(5x + \left[\frac{5}{9}k\right]) + 32\right] \Longrightarrow F = \left[\frac{9}{5} \left[\frac{9}{5}k \right] \right] + 9x + 32</math>. We need to find all values <math>\displaystyle 0 \le k \le 8</math> that <math>\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = k</math>. Testing every value of <math>k</math> shows that <math>k = 0, 2, 4, 5, 7</math>, so <math>5</math> of every <math>9</math> values of <math>k</math> work.
+
Generalizing this, we define that <math>9x + k = F - 32</math>. Thus, <math>F = \left[\frac{9}{5}\left[\frac{5}{9}(9x + k)\right] + 32\right] \Longrightarrow F = \left[\frac{9}{5}(5x + \left[\frac{5}{9}k\right]) + 32\right] \Longrightarrow F = \left[\frac{9}{5} \left[\frac{5}{9}k \right] \right] + 9x + 32</math>. We need to find all values <math>0 \le k \le 8</math> that <math>\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = k</math>. Testing every value of <math>k</math> shows that <math>k = 0, 2, 4, 5, 7</math>, so <math>5</math> of every <math>9</math> values of <math>k</math> work.
  
−
There are <math>\lfloor \frac{1000 - 32}{9} \rfloor = 107</math> cycles of <math>9</math>, giving <math>5 \cdot 107 = 535</math> numbers that work. Of the remaining <math>6</math> numbers from <math>995</math> onwards, <math>995,\ 997,\ 999,\ 1000</math> work, giving us <math>535 + 4 = 539</math> as the solution.
+
There are <math>\lfloor \frac{1000 - 32}{9} \rfloor = 107</math> cycles of <math>9</math>, giving <math>5 \cdot 107 = 535</math> numbers that work. Of the remaining <math>6</math> numbers from <math>995</math> onwards, <math>995,\ 997,\ 999,\ 1000</math> work, giving us <math>535 + 4 = \boxed{539}</math> as the solution.
  
 
=== Solution 2 ===
 
=== Solution 2 ===
−
Notice that <math>\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = k</math> holds iff <math>k=\left[ \frac{9}{5}x\right]</math> for some <math>x</math>.
+
Notice that <math>\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = k</math> holds if <math>k=\left[ \frac{9}{5}x\right]</math> for some integer <math>x</math>.
−
Thus, after translating from <math>F\to F-32</math> we want count how many values of <math>x</math> there are such that <math>k=\left[ \frac{9}{5}x\right]</math> is an integer from <math>0</math> to <math>968</math>. This value is computed as <math>\left[968*\frac{5}{9}\right]+1</math>, adding in the extra solution corresponding to <math>0</math>.
+
Thus, after translating from <math>F\to F-32</math> we want count how many values of <math>x</math> there are such that <math>k=\left[ \frac{9}{5}x\right]</math> is an integer from <math>0</math> to <math>968</math>. This value is computed as <math>\left[968*\frac{5}{9}\right]+1 = \boxed{539}</math>, adding in the extra solution corresponding to <math>0</math>.
 +
 
 +
==== Note ====
 +
Proof that <math>\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = k</math> iff <math>k=\left[ \frac{9}{5}x\right]</math> for some integer <math>x</math>:
 +
 
 +
First assume that <math>k</math> cannot be written in the form <math>k=\left[ \frac{9}{5}x\right]</math> for any integer <math>x</math>. Let <math>z = \left[ \frac{5}{9}k\right]</math>. Our equation simplifies to <math>k = \left[ \frac{9}{5}z\right]</math>. However, this equation is not possible, as we defined <math>k</math> such that it could not be written in this form. Therefore, if <math>k \neq \left[ \frac{9}{5}x\right]</math>, then <math>\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] \neq k</math>.
 +
 
 +
Now we will prove that if <math>k = \left[ \frac{9}{5}x\right]</math>, <math>\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = k</math>. We realize that because of the 5 in the denominator of <math>\left[ \frac{9}{5}x \right]</math>, <math>\left[ \frac{9}{5}x \right]</math> will be at most <math>\frac{2}{5}</math> away from <math>\frac{9}{5}x</math>. Let <math>z = \left[ \frac{9}{5}x \right]- \frac{9}{5}x</math>, meaning that <math>-\frac{2}{5} \leq z \leq \frac{2}{5}</math>. Now we substitute this into our equation:
 +
 
 +
<cmath>\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = \left[ \frac{9}{5} \left[ \frac{5}{9} \left[ \frac{9}{5}x\right] \right] \right] = \left[ \frac{9}{5} \left[ \frac{5}{9} (\frac{9}{5}x + z) \right] \right] = \left[ \frac{9}{5} \left[ \frac{5}{9} (\frac{9}{5}x + z) \right] \right] = \left[ \frac{9}{5} \left[ x+ \frac{5}{9}z \right] \right]</cmath>.
 +
 
 +
Now we use the fact that <math>-\frac{2}{5} \leq z \leq \frac{2}{5}</math>
 +
 
 +
<cmath>\left[ \frac{9}{5} \left[ x - \frac{5}{9}(\frac{2}{5}) \right] \right] \leq \left[ \frac{9}{5} \left[ x + \frac{5}{9}(z) \right] \right] \leq \left[ \frac{9}{5} \left[ x + \frac{5}{9}(\frac{2}{5}) \right] \right]</cmath>
 +
 
 +
<cmath>\left[ \frac{9}{5} x \right] \leq \left[ \frac{9}{5} \left[ x + \frac{5}{9}(z) \right] \right] = \left[ \frac{9}{5} \left[ \frac{5}{9}k \right] \right] \leq \left[ \frac{9}{5}x \right]</cmath>
 +
 
 +
Hence <math>\left[ \frac{9}{5} \left[ \frac{5}{9}k \right] \right] = \left[ \frac{9}{5}x \right] = k</math> and we are done.
 +
 
 +
- mako17
  
 
=== Solution 3 ===
 
=== Solution 3 ===
−
Let <math>c</math> be a degree Celcius, and <math>f=\frac 95c+32</math> rounded to the nearest integer. <math>|f-((\frac 95)c+32)|\leq 1/2</math> <math>|(\frac 59)(f-32)-c|\leq \frac 5{18}</math> so it must round to <math>c</math> because <math>\frac 5{18}<\frac 12</math>. Therefore there is one solution per degree celcius in the range from <math>0</math> to <math>(\frac 59)(1000-32) + 1=(\frac 59)(968) + 1=538.8</math>, meaning there are <math>539</math> solutions.
+
Let <math>c</math> be a degree Celsius, and <math>f=\frac 95c+32</math> rounded to the nearest integer. Since <math>f</math> was rounded to the nearest integer we have <math>|f-((\frac 95)c+32)|\leq 1/2</math>, which is equivalent to <math>|(\frac 59)(f-32)-c|\leq \frac 5{18}</math> if we multiply by <math>5/9</math>. Therefore, it must round to <math>c</math> because <math>\frac 5{18}<\frac 12</math> so <math>c</math> is the closest integer. Therefore there is one solution per degree Celsius in the range from <math>0</math> to <math>(\frac 59)(1000-32) + 1=(\frac 59)(968) + 1=538.8</math>, meaning there are <math>539</math> solutions.
 +
 
 +
=== Solution 4 ===
 +
Start listing out values for <math>F</math> and their corresponding values of <math>C</math>. You will soon find that every 9 values starting from <math>F</math> = 32, there is a pattern:
 +
 
 +
<math>F=32</math>: Works
 +
 
 +
<math>F=33</math>: Doesn't work
 +
 
 +
<math>F=34</math>: work
 +
 
 +
<math>F=35</math>: Doesn’t work
 +
 
 +
<math>F=36</math>: Works
 +
 
 +
<math>F=37</math>: Works
 +
 
 +
<math>F=38</math>: Doesn’t work
 +
 
 +
<math>F=39</math>: Works
 +
 
 +
<math>F=40</math>: Doesn’t work
 +
 
 +
<math>F=41</math>: Works
 +
 
 +
There are <math>969</math> numbers between <math>32</math> and <math>1000</math>, inclusive. This is <math>107</math> sets of <math>9</math>, plus <math>6</math> extra numbers at the end. In each set of <math>9</math>, there are <math>5</math> “Works,” so we have <math>107\cdot5 = 535</math> values of <math>F</math> that work.
 +
 
 +
Now we must add the <math>6</math> extra numbers. The number of “Works” in the first <math>6</math> terms of the pattern is <math>4</math>, so our final answer is <math>535 + 4 = 539</math> solutions that work.
 +
 
 +
Submitted by warriorcats
 +
 
 +
=== Solution 5(similar to solution 3 but faster solution if you have no time) ===
 +
Notice that every <math>C</math> value corresponds to exactly one <math>F</math> value but multiple <math>F</math> values can correspond to a <math>C</math> value. Thus, the smallest <math>C</math> value is <math>0</math> and the largest <math>C</math> value is <math>538</math> yielding <math>\boxed{539}</math> solutions.
 +
 
 +
-alanisawesome2018
  
 
== See also ==
 
== See also ==
Line 27: Line 81:
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 19:30, 4 August 2024

Problem

The formula for converting a Fahrenheit temperature $F$ to the corresponding Celsius temperature $C$ is $C = \frac{5}{9}(F-32).$ An integer Fahrenheit temperature is converted to Celsius, rounded to the nearest integer, converted back to Fahrenheit, and again rounded to the nearest integer.

For how many integer Fahrenheit temperatures between 32 and 1000 inclusive does the original temperature equal the final temperature?

Solution

Solution 1

Examine $F - 32$ modulo 9.

  • If $F - 32 \equiv 0 \pmod{9}$, then we can define $9x = F - 32$. This shows that $F = \left[\frac{9}{5}\left[\frac{5}{9}(F-32)\right] + 32\right] \Longrightarrow F = \left[\frac{9}{5}(5x) + 32\right] \Longrightarrow F = 9x + 32$. This case works.
  • If $F - 32 \equiv 1 \pmod{9}$, then we can define $9x + 1 = F - 32$. This shows that $F = \left[\frac{9}{5}\left[\frac{5}{9}(F-32)\right] + 32\right] \Longrightarrow F = \left[\frac{9}{5}(5x + 1) + 32\right] \Longrightarrow$$F = \left[9x + \frac{9}{5}+ 32 \right] \Longrightarrow F = 9x + 34$. So this case doesn't work.

Generalizing this, we define that $9x + k = F - 32$. Thus, $F = \left[\frac{9}{5}\left[\frac{5}{9}(9x + k)\right] + 32\right] \Longrightarrow F = \left[\frac{9}{5}(5x + \left[\frac{5}{9}k\right]) + 32\right] \Longrightarrow F = \left[\frac{9}{5} \left[\frac{5}{9}k \right] \right] + 9x + 32$. We need to find all values $0 \le k \le 8$ that $\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = k$. Testing every value of $k$ shows that $k = 0, 2, 4, 5, 7$, so $5$ of every $9$ values of $k$ work.

There are $\lfloor \frac{1000 - 32}{9} \rfloor = 107$ cycles of $9$, giving $5 \cdot 107 = 535$ numbers that work. Of the remaining $6$ numbers from $995$ onwards, $995,\ 997,\ 999,\ 1000$ work, giving us $535 + 4 = \boxed{539}$ as the solution.

Solution 2

Notice that $\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = k$ holds if $k=\left[ \frac{9}{5}x\right]$ for some integer $x$. Thus, after translating from $F\to F-32$ we want count how many values of $x$ there are such that $k=\left[ \frac{9}{5}x\right]$ is an integer from $0$ to $968$. This value is computed as $\left[968*\frac{5}{9}\right]+1 = \boxed{539}$, adding in the extra solution corresponding to $0$.

Note

Proof that $\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = k$ iff $k=\left[ \frac{9}{5}x\right]$ for some integer $x$:

First assume that $k$ cannot be written in the form $k=\left[ \frac{9}{5}x\right]$ for any integer $x$. Let $z = \left[ \frac{5}{9}k\right]$. Our equation simplifies to $k = \left[ \frac{9}{5}z\right]$. However, this equation is not possible, as we defined $k$ such that it could not be written in this form. Therefore, if $k \neq \left[ \frac{9}{5}x\right]$, then $\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] \neq k$.

Now we will prove that if $k = \left[ \frac{9}{5}x\right]$, $\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = k$. We realize that because of the 5 in the denominator of $\left[ \frac{9}{5}x \right]$, $\left[ \frac{9}{5}x \right]$ will be at most $\frac{2}{5}$ away from $\frac{9}{5}x$. Let $z = \left[ \frac{9}{5}x \right]- \frac{9}{5}x$, meaning that $-\frac{2}{5} \leq z \leq \frac{2}{5}$. Now we substitute this into our equation:

\[\left[ \frac{9}{5} \left[ \frac{5}{9} k \right] \right] = \left[ \frac{9}{5} \left[ \frac{5}{9} \left[ \frac{9}{5}x\right] \right] \right] = \left[ \frac{9}{5} \left[ \frac{5}{9} (\frac{9}{5}x + z) \right] \right] = \left[ \frac{9}{5} \left[ \frac{5}{9} (\frac{9}{5}x + z) \right] \right] = \left[ \frac{9}{5} \left[ x+ \frac{5}{9}z \right] \right]\].

Now we use the fact that $-\frac{2}{5} \leq z \leq \frac{2}{5}$

\[\left[ \frac{9}{5} \left[ x - \frac{5}{9}(\frac{2}{5}) \right] \right] \leq \left[ \frac{9}{5} \left[ x + \frac{5}{9}(z) \right] \right] \leq \left[ \frac{9}{5} \left[ x + \frac{5}{9}(\frac{2}{5}) \right] \right]\]

\[\left[ \frac{9}{5} x \right] \leq \left[ \frac{9}{5} \left[ x + \frac{5}{9}(z) \right] \right] = \left[ \frac{9}{5} \left[ \frac{5}{9}k \right] \right] \leq \left[ \frac{9}{5}x \right]\]

Hence $\left[ \frac{9}{5} \left[ \frac{5}{9}k \right] \right] = \left[ \frac{9}{5}x \right] = k$ and we are done.

- mako17

Solution 3

Let $c$ be a degree Celsius, and $f=\frac 95c+32$ rounded to the nearest integer. Since $f$ was rounded to the nearest integer we have $|f-((\frac 95)c+32)|\leq 1/2$, which is equivalent to $|(\frac 59)(f-32)-c|\leq \frac 5{18}$ if we multiply by $5/9$. Therefore, it must round to $c$ because $\frac 5{18}<\frac 12$ so $c$ is the closest integer. Therefore there is one solution per degree Celsius in the range from $0$ to $(\frac 59)(1000-32) + 1=(\frac 59)(968) + 1=538.8$, meaning there are $539$ solutions.

Solution 4

Start listing out values for $F$ and their corresponding values of $C$. You will soon find that every 9 values starting from $F$ = 32, there is a pattern:

$F=32$: Works

$F=33$: Doesn't work

$F=34$: work

$F=35$: Doesn’t work

$F=36$: Works

$F=37$: Works

$F=38$: Doesn’t work

$F=39$: Works

$F=40$: Doesn’t work

$F=41$: Works

There are $969$ numbers between $32$ and $1000$, inclusive. This is $107$ sets of $9$, plus $6$ extra numbers at the end. In each set of $9$, there are $5$ “Works,” so we have $107\cdot5 = 535$ values of $F$ that work.

Now we must add the $6$ extra numbers. The number of “Works” in the first $6$ terms of the pattern is $4$, so our final answer is $535 + 4 = 539$ solutions that work.

Submitted by warriorcats

Solution 5(similar to solution 3 but faster solution if you have no time)

Notice that every $C$ value corresponds to exactly one $F$ value but multiple $F$ values can correspond to a $C$ value. Thus, the smallest $C$ value is $0$ and the largest $C$ value is $538$ yielding $\boxed{539}$ solutions.

-alanisawesome2018

See also

2007 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 4 		Followed by
Problem 6
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_AIME_I_Problems/Problem_5&oldid=224465"