Where's The Borderline?

Relevant wiki: Floor and Ceiling Functions - Problem Solving

Let $f(x) = \lfloor 2x \rfloor \lfloor 3x \rfloor$

Important Fact: $\lfloor x \rfloor$ is a function that remains constant, and only changes its value (increases by 1) when $x$ crosses an integer, say $n$ .

Therefore $\lfloor 2x\rfloor$ increases when $x$ crosses $\frac{n}{2}$ and $\lfloor 3x \rfloor$ increases when $x$ crosses $\frac{n}{3}$ .

$\lfloor 2x \rfloor \lfloor 3x \rfloor$ will increase when $x$ crosses $\frac{n}{6}$ .

Another important fact: The floor function is neither odd nor even, so we need to take two cases separately : $x$ is non-negative, and $x$ is negative.

---

Case 1: $x$ is non-negative

Note that when $x$ is an integer $n$ , $f$ will be equal to $6n^2$ . So all numbers of the form $6n^2$ can be written in this form.

Now let's see how the value of $f$ changes as $x$ varies from $n$ to $n+1$ . Since the period of $f$ is $\text{lcm}( \frac{1}{2} , \frac{1}{3}) = 1$ , we can be sure that the same pattern will be followed as $x$ goes from $n+1$ to $n+2$ .

As we saw above, $f$ only changes when $x$ crosses and integral multiple of $\frac{1}{6}$ , we can divide the interval $[n, n+1)$ into $6$ equal intervals.

$\begin{array}{|l|c|c|c|}\hline \text{Interval} & \lfloor 2x \rfloor & \lfloor 3x \rfloor & f(x) \\\hline \left[n, n + \frac{1}{6}\right) & 2n & 3n & 6n^{2} \\ \left[n + \frac{1}{6}, n + \frac{2}{6}\right) & 2n & 3n & 6n^{2}\\ \left[n + \frac{2}{6}, n + \frac{3}{6}\right) & 2n & 3n + 1& 6n^{2} + 2n\\ \left[n + \frac{3}{6}, n + \frac{4}{6}\right) & 2n + 1& 3n + 1& 6n^{2} + 5n + 1\\ \left[n + \frac{4}{6}, n + \frac{5}{6}\right) & 2n + 1& 3n + 2& 6n^{2} + 7n + 2\\ \left[n + \frac{5}{6}, n + 1\right) & 2n + 1& 3n + 2& 6n^{2} + 7n + 2\\\hline \end{array}$

We see that there are 4 distinct values that $f$ takes as $x$ goes from $n$ to $n + 1$ viz. $6n^2, 6n^2 +2n, 6n^2 + 5n + 1, 6n^2 + 7n + 2$ .

When $n = 0$ , we only get two values - $1, 2$ since we don't want 0. For all $n > 0$ , we get 4 values, for example for $n = 1$ , we get $6, 8, 12$ and $15$ . These are the numbers that can be written in the desired form. If we arrange them in ascending order, it is not hard to prove that $f(n) = 6n^2$ will be the $(4n - 1)^{\text{th}}$ term in the sequence.

$1$ is the minimum number in the range of $f$ . To find the maximum number less than $10000$ , the easiest way would be to find the greatest possible $n$ , by setting $6n^2 \leq 10000$ .

$\implies n^2 \leq 1666$

$\implies n \leq 40$

The maximum $n$ is $40$ .

Now we check if $f(40 + \frac{5}{6}) < 10000$ .

$f(40 + \frac{5}{6}) = 6 \times 40^2 + 7 \times 40 + 2 = 9882 \leq 10000$ which works as well.

We know that $f(40) = 6 \times 40^2 = 9600$ is the $(4 \times 40 - 1)$ th term, ie $159$ th term. Therefore $9882$ will be the $159 + 3 = 162$ th term.

However, we mustn't forget Case 2, in which $x$ is negative.

---

Case 2: $x$ is negative.

For some negative integer $k$ , let $m = k - \frac{1}{2}$ . The motivation to do this will become clear shortly. Now let's see how $f$ varies as $x$ goes from $m$ to $m + 1$ .

$\begin{array}{|l|c|c|c|}\hline \text{Interval} & \lfloor 2x \rfloor & \lfloor 3x \rfloor & f(x) \\\hline \left[m + \frac{5}{6}, m\right) & 2k & 3k + 1 & 6k^{2} + 2k\\ \left[m + \frac{4}{6}, m + \frac{5}{6}\right) & 2k & 3k & 6k^{2}\\ \left[m + \frac{3}{6}, m + \frac{4}{6}\right) & 2k & 3k & 6k^{2}\\ \left[m + \frac{2}{6}, m + \frac{3}{6}\right) & 2k - 1& 3k - 1& 6k^{2} - 5k + 1\\ \left[m + \frac{1}{6}, m + \frac{2}{6}\right) & 2k - 1& 3k - 1& 6k^{2} - 7k + 2\\ \left[m, m + \frac{1}{6}\right) & 2k - 1& 3k - 2& 6k^{2} - 7k + 2\\\hline \end{array}$

Since $k$ is a negative number, we can replace it by $- n$ , where $n$ is a positive number. Observe for each $n$ , the outputs are now $6n^2 - 2n, 6n^2 , 6n^2 + 5n + 1, 6n^2 + 7n + 2$ .

That is, for each $n$ , $f(- n)$ has exactly one element in its range ( $6n^2 - 2n$ ) which is not present in range of $f(n)$ , ie a one-to-one correspondence. Since we calculated $n$ to be $40$ in the previous case, there will be $40$ more numbers which can be written in this form if $x$ is negative.

---

There are $162 + 40 = \boxed{202}$ integers from $1$ to $10000$ which can be written as $\lfloor 2x \rfloor \lfloor 3x \rfloor$ $_\square$ .

Let $i(x) = \lfloor 2x \rfloor \lfloor 3x \rfloor$ . Consider $n \le x < n+1$ , where $n$ is an integer, then there are $4$ integers $i(x)$ generated (see figure below).

$\quad \quad \quad i(x) = \begin{cases} 6n^2 & n \le x < n+\frac{1}{3} \\ 2n(3n+1) & n+\frac {1}{3} \le x < n+\frac{1}{2} \\ (2n+1)(3n+1) & n+\frac {1}{2} \le x < n+\frac{2}{3} \\ (2n+1)(3n+2) & n+\frac {2}{3} \le x < n+1 \end{cases}$

This is true for $x < 0$ . To only consider non-negative $n$ , we do the following:

$\begin{cases} 6m^2 \\ 2m(3m+1) \\ (2m+1)(3m+1) \\ (2m+1)(3m+2) \end{cases}$

$\Rightarrow \begin{cases} 6(-m)^2 & = 6(m)^2 \\ (-2m)[-(3m-1)] & = 2m(3m-1) \\ [-(2m-1)][-(3m-1)] &= (2m-1)(3m-1) \\ [-(2m-1)][-(3m-2)] & = (2m-1)(3m-2) \end{cases}$

Replace $m = n + 1$ , we have:

$\Rightarrow \begin{cases} 6(m)^2 & = 6(n+1)^2 \\ 2m(3m-1) & = 2(n+1)(3n+2) \\ (2m-1)(3m-1) & = (2n+1)(3n+2) \\ (2m-1)(3m-2) & = (2n+1)(3n+1)\\ \end{cases}$

We note that negative $n$ introduce an extra $i(x) = 2(n+1)(3n+2)$ . Therefore, for each positive $n$ we have five $i(x)$ as follows:

$i(n) = \begin{cases} 6n^2 \\ 2n(3n+1) \\ (2n+1)(3n+1) \\ (2n+1)(3n+2) \\ 2(n+1)(3n+2) \end{cases}\space \text{and} \space i(0) = \begin{cases} 0 \\ 0 \\ 1 \\ 2 \\ 4 \end{cases}$

For $i(n) \ge 10000$ , we have:

$2(n+1)(3n+2) \ge 10000\quad \Rightarrow (n+1)(3n+2) \ge 5000$

$\Rightarrow 3n^2 + 5n - 4998 \ge 0\quad \Rightarrow n \ge 39.99$

And we note that: $\space i(40) = \begin{cases} 9600 \\ 9680 \\ 9801 \\ 9882 \\ 10004 \end{cases}$

Therefore, the number of integers from $1$ to $10000$ can be written as $\lfloor 2x \rfloor \lfloor 3x \rfloor$ is:

$N = 41 \times 5 - 3 = \boxed{202}$

I have a (somewhat inefficient but still very fast) Java solution. It is based on the fact that since we are only looking for values between 1 and 10,000, $-41 < x < 41.$
Link 1
Link 2 (if Link 1 doesn't work)
EDIT: the increment I use to check for new values of n is $\Delta x = 0.01$ , but there is a much greater value of $\Delta x$ that still guarantees the correct answer. I wonder what it is?

PROGRAM Floor 2x and _3x; {202 = 40 + 122 + 40. 1 tenth. Flexible for each check.}

USES CRT;

VAR i, count: LONGINT; n, x: EXTENDED; num, num1, num2: ARRAY[1..10001] OF WORD; Skip: BOOLEAN;

FUNCTION Flr(x: EXTENDED): LONGINT; BEGIN IF x<0.0 THEN Flr:=TRUNC(x)-1 ELSE Flr:=TRUNC(x) END;

FUNCTION Dmp(x: EXTENDED): LONGINT; BEGIN IF x>10000.0 THEN Dmp:=10001 ELSE Dmp:=TRUNC(x) END;

BEGIN CLRSCR;

 FOR i:=1 TO 10001 DO
     Num1[i]:=i;

 FOR i:=1 TO 10001 DO
     Num2[i]:=i;

 WRITELN('Fine verification to tenth requires about 0.6 seconds...');
 n:=0.0;
 REPEAT
       x:=0.1*n;

       Num1[Dmp(1.0*Flr(2.0*x)*Flr(3.0*x))]:=0;
       Num2[Dmp(1.0*Flr(-2.0*x)*Flr(-3.0*x))]:=0;

       n:=n+1.0
 UNTIL n>100000.0;

 CLRSCR;
 WRITELN('Verification completed. Do you want to see one by one for counts?');
 WRITE('If NO then press [N] else press [ENTER] to read> ');
 IF UPCASE(READKEY)='N' THEN
    Skip:=TRUE
 ELSE
     Skip:=FALSE;
 WRITELN;

 FOR i:=1 TO 10001 DO
     Num[i]:=i;

 count:=0;
 FOR i:=1 TO 10000 DO
     IF (Num1[i]=0) OR (Num2[i]=0) THEN {Can be changed to count for others.}
     BEGIN
          INC(count);
          IF NOT Skip THEN
          BEGIN
             WRITELN(Num[i]:4, '; Count = ', count);
             IF READKEY=#27 THEN
                Skip:=TRUE
          END
          ELSE
             WRITELN(Num[i]:4, '; Count = ', count)
     END;
 WRITELN;
 WRITE('Total counts = ', count, '    ', 'Press [Esc] to quit> ');
 REPEAT UNTIL READKEY=#27

END.