1
$\begingroup$

Recently I had solved this number theory problem but after I solved it I was a bit uncertain whether my approach was correct so I approached AOPS.

The problem is :

Prove that $[x] + [y] + [x + y] \leq [2x] + [2y]$.

My proof goes as follows:

We know that $x - 1 < [x] \leq x$, $y - 1 < [y] \leq y$ and $x + y - 1 < [x + y] \leq x + y$.

So adding up all these inequalities we get

$$ 2x + 2y - 3 < [x] + [y] + [x + y] \leq 2x + 2y$$

Which could be divided into two inequalities as

$$\color{blue}{2x + 2y - 3 < [x] + [y] + [x + y] \leq 2x + 2y - 1 \tag1}$$

$$\color{blue}{2x + 2y - 1 < [x] + [y] + [x + y] \leq 2x + 2y \tag2}$$

And similarly we also know that $2x + 2y - 1 < [2x] + [2y] \leq 2x + 2y$, now using this with inequality $(1)$ we get, $$ [x] + [y] + [x + y] < [2x] + [2y]$$ and similarly by subtracting with inequation $(2)$ we get $$0 < [x] + [y] + [x + y] - ([2x] + ([2y]) \leq 0$$ as the box function can only take integer values we get $[x] + [y] + [x + y] = [2x] + [2y]$ and this completes the proof.

I didn't get any reply on AOPS but a lot many people pointed out on how I split the inequality $2x + 2y - 3 < [x] + [y] + [x + y] \leq 2x + 2y$ into inequalities $(1)$ and $(2)$.

Is it wrong to split it as such? I had used this technique in proving a few other problems so it would be helpful to know whether this approach is right.

$\endgroup$
  • 1
    $\begingroup$ One of your inequalities, $\ 2x+2y-1 <\lfloor 2x\rfloor + \lfloor 2y\rfloor\ $, is not correct in general. Take $\ x=y=1.9\ $, for instance, when $ 2x+2y-1 = 6.6 > 6=\lfloor 2x\rfloor + \lfloor 2y\rfloor\ $. $\endgroup$ – lonza leggiera Apr 23 at 23:02
0
$\begingroup$

First, as noted in a question comment by lonza leggiera, your statement of

And similarly we also know that $2x + 2y - 1 < [2x] + [2y] \leq 2x + 2y$

is not correct. Note you have $2$ floor functions being used, so each $1$ is up to $1$ less, for an overall total of $2$ less. In particular, $2x - 1 \lt \lfloor 2x \rfloor \le 2x$ and $2y - 1 \lt \lfloor 2y \rfloor \le 2y$. Combining these gives

$$2x + 2y - 2 \lt \lfloor 2x \rfloor + \lfloor 2y \rfloor \le 2x + 2y \tag{1}\label{eq1}$$

As to your main question, splitting an inequality into $2$ parts can be used in certain cases, but you should make it clear what you're doing & why it works. However, there's another major issue here. Your use of the first part, after making the appropriate adjustment based on \eqref{eq1}, is fine. However, with the second inequality split, you're basically assuming that if $a \lt b$ and $c \lt d$, then $a - c \lt b - d$. This is not always true. For example, $1 \lt 2$ and $0 \lt 3$, but $1 - 0 \gt 2 - 3$. You can add similar inequalities, i.e., if $a \lt b$ and $c \lt d$, then $a + c \lt b + d$, but subtracting them doesn't always work. This is because subtracting basically involves multiplying both sides of the second inequality by $-1$ and then adding. However, the inequality becomes reversed when you multiply by $-1$. In other words, you have $a \lt b$ and $-c \gt -d$, with the latter becoming $-d \lt -c$, so you can only properly state that $a - d \lt b - c$.

I don't see any particularly easy to properly finish the proof using these split of inequalities. Instead, my first approach to these types of problems is it to define the values in terms of their integer & fractional parts. Due to the $2$ uses of $x$ & $y$ on the LHS, plus $2x$ and $2y$ on the RHS, as skrublord420 suggests in your post, you only need to check values in $[0,1)$ for $\lfloor x + y \rfloor \le \lfloor 2x \rfloor + \lfloor 2y \rfloor$. However, assuming you don't see this offhand, then more generally let

$$x = n_1 + r_1, \; n_1 \in \mathbb{Z}, \; 0 \le r_1 \lt 1 \tag{2}\label{eq2}$$ $$y = n_2 + r_2, \; n_2 \in \mathbb{Z}, \; 0 \le r_2 \lt 1 \tag{3}\label{eq3}$$

You basically want to prove that

$$\lfloor 2x \rfloor + \lfloor 2y \rfloor - \lfloor x + y \rfloor - \lfloor x \rfloor - \lfloor y \rfloor \ge 0 \tag{4}\label{eq4}$$

The factor of $2$ for $x$ and $y$ indicates checking $r_1$ and $r_2$ in the $4$ cases where $0 \le r_i \lt 0.5$ and $0.5 \le r_i \lt 1$, for $i = 1, 2$. However, due to the symmetry here in $x$ and $y$, you can reduce the work slightly by assuming, WLOG, that $r_2 \ge r_1$, so you don't need to check the one case where $0.5 \le r_1 \lt 1$ and $0 \le r_2 \lt 0.5$, thus leaving only $3$ cases to check. I'll do $2$ cases & leave the last one for you to do. First, consider $0 \le r_1 \lt 0.5$ and $0 \le r_2 \lt 0.5$. In this case, the LHS of \eqref{eq4} becomes

$$2n_1 + 2n_2 - (n_1 + n_2) - n_1 - n_2 = 0 \tag{5}\label{eq5}$$

Next, consider $0 \le r_1 \lt 0.5$ and $0.5 \le r_2 \lt 1$. The LHS of \eqref{eq4} becomes

$$2n_1 + (2n_2 + 1) - \lfloor (n_1 + n_2) + (r_1 + r_2) \rfloor - n_1 - n_2 = n_1 + n_2 + 1 - \lfloor (n_1 + n_2) + (r_1 + r_2) \rfloor \tag{6}\label{eq6}$$

Note that $0 \le r_1 + r_2 \lt 2$, so either $\lfloor (n_1 + n_2) + (r_1 + r_2) \rfloor = n_1 + n_2$, in which case \eqref{eq6} is $1$, or $\lfloor (n_1 + n_2) + (r_1 + r_2) \rfloor = n_1 + n_2 + 1$, in which case \eqref{eq6} is $0$.

The remaining case to check is $0.5 \le r_1 \lt 1$ and $0.5 \le r_2 \lt 1$ to finish verifying the inequality you want to prove.

Update: You can simplify the calculations a bit by substituting \eqref{eq2} and \eqref{eq3} into the LHS of \eqref{eq4}, and noting that $\lfloor x \rfloor = n_1$ and $\lfloor y \rfloor = n_2$, to get

$$2n_1 + \lfloor 2r_1 \rfloor + 2n_2 + \lfloor 2r_2 \rfloor - (n_1 + n_2) - \lfloor r_1 + r_2 \rfloor - n_1 - n_2 = \lfloor 2r_1 \rfloor + \lfloor 2r_2 \rfloor - \lfloor r_1 + r_2 \rfloor \tag{7}\label{eq7}$$

Being able to ignore the integer parts of $x$ and $y$ is basically what I commented on earlier as being originally suggested by skrublord420.

$\endgroup$
  • $\begingroup$ I didn't know if a < b and c < d then that need not imply a - c < b - d. That added a lot of clarity. Thanks ! $\endgroup$ – Deepam Sarmah Apr 24 at 5:17
  • $\begingroup$ @DeepamSarmah You're welcome. It's easy to make mistakes when working with inequalities if you're not careful; I've done it myself a few times! $\endgroup$ – John Omielan Apr 24 at 5:18
  • $\begingroup$ @DeepamSarmah I added an update stating a small simplification that shows you can, in your case, basically ignore the integer parts of $x$ and $y$. $\endgroup$ – John Omielan Apr 24 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.