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"

m (→‎Solution 6)
(→‎Solution 2 Shortcut Shortcut)
 
(20 intermediate revisions by 6 users not shown)
Line 6: Line 6:
 
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__
 
__TOC__
−
== 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> (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 ===
+
== 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>\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.  
 
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>\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.  
  
Line 25: Line 23:
 
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 = \boxed{600}</math>.
 
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 = \boxed{600}</math>.
  
−
=== Solution 2 ===
+
== 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{lcm}(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{lcm}(2, 4, 6, 8)} = \frac{m}{24}</math>.  This gives us 24 calculations to make; we summarize the results here:
  
Line 62: Line 60:
 
~[[User:N828335|N828335]]
 
~[[User:N828335|N828335]]
  
−
===Solution 3===
+
===Solution 2 Bigger Shortcut (Close to Solution 6)===
 +
We only need to check the numbers where it increments, namely <math>\frac{1}{8}, \frac{1}{6}, \frac{1}{4}, \frac{1}{3}, \frac{3}{8}, \frac{1}{2}</math>. As shown before, we hit 6 integers (<math>1,2,4,5,6,10</math>) from <math>\frac{1}{24}</math> to <math>\frac{1}{2}</math>. Similarly, this should repeat 100 times, for <math>\boxed{600}</math>
 +
 
 +
~JeffersonJ
 +
 
 +
==Solution 3==
  
 
Recall from Hermite's Identity that <math>\sum_{k = 0}^{n - 1}\left\lfloor x + \frac kn\right\rfloor = \lfloor nx\rfloor</math>. Then we can rewrite <math>\lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 6x \rfloor + \lfloor 8x \rfloor = 4\lfloor x\rfloor + \left\lfloor x + \frac18\right\rfloor + \left\lfloor x + \frac16\right\rfloor + 2\left\lfloor x + \frac14\right\rfloor + \left\lfloor x + \frac13\right\rfloor</math>
 
Recall from Hermite's Identity that <math>\sum_{k = 0}^{n - 1}\left\lfloor x + \frac kn\right\rfloor = \lfloor nx\rfloor</math>. Then we can rewrite <math>\lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 6x \rfloor + \lfloor 8x \rfloor = 4\lfloor x\rfloor + \left\lfloor x + \frac18\right\rfloor + \left\lfloor x + \frac16\right\rfloor + 2\left\lfloor x + \frac14\right\rfloor + \left\lfloor x + \frac13\right\rfloor</math>
 
<math>+ \left\lfloor x + \frac38\right\rfloor + 4\left\lfloor x + \frac12\right\rfloor + \left\lfloor x + \frac58\right\rfloor + \left\lfloor x + \frac23\right\rfloor + 2\left\lfloor x + \frac34\right\rfloor + \left\lfloor x + \frac56\right\rfloor + \left\lfloor x + \frac78\right\rfloor</math>. There are <math>12</math> terms here (we don't actually have to write all of it out; we can just see where there will be duplicates and subtract accordingly from <math>20</math>). Starting from every integer <math>x</math>, we can keep adding to achieve one higher value for each of these terms, but after raising the last term, we will have raised the whole sum by <math>20</math> while only achieving <math>12</math> of those <math>20</math> values. We can conveniently shift the <math>1000</math> (since it can be achieved) to the position of the <math>0</math> so that there are only complete cycles of <math>20</math>, and the answer is <math>\frac {12}{20}\cdot1000 = \boxed{600}</math>.
 
<math>+ \left\lfloor x + \frac38\right\rfloor + 4\left\lfloor x + \frac12\right\rfloor + \left\lfloor x + \frac58\right\rfloor + \left\lfloor x + \frac23\right\rfloor + 2\left\lfloor x + \frac34\right\rfloor + \left\lfloor x + \frac56\right\rfloor + \left\lfloor x + \frac78\right\rfloor</math>. There are <math>12</math> terms here (we don't actually have to write all of it out; we can just see where there will be duplicates and subtract accordingly from <math>20</math>). Starting from every integer <math>x</math>, we can keep adding to achieve one higher value for each of these terms, but after raising the last term, we will have raised the whole sum by <math>20</math> while only achieving <math>12</math> of those <math>20</math> values. We can conveniently shift the <math>1000</math> (since it can be achieved) to the position of the <math>0</math> so that there are only complete cycles of <math>20</math>, and the answer is <math>\frac {12}{20}\cdot1000 = \boxed{600}</math>.
  
−
===Solution 4===
+
== Solution 4 ==
−
 
 
−
Imagine that we increase <math>x</math> from <math>0</math> to <math>1</math>. At the beginning, the value of our expression is <math>0</math>, at the end it is <math>2+4+6+8=20</math>. How many integers between <math>1</math> and <math>20</math> did we skip? We skip some integers precisely at those points where at least two of <math>2x</math>, <math>4x</math>, <math>6x</math>, and <math>8x</math> become integers at the same time.
 
−
 
 
−
Obviously, for <math>x=1/2</math> and <math>x=1</math> all four values become integers at the same time, hence we skip three integers at each of these locations. Additionally, for <math>x=1/4</math> and <math>x=3/4</math> the values <math>4x</math> and <math>8x</math> become integers at the same time, hence we skip one integer at each of the locations.
 
−
 
 
−
Therefore for <math>x\in(0,1]</math> we skip a total of <math>3+3+1+1=8</math> integers. As in Solution 2, we conclude that we hit <math>12</math> of the integers from <math>1</math> to <math>20</math>, and so we hit <math>50 \cdot 12 = \boxed{600}</math> of the first <math>1000</math>.
 
−
 
 
−
 
 
−
=== Solution 5 ===
 
  
 
Let <math>x=\lfloor x\rfloor+\{x\}</math> then
 
Let <math>x=\lfloor x\rfloor+\{x\}</math> then
Line 100: Line 94:
 
~ Nafer
 
~ Nafer
  
−
=== Solution 6 ===
+
== Solution 5 ==
 +
 
 +
To simplify the question, let <math>y = 2x</math>. Then, the expression in the question becomes <math>\lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor</math>.
 +
 
 +
Let <math>\{x\}</math> represent the non-integer part of <math>x</math> (For example, <math>\{2.8\} = 0.8</math>). Then,
 +
 
 +
<cmath>\begin{align*}
 +
\lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor &= y - \{y\} + 2y - \{2y\} + 3y - \{3y\} + 4y - \{4y\} \\
 +
&= 10y - (\{y\} + \{2y\} + \{3y\} + \{4y\}) \\
 +
&= 10(\lfloor y \rfloor + \{y\}) - (\{y\} + \{2y\} + \{3y\} + \{4y\}) \\
 +
&= 10\lfloor y \rfloor + 10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\}) \\
 +
&= 10\lfloor y \rfloor + 9\{y\} - (\{2y\} + \{3y\} + \{4y\}) \\
 +
\end{align*}</cmath>
  
−
First, let <math>y = 2x</math> to simplify the question. The expression in the question then becomes <math>\lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor</math>.
+
Since <math>\lfloor y \rfloor</math> is always an integer, <math>10\lfloor y \rfloor</math> will be a multiple of 10. Thus, we look for the range of the other part of the expression. We will be able to reach the same numbers when <math>y</math> ranges from <math>0</math> to <math>1</math>, because the curly brackets (<math>\{\}</math>) gets rid of any integer part. Let the combined integer part of <math>2y</math>, <math>3y</math>, and <math>4y</math> be <math>k</math> (In other words, <math>k = \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor</math>). Then,
  
−
Let <math>\{x\} = x - \lfloor x\rfloor</math>. Then, <math>\lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor</math> can be rewritten as <math>y - \{y\} + 2y - \{2y\} + 3y - \{3y\} + 4y - \{4y\}</math>, or <math>10y - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math>. Substituting <math>\lfloor y\rfloor + \{y\}</math> for <math>y</math> yields <math>10\lfloor y\rfloor + 10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math>. Since <math>10\lfloor y\rfloor</math> will always be a multiple of <math>10</math>, we must find the range of <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math>. Clearly, <math>10\{y\}\in \left[0, 10\right)</math> and <math>\{y\} + \{2y\} + \{3y\} + \{4y\}\in \left[0, 4\right)</math>. This suggests that <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math> is in the interval <math>\left[0, 6\right)</math>.
+
<cmath>\begin{align*}
 +
9\{y\} - (\{2y\} + \{3y\} + \{4y\}) &= 9\{y\} - (2\{y\} + 3\{y\} + 4\{y\} - k) \\
 +
&= 9\{y\} - (9\{y\} - k) \\
 +
&= k
 +
\end{align*}</cmath>
  
−
Next, we must prove that the expression hits every integer in that interval. To do this, we look at the intervals between places where the expression makes a discontinuous leap. This expression is not continuous when one of the values <math>\{y\}</math>, <math>\{2y\}</math>, <math>\{3y\}</math>, or <math>\{4y\}</math> resets to 0, which happens when <math>y</math>, <math>2y</math>, <math>3y</math>, or <math>4y</math> is an integer. This occurs when <math>\{y\} \in \left\{0, \dfrac14, \dfrac13, \dfrac12, \dfrac23, \dfrac34, 1\right\}</math>. In each of the intervals between these numbers, the expression is continuous. In the first interval, when <math>\{y\} \in \left[0, \dfrac14\right)</math>, <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math> ranges from <math>0</math> to <math>\dfrac52</math>. In the last interval, when <math>\{y\} \in \left[\dfrac34, 1\right)</math>, the expression ranges from <math>\dfrac32</math> to <math>4</math>. These two intervals combined hit all the numbers in <math>[0, 4)</math>. Thus, as <math>\{y\}</math> ranges from <math>0</math> to <math>1</math>, the expression <math>10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\})</math> hits all the numbers in the interval <math>[0, 6)</math>.  
+
The maximum value of <math>k</math> will be when <math>y</math> is slightly less than <math>1</math>, which means <math>k = 1 + 2 + 3 = 6</math>. As <math>y</math> increases from <math>0</math> to <math>1</math>, <math>k</math> will increase whenever <math>2y</math>, <math>3y</math>, or <math>4y</math> is an integer, which happens when <math>y</math> hits one of the numbers in the set <math>\left\{\dfrac14, \dfrac13, \dfrac12, \dfrac23, \dfrac34 \right\}</math>. When <math>y</math> reaches <math>\dfrac12</math>, both <math>2y</math> and <math>4y</math> will be an integer, so <math>k</math> will increase by <math>2</math>. For all the other numbers in the set, <math>k</math> increases by <math>1</math> since only <math>1</math> number in the set will be an integer. Thus, the possible values of <math>k</math> are <math>\{0, 1, 2, 4, 5, 6\}</math>.  
  
−
Finally, to find the answer, we know all integers that are less than 6 greater than a multiple of <math>10</math> can be expressed, so the answer is <math>\boxed{600}</math> (any number ending in <math>0</math>, <math>1</math>, <math>2</math>, <math>3</math>, <math>4</math>, or <math>5</math>).
+
Finally, looking back at the original expression, we plug in <math>k</math> to get a multiple of <math>10</math> plus any number in <math>\{0, 1, 2, 4, 5, 6\}</math>. Thus, we hit all numbers ending in <math>\{0, 1, 2, 4, 5, 6\}</math>, of which there are <math>\boxed{600}</math>.  
  
 
~Owen1204
 
~Owen1204
 +
 +
==Solution 6==
 +
 +
Imagine that we gradually increase <math>x</math> from <math>0</math> to <math>1</math>. At the beginning, the value of our expression is <math>0</math>, at the end it is <math>2+4+6+8=20</math>. Note that every time <math>x=\frac{a}{b}</math> for some positive integer <math>a</math> and a positive multiple <math>b</math> of either <math>2, 4, 6,</math> or <math>8</math>. Thus, we have been able to express 12 of the integers from 1 through 20 when <math>0<x<1</math>, namely when <cmath>x = \frac{1}{2}, \frac{2}{2}=1, \frac{1}{4}, \frac{3}{4}, \frac{1}{6}, \frac{1}{3}, \frac{2}{3}, \frac{5}{6}, \frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{7}{8}</cmath>.
 +
 +
 +
Notice that <cmath>\lfloor 2(x+n) \rfloor + \lfloor 4(x+n)\rfloor + \lfloor 6(x+n) \rfloor+ \lfloor8(x+n) \rfloor= \lfloor 2x \rfloor+ \lfloor 4x \rfloor+ \lfloor 6x \rfloor+ \lfloor 8x \rfloor+ 20n</cmath>. This conceptually means that the number of integers that can be expressed in the range <math>(i, j)</math> is the same as the number of integers that can be expressed in the range <math>(i+x, j+x)</math>. Thus, because we can express <math>12</math> integers in the range <math>(1, 20)</math>, we can cover <math>12*50 = \boxed{600}</math> from 1 to 1000.
 +
<math>-\text{thinker123}</math>
 +
 +
==Solution 7==
 +
 +
After observing, we can see that there are <math>6</math> values of can be evaluated through the expression every <math>10</math> numbers, so our answer is <math>6*100=600</math> ~bluesoul
  
 
== See also ==
 
== See also ==
Line 119: Line 141:
 
* [[Mathematics competition resources]]
 
* [[Mathematics competition resources]]
  
−
[[Category:Intermediate Algebra Problems]]
+
[[Category:Intermediate Number Theory Problems]]

Latest revision as of 17:16, 28 March 2022

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 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 $\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$, $\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 =\frac 18$.
  • $2$: Also simple, for example using $\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 = \boxed{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{lcm}(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 = \boxed{600}$ of the first $1000$.

Solution 2 Shortcut

Because $2,4,6,8$ are all multiples of $2$, we can speed things up. We only need to check up to $\frac{12}{24}$, and the rest should repeat. As shown before, we hit 6 integers ($1,2,4,5,6,10$) from $\frac{1}{24}$ to $\frac{12}{24}$. Similarly, this should repeat 100 times, for $\boxed{600}$

~N828335

Solution 2 Bigger Shortcut (Close to Solution 6)

We only need to check the numbers where it increments, namely $\frac{1}{8}, \frac{1}{6}, \frac{1}{4}, \frac{1}{3}, \frac{3}{8}, \frac{1}{2}$. As shown before, we hit 6 integers ($1,2,4,5,6,10$) from $\frac{1}{24}$ to $\frac{1}{2}$. Similarly, this should repeat 100 times, for $\boxed{600}$

~JeffersonJ

Solution 3

Recall from Hermite's Identity that $\sum_{k = 0}^{n - 1}\left\lfloor x + \frac kn\right\rfloor = \lfloor nx\rfloor$. Then we can rewrite $\lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 6x \rfloor + \lfloor 8x \rfloor = 4\lfloor x\rfloor + \left\lfloor x + \frac18\right\rfloor + \left\lfloor x + \frac16\right\rfloor + 2\left\lfloor x + \frac14\right\rfloor + \left\lfloor x + \frac13\right\rfloor$ $+ \left\lfloor x + \frac38\right\rfloor + 4\left\lfloor x + \frac12\right\rfloor + \left\lfloor x + \frac58\right\rfloor + \left\lfloor x + \frac23\right\rfloor + 2\left\lfloor x + \frac34\right\rfloor + \left\lfloor x + \frac56\right\rfloor + \left\lfloor x + \frac78\right\rfloor$. There are $12$ terms here (we don't actually have to write all of it out; we can just see where there will be duplicates and subtract accordingly from $20$). Starting from every integer $x$, we can keep adding to achieve one higher value for each of these terms, but after raising the last term, we will have raised the whole sum by $20$ while only achieving $12$ of those $20$ values. We can conveniently shift the $1000$ (since it can be achieved) to the position of the $0$ so that there are only complete cycles of $20$, and the answer is $\frac {12}{20}\cdot1000 = \boxed{600}$.

Solution 4

Let $x=\lfloor x\rfloor+\{x\}$ then \begin{align*} \lfloor 2x\rfloor+\lfloor 4x\rfloor+\lfloor 6x\rfloor+\lfloor 8x\rfloor&=\lfloor 2(\lfloor x\rfloor+\{x\})\rfloor+\lfloor 4(\lfloor x\rfloor+\{x\})\rfloor+\lfloor 6(\lfloor x\rfloor+\{x\})\rfloor+\lfloor 8(\lfloor x\rfloor+\{x\})\rfloor\\ &=2\lfloor x\rfloor+4\lfloor x\rfloor+6\lfloor x\rfloor+8\lfloor x\rfloor+\lfloor 2\{x\}\rfloor+\lfloor 4\{x\}\rfloor+\lfloor 6\{x\}\rfloor+\lfloor 8\{x\}\rfloor\\ &=20\lfloor x\rfloor+(\lfloor 2\{x\}\rfloor+\lfloor 4\{x\}\rfloor+\lfloor 6\{x\}\rfloor+\lfloor 8\{x\}\rfloor) \end{align*} Similar to the previous solutions, the value of $\lfloor 2\{x\}\rfloor+\lfloor 4\{x\}\rfloor+\lfloor 6\{x\}\rfloor+\lfloor 8\{x\}\rfloor$ changes when $\{x\}=\frac{m}{n}$, where $m\in\{1,2,3,...,n-1\}$, $n\in\{2,4,6,8\}$. Using Euler's Totient Function \[\sum\limits_{k=0}^4 \phi(2k)\] to obtain $12$ different values for $\{x\}=\frac{m}{n}$. (note that here Euler's Totient Function counts the number of $\{x\}=\frac{m}{n}$ where $m$, $n$ are relatively prime so that the values of $\{x\}$ won't overlap.).

Thus if $k$ can be expressed as $\lfloor 2x\rfloor+\lfloor 4x\rfloor+\lfloor 6x\rfloor+\lfloor 8x\rfloor$, then $k=20a+b$ for some non-negative integers $a$, $b$, where there are $12$ values for $b$.

Exclusively, there are $49$ values for $a$ in the range $0<k<1000$, or $49\cdot12=588$ ordered pairs $(a,b)$.

If $a=0$, $b\neq0$, which includes $11$ ordered pairs.

If $a=50$, $b=0$, which includes $1$ ordered pair.

In total, there are $588+11+1=\boxed{600}$ values for $k$.

~ Nafer

Solution 5

To simplify the question, let $y = 2x$. Then, the expression in the question becomes $\lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor$.

Let $\{x\}$ represent the non-integer part of $x$ (For example, $\{2.8\} = 0.8$). Then,

\begin{align*} \lfloor y \rfloor + \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor &= y - \{y\} + 2y - \{2y\} + 3y - \{3y\} + 4y - \{4y\} \\ &= 10y - (\{y\} + \{2y\} + \{3y\} + \{4y\}) \\ &= 10(\lfloor y \rfloor + \{y\}) - (\{y\} + \{2y\} + \{3y\} + \{4y\}) \\ &= 10\lfloor y \rfloor + 10\{y\} - (\{y\} + \{2y\} + \{3y\} + \{4y\}) \\ &= 10\lfloor y \rfloor + 9\{y\} - (\{2y\} + \{3y\} + \{4y\}) \\ \end{align*}

Since $\lfloor y \rfloor$ is always an integer, $10\lfloor y \rfloor$ will be a multiple of 10. Thus, we look for the range of the other part of the expression. We will be able to reach the same numbers when $y$ ranges from $0$ to $1$, because the curly brackets ($\{\}$) gets rid of any integer part. Let the combined integer part of $2y$, $3y$, and $4y$ be $k$ (In other words, $k = \lfloor 2y \rfloor + \lfloor 3y \rfloor + \lfloor 4y \rfloor$). Then,

\begin{align*} 9\{y\} - (\{2y\} + \{3y\} + \{4y\}) &= 9\{y\} - (2\{y\} + 3\{y\} + 4\{y\} - k) \\ &= 9\{y\} - (9\{y\} - k) \\ &= k \end{align*}

The maximum value of $k$ will be when $y$ is slightly less than $1$, which means $k = 1 + 2 + 3 = 6$. As $y$ increases from $0$ to $1$, $k$ will increase whenever $2y$, $3y$, or $4y$ is an integer, which happens when $y$ hits one of the numbers in the set $\left\{\dfrac14, \dfrac13, \dfrac12, \dfrac23, \dfrac34 \right\}$. When $y$ reaches $\dfrac12$, both $2y$ and $4y$ will be an integer, so $k$ will increase by $2$. For all the other numbers in the set, $k$ increases by $1$ since only $1$ number in the set will be an integer. Thus, the possible values of $k$ are $\{0, 1, 2, 4, 5, 6\}$.

Finally, looking back at the original expression, we plug in $k$ to get a multiple of $10$ plus any number in $\{0, 1, 2, 4, 5, 6\}$. Thus, we hit all numbers ending in $\{0, 1, 2, 4, 5, 6\}$, of which there are $\boxed{600}$.

~Owen1204

Solution 6

Imagine that we gradually increase $x$ from $0$ to $1$. At the beginning, the value of our expression is $0$, at the end it is $2+4+6+8=20$. Note that every time $x=\frac{a}{b}$ for some positive integer $a$ and a positive multiple $b$ of either $2, 4, 6,$ or $8$. Thus, we have been able to express 12 of the integers from 1 through 20 when $0<x<1$, namely when \[x = \frac{1}{2}, \frac{2}{2}=1, \frac{1}{4}, \frac{3}{4}, \frac{1}{6}, \frac{1}{3}, \frac{2}{3}, \frac{5}{6}, \frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{7}{8}\].


Notice that \[\lfloor 2(x+n) \rfloor + \lfloor 4(x+n)\rfloor + \lfloor 6(x+n) \rfloor+ \lfloor8(x+n) \rfloor= \lfloor 2x \rfloor+ \lfloor 4x \rfloor+ \lfloor 6x \rfloor+ \lfloor 8x \rfloor+ 20n\]. This conceptually means that the number of integers that can be expressed in the range $(i, j)$ is the same as the number of integers that can be expressed in the range $(i+x, j+x)$. Thus, because we can express $12$ integers in the range $(1, 20)$, we can cover $12*50 = \boxed{600}$ from 1 to 1000. $-\text{thinker123}$

Solution 7

After observing, we can see that there are $6$ values of can be evaluated through the expression every $10$ numbers, so our answer is $6*100=600$ ~bluesoul

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=173032"