# Solving multiple ceil functions

Hello,
I am working on an computer program and I am required to find the least possible value of $x$ for

$\lceil \dfrac a x \rceil + \lceil \dfrac b x \rceil + \lceil \dfrac c x \rceil + \lceil \dfrac d x \rceil = H$

where $x,a,b,c,d,H$ are all integers and the values of $a,b,c,d$ and $H$ are given.
I am supposed to find the least possible integral value for $x$ such that the value of $H$ that will be formed (after substituting the values) should be lesser than or equal to the value of $H$ in the question but not greater than $H$.
What I mean by this is that we need to find a minimum possible integral value for $x$ such that after plugging in the values of $a, b...$ the value of $H$ that we get is maximum possible and not greater than the proposed value of $H$ (See the examples for further understanding).

I saw this question on FLOOR function but it was about multiplication and following the method they used to solve it, I got,

$\lceil \dfrac a {n - \alpha} \rceil + \lceil \dfrac b {n - \alpha} \rceil + \lceil \dfrac c {n - \alpha} \rceil + \lceil \dfrac d {n - \alpha} \rceil = H$

where $n$ is the ceil of $x$ and $\alpha$ is the difference of $n$ and $x$. But this method has left me even more clueless on how to go about, since I'm pretty new to ceil and floor functions.

****** EXAMPLES ******

If the values are

$A = 3, B = 5, C = 6, D = 8, H = 6$

then the equation formed will be

$\lceil \dfrac 3 x \rceil + \lceil \dfrac 5 x \rceil + \lceil \dfrac 6 x \rceil + \lceil \dfrac 8 x \rceil = 6$

for which the correct value for $x$ will be $5$ which is the lowest possible value since, if it is $6$ then the value of $H$ will be $5$ and if the value is $4$, then the value of $H$ will be $7$ which wont comply to the requirements of the value of $H$ and $x$.

But, If the values are

$A = 3, B = 5, C = 6, D = 9, H = 7$

then the equation formed will be

$\lceil \dfrac 3 x \rceil + \lceil \dfrac 5 x \rceil + \lceil \dfrac 6 x \rceil + \lceil \dfrac 9 x \rceil = 7$

for which the correct integral value for $X$ will be $5$ since if $X = 4$ it would made $H = 8$ (Greater than the given value of $7$) and if $X = 6$ then it would make $H = 5$ (which would be smaller than the value for $x = 5$).

What I thought is that for questions like the second example once we get an fractional value for $x$ (after mathematically solving it) we can floor[ $\lfloor x \rfloor$ ] it.

ANY HELP IS GREATLY APPRECIATED!!! (And if it's not possible to reduce it to an easier equation, a algorithm to computer-solve it is also OK :P )

• "the values of A,B,C,D and H are given such that H gets the greatest possible value" : would you care to elaborate? From your examples, you do not mean given $A,B,C,D$ you set $H$ so that the problem has a solution and is as large as possible. Thus, what do you mean? – username Mar 7 '18 at 11:27
• @username I'm sorry for my poor elaboration. I have elaborated it correctly now. Can you please check it out? – user538335 Mar 7 '18 at 17:26

COMMENT.-Let $f(x)=\lceil a/ x \rceil + \lceil b/ x \rceil + \lceil c/ x \rceil + \lceil d/ x \rceil$ with $a,b,c,d\gt0$ . We have $$f(x)\to \infty\text{ when } x\to 0\\f(x)\to 4\text{ when } x\to \infty$$ Can you explain to me better what you want to calculate? I do not understand well. Thank you.

• Perhaps you should see that $f(1)=a+b+c+d=A$ and $f((0,1])=[A,\infty)$? – Piquito Mar 7 '18 at 12:29
• I'm sorry for my poor elaboration. I have elaborated it correctly now with more detailed examples. Can you please check it out? Thank you – user538335 Mar 7 '18 at 17:27

So the question is $$\text{maximize} \left(\left[\frac a x\right]+\left[\frac b x\right]+\left[\frac c x\right]+\left[\frac d x\right]\right)$$ under the contraint that $$\left[\frac a x\right]+\left[\frac b x\right]+\left[\frac c x\right]+\left[\frac d x\right] \leq H$$ The map $$x\to \left[\frac a x\right]+\left[\frac b x\right]+\left[\frac c x\right]+\left[\frac d x\right]$$ is decreasing with $x$, and its smallest non trivial value is obtained for $$x_M=\max(a,b,c,d)$$ where it is equal to the multiplicity of that maximum (1,2,3, or 4) The largest value is obtained for $x_m=1$ where it is equal to $a+b+c+d$.

So a simple algorithm is a dichotomy: try [(x_m+x_M)/2] if the result is greater than H, then set x_m = [(x_m+x_M)/2] if it is smaller than H, then set x_M=[(x_m+x_M)/2] and iterate. Stop when they are only 1 apart...

• I'm sorry, but I didn't understand from the part of xm = Max(a,b,c,d) – user538335 Mar 8 '18 at 2:00
• And can you please tell me what's the value of xM – user538335 Mar 8 '18 at 2:01
• @user538335 If $x>a$ then $\left[\frac{a}{x}\right]=0$, as $[y]=0$ if $y<1$... – username Mar 9 '18 at 19:47
• Can you please modify your answer by including this explanation and giving some examples of the application of the algorithm? – user538335 Mar 10 '18 at 4:12