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 "1985 AIME Problems/Problem 10"

(→‎See also)
(→‎Solution: reduce by 1/2)
Line 5: Line 5:
  
 
where <math>x</math> is a [[real number]], and <math>\lfloor z \rfloor</math> denotes the greatest [[integer]] less than or equal to <math>z</math>?
 
where <math>x</math> is a [[real number]], and <math>\lfloor z \rfloor</math> denotes the greatest [[integer]] less than or equal to <math>z</math>?
 +
__TOC__
 
== Solution ==
 
== Solution ==
−
We will be able to reach the same number of integers while <math>x</math> ranges from 0 to 1 as we will when <math>x</math> ranges from <math>n</math> to <math>n + 1</math> for any integer <math>n</math>. Since <math>\lfloor 2\cdot50 \rfloor + \lfloor 4\cdot50 \rfloor + \lfloor 6\cdot50 \rfloor + \lfloor 8\cdot50 \rfloor = 100 + 200 + 300 + 400</math>, the answer must be exactly 50 times the number of integers we will be able to reach as <math>x</math> ranges from 0 to 1, including 1 but excluding 0.
+
We will be able to reach the same number of integers while <math>x</math> ranges from 0 to 1 as we will when <math>x</math> ranges from <math>n</math> to <math>n + 1</math> for any [[integer]] <math>n</math> (Quick proof: <math>\lfloor 2(n+x)\rfloor + \ldots = \lfloor 2n + 2x\rfloor + \ldots = 2n + \lfloor 2x\rfloor \ldots</math>). Since <math>\lfloor 2\cdot50 \rfloor + \lfloor 4\cdot50 \rfloor + \lfloor 6\cdot50 \rfloor + \lfloor 8\cdot50 \rfloor = 100 + 200 + 300 + 400</math>, the answer must be exactly 50 times the number of integers we will be able to reach as <math>x</math> ranges from 0 to 1, including 1 but excluding 0.
  
 +
=== Solution 1 ===
 +
Noting that all of the numbers are even, we can reduce this to any real number <math>x</math> between <math>0</math> to <math>\frac 12</math>, as this will be equivalent to <math>\displaystyle \frac n2</math> to <math>\frac {n+1}2</math> for any integer <math>n</math> (same reasoning as above). So now we only need to test every 10 numbers; and our answer will be 100 times the number of integers we can reach between 1 and 10.
 +
 +
We can now approach this by directly searching for the integers (this solution) or brute forcing all of the cases (next solution):
 +
 +
We can match up the greatest integer functions with one of the partitions of the integer. If we let <math>x = \frac 12</math> then we get the solution <math>10</math>; now consider when <math>x < \frac 12</math>: <math>\lfloor 2x \rfloor = 0</math>, <math>\lfloor 4x \rfloor \le 1</math>, <math>\lfloor 6x \rfloor \le 2</math>, <math>\displaystyle \lfloor 8x \rfloor \le 3</math>. But according to this the maximum we can get is <math>1+2+3 = 6</math>, so we only need to try the first 6 numbers.
 +
 +
*<math>1</math>: Easily possible, for example try plugging in <math>x = \displaystyle \frac 18</math>.
 +
*<math>2</math>: Also simple, for example using <math>\displaystyle \frac 16</math>.
 +
*<math>3</math>: The partition must either be <math>1+1+1</math> or <math>1+2</math>. If <math>\lfloor 4x \rfloor = 1</math>, then <math>x \ge \frac 14</math>, but then <math>\lfloor 8x \rfloor \ge 2</math>; not possible; and vice versa to show that the latter partition doesn't work. So we cannot obtain <math>3</math>.
 +
*<math>4</math>: We can partition as <math>1+1+2</math>, and from the previous case we see that <math>\frac 14</math> works.
 +
*<math>5</math>: We can partition as <math>1+2+2</math>, from which we find that <math>\frac 13</math> works.
 +
*<math>6</math>: We can partition as <math>1+2+3</math>, from which we find that <math>\frac 38</math> works.
 +
 +
Out of these 6 cases, only 3 fails. So between 1 and 10 we can reach only the integers <math>1,2,4,5,6,10</math>; hence our solution is <math>6 \cdot 100 = 600</math>.
 +
 +
=== Solution 2 ===
 
As we change the value of <math>x</math>, the value of our [[expression]] changes only when <math>x</math> crosses [[rational number]] of the form <math>\frac{m}{n}</math>, where <math>n</math> is divisible by 2, 4, 6 or 8.  Thus, we need only see what happens at the numbers of the form <math>\frac{m}{\textrm{gcd}(2, 4, 6, 8)} = \frac{m}{24}</math>.  This gives us 24 calculations to make; we summarize the results here:
 
As we change the value of <math>x</math>, the value of our [[expression]] changes only when <math>x</math> crosses [[rational number]] of the form <math>\frac{m}{n}</math>, where <math>n</math> is divisible by 2, 4, 6 or 8.  Thus, we need only see what happens at the numbers of the form <math>\frac{m}{\textrm{gcd}(2, 4, 6, 8)} = \frac{m}{24}</math>.  This gives us 24 calculations to make; we summarize the results here:
  
Line 36: Line 54:
 
<math>\frac{24}{24} \to 20</math>
 
<math>\frac{24}{24} \to 20</math>
  
−
Thus, we hit 12 of the first 20 integers and so we hit <math>50 \cdot 12 = 600</math> of the first 100.
+
Thus, we hit 12 of the first 20 integers and so we hit <math>50 \cdot 12 = 600</math> of the first 1000.
  
 
== See also ==
 
== See also ==

Revision as of 18:08, 11 September 2007

Problem

How many of the first 1000 positive integers can be expressed in the form

$\lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 6x \rfloor + \lfloor 8x \rfloor$,

where $x$ is a real number, and $\lfloor z \rfloor$ denotes the greatest integer less than or equal to $z$?

Solution

We will be able to reach the same number of integers while $x$ ranges from 0 to 1 as we will when $x$ ranges from $n$ to $n + 1$ for any integer $n$ (Quick proof: $\lfloor 2(n+x)\rfloor + \ldots = \lfloor 2n + 2x\rfloor + \ldots = 2n + \lfloor 2x\rfloor \ldots$). Since $\lfloor 2\cdot50 \rfloor + \lfloor 4\cdot50 \rfloor + \lfloor 6\cdot50 \rfloor + \lfloor 8\cdot50 \rfloor = 100 + 200 + 300 + 400$, the answer must be exactly 50 times the number of integers we will be able to reach as $x$ ranges from 0 to 1, including 1 but excluding 0.

Solution 1

Noting that all of the numbers are even, we can reduce this to any real number $x$ between $0$ to $\frac 12$, as this will be equivalent to $\displaystyle \frac n2$ to $\frac {n+1}2$ for any integer $n$ (same reasoning as above). So now we only need to test every 10 numbers; and our answer will be 100 times the number of integers we can reach between 1 and 10.

We can now approach this by directly searching for the integers (this solution) or brute forcing all of the cases (next solution):

We can match up the greatest integer functions with one of the partitions of the integer. If we let $x = \frac 12$ then we get the solution $10$; now consider when $x < \frac 12$: $\lfloor 2x \rfloor = 0$, $\lfloor 4x \rfloor \le 1$, $\lfloor 6x \rfloor \le 2$, $\displaystyle \lfloor 8x \rfloor \le 3$. But according to this the maximum we can get is $1+2+3 = 6$, so we only need to try the first 6 numbers.

  • $1$: Easily possible, for example try plugging in $x = \displaystyle \frac 18$.
  • $2$: Also simple, for example using $\displaystyle \frac 16$.
  • $3$: The partition must either be $1+1+1$ or $1+2$. If $\lfloor 4x \rfloor = 1$, then $x \ge \frac 14$, but then $\lfloor 8x \rfloor \ge 2$; not possible; and vice versa to show that the latter partition doesn't work. So we cannot obtain $3$.
  • $4$: We can partition as $1+1+2$, and from the previous case we see that $\frac 14$ works.
  • $5$: We can partition as $1+2+2$, from which we find that $\frac 13$ works.
  • $6$: We can partition as $1+2+3$, from which we find that $\frac 38$ works.

Out of these 6 cases, only 3 fails. So between 1 and 10 we can reach only the integers $1,2,4,5,6,10$; hence our solution is $6 \cdot 100 = 600$.

Solution 2

As we change the value of $x$, the value of our expression changes only when $x$ crosses rational number of the form $\frac{m}{n}$, where $n$ is divisible by 2, 4, 6 or 8. Thus, we need only see what happens at the numbers of the form $\frac{m}{\textrm{gcd}(2, 4, 6, 8)} = \frac{m}{24}$. This gives us 24 calculations to make; we summarize the results here:

$\frac{1}{24}, \frac{2}{24} \to 0$

$\frac{3}{24} \to 1$

$\frac{4}{24}, \frac{5}{24} \to 2$

$\frac{6}{24}, \frac{7}{24} \to 4$

$\frac{8}{24} \to 5$

$\frac{9}{24}, \frac{10}{24}, \frac{11}{24} \to 6$

$\frac{12}{24}, \frac{13}{24}, \frac{14}{24} \to 10$

$\frac{15}{24} \to 11$

$\frac{16}{24},\frac{17}{24} \to 12$

$\frac{18}{24}, \frac{19}{24} \to 14$

$\frac{20}{24}\to 15$

$\frac{21}{24}, \frac{22}{24}, \frac{23}{24} \to16$

$\frac{24}{24} \to 20$

Thus, we hit 12 of the first 20 integers and so we hit $50 \cdot 12 = 600$ of the first 1000.

See also

1985 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 9 		Followed by
Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1985_AIME_Problems/Problem_10&oldid=16066"