4
$\begingroup$

I want to solve for minimum value of $n$ such that$$ \lceil x\rceil - \frac{\lceil nx\rceil} n \geqslant y $$ with $x$ and $y$ given. I want to arrive at the value of $n$ in a computer program without brute forcing values of $n$.

Also, what is the maximum/minimum value of $$ \lceil x\rceil - \frac{\lceil nx \rceil}{n}$$

I suspect the minimum value is 0 (that too under certain conditions) but can't prove it is never less than 0.

Edit:

So this is what I worked out. There is no solution when $x \in \mathbb{Z}$ because then $$n \lceil x\rceil = \lceil nx \rceil = nx.$$

When $x \not\in \mathbb{Z}$, then I cannot simplify it more than this:

$$\lceil{x}\rceil = x - \{x\} + 1,$$ where $\{x\}$ is the fractional part of $x$.

So,

$$n \lceil x\rceil - \lceil nx \rceil \geqslant ny \implies nx -n\{x\} + n - nx +\{nx\} - 1 \geqslant ny \implies \frac{\{nx\} - 1}{y + \{x\} - 1} \geqslant n.$$

But this doesn't give me any clue on how to arrive at a value of $n$.

For context, I am trying to work out a new algorithm for scheduling in real time embedded systems and this equation props up as a necessary condition. My math skills are very rusty so any help is appreciated. Any method more efficient than brute force is welcomed.

$\endgroup$
2
$\begingroup$

As you noticed, if $x$ is an integer, $\lceil nx \rceil = n\lceil x \rceil$ for any integer $n$ and therefore $\lceil x\rceil - \frac{\lceil nx\rceil}{n} = 0.$

For $x$ not an integer, let $x' = \lceil x \rceil - x.$ Then $$\lceil nx \rceil = \lceil n\lceil x \rceil - nx' \rceil = n\lceil x \rceil + \lceil -nx' \rceil = n\lceil x \rceil - \lfloor nx' \rfloor,$$ so $$n\lceil x \rceil - \lceil nx \rceil = n\lceil x \rceil - (n\lceil x \rceil - \lfloor nx' \rfloor) = \lfloor nx' \rfloor.$$

Therefore you are looking for the least value of $n$ such that $\lfloor nx' \rfloor \geq ny.$ That is, there is an integer in the interval $[ny, nx']$ (either between $ny$ and $nx'$ or equal to one of them).

That's not a solution yet, but it reduces it to a more familiar problem: on a Cartesian plane with coordinate axes $u$ and $v$ (since we've already used $x$ and $y$ for other things), find the point in the first quadrant of the plane with integer coordinates that is on or between the lines $v = yu$ and $v = x'u$ and on or to the right of the line $u=1,$ such that the $u$-coordinate of the point is minimized. (The line $u=1$ is there merely to exclude the origin itself.) A similar problem is considered in a question on Stack Overflow. The answers to that question suggest the existence of efficient solution methods, though none seems to lay one out in explicit detail (and the problem itself assumes the slopes of the lines—in our case, $x'$ and $y$—are rational). The problem itself can be expressed as a mixed integer lineary programming problem.

The Stack Overflow question was followed up in a question on Math Overflow with some additional answers.

If $n \geq \frac{1}{x' - y},$ then $nx' - ny \geq 1$ and we are guaranteed that $\lfloor nx' \rfloor \geq ny.$ This puts a limit on the number of values of $n$ you might have to try. It also allows you to add a condition to the problem, $u < u_\max,$ which means that the region containing the solutions is bounded.


About the maximum and minimum values of $\lceil x\rceil - \frac{\lceil nx\rceil}{n}$:

Since $nx' \geq \lfloor nx' \rfloor,$ a solution for $n$ exists only if $x' \geq y.$ Also note that $x' = 1 - \{x\} < 1$; therefore $y < 1.$ But you can allow $y$ to be as close to $1$ as you like in $\lceil x\rceil - \frac{\lceil nx\rceil}{n} \geq y$ by making $n$ very large and setting $x = \frac1n,$ so $1$ is the least upper bound of $y.$

Also $x' \geq 0,$ so $\lfloor nx' \rfloor \geq 0$ for $n > 0.$ Since $\frac1n\lfloor nx' \rfloor = \lceil x\rceil - \frac{\lceil nx\rceil}{n},$ it follows that $\lceil x\rceil - \frac{\lceil nx\rceil}{n} \geq 0.$

$\endgroup$

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.