MHB Finding Real Solutions to the Floor Function Equation: A Scientific Approach

[anemone]

Solve for real (if there is any) of the equation $\left\lfloor{a}\right\rfloor+\left\lfloor{2a}\right\rfloor+\left\lfloor{4a}\right\rfloor+\left\lfloor{8a}\right\rfloor+\left\lfloor{16a}\right\rfloor=300$.

 

[Nono713]

Solve for real (if there is any) of the equation $\left\lfloor{a}\right\rfloor+\left\lfloor{2a}\right\rfloor+\left\lfloor{4a}\right\rfloor+\left\lfloor{8a}\right\rfloor+\left\lfloor{16a}\right\rfloor=300$.

I might clean this up tomorrow, I'm sure there is a nicer proof:

Spoiler

Define a function $f : \mathbb{R} \to \mathbb{N}$ as:
$$f(x) = \sum_{k = 0}^4 \lfloor 2^k x \rfloor = \lfloor x \rfloor + \lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 8x \rfloor + \lfloor 16x \rfloor$$
The floor function is monotonic, and so $f$ is monotonic as well. Thus the solutions to the equation $f(x) = 300$ can be numerically approximated to get an idea of where they lie. Via bisection, we find that $f(x) = 298$ for $x \to 9.75$, but jumps to $301$ at $x = 9.75$. We can thus conclude that the solutions, if any exist, must lie in, say, $\left ( 9.74, 9.75 \right )$. Thus, let $x \in \left ( 9.74, 9.75 \right )$. Write it as $x = 9.74 + \epsilon$ for some $0 < \epsilon < 0.01$. Then we have:
$$f(x) = \lfloor 9.74 + \epsilon \rfloor + \lfloor 19.48 + 2\epsilon \rfloor + \lfloor 38.96 + 4\epsilon \rfloor + \lfloor 77.92 + 8 \epsilon \rfloor + \lfloor 155.84 + 16 \epsilon \rfloor$$
And hence it immediately follows from $\epsilon < 0.01$ that:
$$f(x) = 9 + 19 + 38 + 77 + 155 = 298$$
In other words, $f(x) = 298$ for all $x$ approaching $9.75$, and then jumps to $f(x) = 301$ for $x = 9.75$ without taking on the value $300$. Thus there is no solution to the equation $f(x) = 300$. $\blacksquare$

Intuitively, observe that for $\epsilon < 0.01$, only the last three terms can "cross the threshold", as $9.74 + \epsilon$ and $19.48 + 2 \epsilon$ are not close enough to an integer boundary. They also cross the threshold at the same time, and thus $f$ can increase by a minimum of $3$ at that point, and therefore skips $300$.

​

 

[anemone]

I might clean this up tomorrow..

Thanks for participating, Bacterius, and I will wait for you (for another few days) just in case you're busy but want to edit it or post for another "cleaned up" solution. :)

I still welcome others to take a stab at it in the mean time...

 

[Nono713]

Thanks for participating, Bacterius, and I will wait for you (for another few days) just in case you're busy but want to edit it or post for another "cleaned up" solution. :)

I still welcome others to take a stab at it in the mean time...

Yeah, I figured it out. Here we go:

Spoiler

Define a function $f(x) : \mathbb{R} \mapsto \mathbb{N}$ as:
$$f(x) = \lfloor x \rfloor + \lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 8x \rfloor + \lfloor 16x \rfloor$$
Note that if $f(x) = n$, then $f(x + 1) = n + 1 + 2 + 4 + 8 + 16 = n + 31$, and vice versa. Thus it follows that $f(x) = n$ if and only if $f(y) = n \bmod{31}$ for some $0 \leq y < 1$. Thus $x \mapsto f(x) \bmod{31}$ is periodic with unit period.

Therefore it suffices to check all possible values of $f(x)$ over the unit interval. To do this, proceed as follows: start at $x = 0$, look at all five terms, and check which one of the floored terms will reach an integer boundary first (so that $f$ increase). Increase $x$ to that value, and repeat. This is guaranteed to produce all solutions in the given interval, since $f$ is monotonic.

Iterating this algorithm, we get that $f(x)$ takes the following values over $[0, 1)$:
$$S = \{ 0, 1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19, 22, 23, 25, 26 \}$$
Invoking the periodicity of $f$, we arrive at the conclusion that $f(x) = n$ has solutions if and only if $n \bmod{31} \in S$. And $300 \bmod{31} = 21$, so $f(x) = 300$ has no solutions. Notice that $301 \bmod{31} = 22$ and $298 \bmod{31} = 19$ which are both in $S$, which nicely generalizes the earlier proof's observations.

 

[mathbalarka]

The clever work is all done by Bacterius, so I'll do the tedious job - here's a neat method for computing $S$ (not sure if this is what he meant by "increase $x$ and repeat") :

Spoiler

Consider $x \in [0, 1)$, and partition the interval as $ \bigcup_{1 \leq i \leq 16}^\star (i/16-1/16, i/16] \cup \{0\}$ where the star indicates that the interval for $i = 16$ is totally open.

If $x = 0$, $f(x) = 0 + 0 + 0 + 0 + 0 = 0$.
If $x \in (0, 1/16]$, $f(x) = 0 + 0 + 0 + 0 + 1 = 1$
If $x \in (1/16, 2/16]$, $f(x) = 0 + 0 + 0 + 1 + 2 = 3$
If $x \in (2/16, 3/16]$, $f(x) = 0 + 0 + 0 + 1 + 3 = 4$
If $x \in (3/16, 4/16]$, $f(x) = 0 + 0 + 1 + 2 + 4 = 7$
If $x \in (4/16, 5/16]$, $f(x) = 0 + 0 + 1 + 2 + 5 = 8$
If $x \in (5/16, 6/16]$, $f(x) = 0 + 0 + 1 + 3 + 6 = 10$
If $x \in (6/16, 7/16]$, $f(x) = 0 + 0 + 1 + 3 + 7 = 11$
If $x \in (7/16, 8/16]$, $f(x) = 0 + 1 + 2 + 4 + 8 = 15$
If $x \in (8/16, 9/16]$, $f(x) = 0 + 1 + 2 + 4 + 9 = 16$
If $x \in (9/16, 10/16]$, $f(x) = 0 + 1 + 2 + 5 + 10 = 18$
If $x \in (10/16, 11/16]$, $f(x) = 0 + 1 + 2 + 5 + 11 = 19$
If $x \in (11/16, 12/16]$, $f(x) = 0 + 1 + 3 + 6 + 12 = 22$
If $x \in (12/16, 13/16]$, $f(x) = 0 + 1 + 3 + 6 + 13 = 23$
If $x \in (13/16, 14/16]$, $f(x) = 0 + 1 + 3 + 7 + 14 = 25$
If $x \in (14/16, 15/16]$, $f(x) = 0 + 1 + 3 + 7 + 15 = 26$
If $x \in (15/16, 1)$, $f(x) = 0 + 1 + 3 + 7 + 15 = 26$

Thus, all the possible values $f(x)$ takes on $[0, 1)$ is $S = \{ 0, 1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19, 22, 23, 25, 26\}$.

PS : This in no way stands as a possible solution to the question asked. It's an addendum to Bacterius's solution above.

 

[anemone]

Yeah, I figured it out. Here we go:

Spoiler

Define a function $f(x) : \mathbb{R} \mapsto \mathbb{N}$ as:
$$f(x) = \lfloor x \rfloor + \lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 8x \rfloor + \lfloor 16x \rfloor$$
Note that if $f(x) = n$, then $f(x + 1) = n + 1 + 2 + 4 + 8 + 16 = n + 31$, and vice versa. Thus it follows that $f(x) = n$ if and only if $f(y) = n \bmod{31}$ for some $0 \leq y < 1$. Thus $x \mapsto f(x) \bmod{31}$ is periodic with unit period.

Therefore it suffices to check all possible values of $f(x)$ over the unit interval. To do this, proceed as follows: start at $x = 0$, look at all five terms, and check which one of the floored terms will reach an integer boundary first (so that $f$ increase). Increase $x$ to that value, and repeat. This is guaranteed to produce all solutions in the given interval, since $f$ is monotonic.

Iterating this algorithm, we get that $f(x)$ takes the following values over $[0, 1)$:
$$S = \{ 0, 1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19, 22, 23, 25, 26 \}$$
Invoking the periodicity of $f$, we arrive at the conclusion that $f(x) = n$ has solutions if and only if $n \bmod{31} \in S$. And $300 \bmod{31} = 21$, so $f(x) = 300$ has no solutions. Notice that $301 \bmod{31} = 22$ and $298 \bmod{31} = 19$ which are both in $S$, which nicely generalizes the earlier proof's observations.

Well done, Bacterius! Thanks for participating...thanks to you too, Balarka for your post!

Here is another easy proof of other that I wanted to share:

Spoiler

Suppose that there is one real $a>0$ that satisfies

$\left\lfloor{a}\right\rfloor+\left\lfloor{2a}\right\rfloor+\left\lfloor{4a}\right\rfloor+\left\lfloor{8a}\right\rfloor+\left\lfloor{16a}\right\rfloor=300$.

Then we may write

$a=N+\dfrac{p}{2}+\dfrac{q}{4}+\dfrac{r}{8}+\dfrac{s}{16}+t$ where $N$ is a positive integer, $p,q,r,s\in \{0,1\}$ and $t\in\left[0,\,\dfrac{1}{16}\right)$.

We then obtain, from the original equation

$30N+15p+7q+3r+s=300$

Thus, $300N< 300\,\,\,\rightarrow\,\,\,N< 10$

Also, $300< 300N+15+7+3+1\,\,\,\rightarrow\,\,\,N< 9\dfrac{2}{15}$

Putting these two results together, we see that $9\dfrac{2}{15}< N < 10$, which is impossible since $N$ is supposed to be an integer.

Therefore, the original equation has no solution.