0
$\begingroup$

Maybe I just have a mental block and this is really easy, but I'm having a hard time figuring out the following problem:

Given an integer value $p$ and a scaling factor $f \in \mathbb{Q}$, i.e. $f = \frac{n}{d}$, where $n$ and $d$ are integers, I need to find some integer value $x$ such that the following holds:

  • $ \lfloor xf \rfloor = \lfloor x\frac{n}{d}\rfloor \leq p$
  • $ \lfloor (x+1)f \rfloor = \lfloor (x+1)\frac{n}{d}\rfloor > p$

where $\lfloor \cdot \rfloor$ means rounding down to the nearest integer.

Obviously, one can simply calculate $ x \approx \lfloor p /f \rfloor = \lfloor p \frac{d}{n} \rfloor $ and then keep increasing or decreasing $x$ until both conditions are satisfied, but I'd prefer a singe-shot solution.

Thinking about it more, I came up with the following guess at a solution, but I'm having a hard time convincing myself that it is generally correct:

$$ x = \lceil (p+1)/f \rceil - 1 = \lceil (p+1)\frac{d}{n} \rceil - 1$$

where $\lceil \cdot \rceil$ means rounding up to the nearest integer.

Are there general rules or tricks on how to manipulate equations that contain rounding?

$\endgroup$
1
$\begingroup$

$$xn<pd+d........(1)$$ and $$(x+1)n\geq pd+d.......(2)$$ Hence, $$\frac{d(p+1)}{n}-1\leq x< \frac{d(p+1)}{n}$$

$x$ is the integer between these two limits. The fact that there is indeed an integer between these two limits stems from the fact that there is an integer within an interva of $1$ between any two real numbers.

$\endgroup$
2
  • $\begingroup$ That's a good way to think about it, and I think the solution I guessed now follows easily from the left half of your last inequalities. Thanks! $\endgroup$ – Markus A. Jul 1 '13 at 7:40
  • $\begingroup$ The r.h.s of the last display is too loose, and the 2 given constraints don't always have a solution. For example, take $n=2, d=10, p=1$. Then taking $x=5$ verifies the first constraint but not the second, whereas $x=6$ verifies the second but not the first. $\endgroup$ – Metaxal Apr 16 '18 at 15:38
1
$\begingroup$

Let’s see what happens if we set

$$x=\left\lceil\frac{(p+1)d}n\right\rceil-1\;,$$

so that

$$x<\frac{(p+1)d}n\le x+1\;,$$

and therefore $xf<p+1\le(x+1)f$. This certainly ensures that $\lfloor(x+1)f\rfloor\ge p+1>p$. Moreover, it ensures that $\lfloor xf\rfloor\le p$. Thus, it works exactly as you hoped.

$\endgroup$
2
  • $\begingroup$ Took me a quick second to follow the "certainly ensures" part ;), but I think this makes sense! Thank you! I think I'll select Ayush's answer, though, since it's more of a derivation and helps me to think about how to systematically arrive at a solution in the future rather than "just" being able to verify a guess as correct. But definitely +1! $\endgroup$ – Markus A. Jul 1 '13 at 7:36
  • $\begingroup$ @Markus: You’re welcome. $\endgroup$ – Brian M. Scott Jul 1 '13 at 7:41

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.