Difference between revisions of "1985 AIME Problems/Problem 10"

Revision as of 20:33, 25 July 2020

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 $\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 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

Imagine that we 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$ . How many integers between $1$ and $20$ did we skip? We skip some integers precisely at those points where at least two of $2x$ , $4x$ , $6x$ , and $8x$ become integers at the same time.

Obviously, for $x=1/2$ and $x=1$ all four values become integers at the same time, hence we skip three integers at each of these locations. Additionally, for $x=1/4$ and $x=3/4$ the values $4x$ and $8x$ become integers at the same time, hence we skip one integer at each of the locations.

Therefore for $x\in(0,1]$ we skip a total of $3+3+1+1=8$ integers. As in Solution 2, we conclude that we hit $12$ of the integers from $1$ to $20$ , and so we hit $50 \cdot 12 = \boxed{600}$ of the first $1000$ .

Solution 5

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

@@ Line 100: / Line 100: @@
 ~ Nafer
-=== Solution 6 ===
-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>.
-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>.
-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>.
-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>).
 == 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

Page

Toolbox

Search