0
$\begingroup$

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 )

$\endgroup$
  • $\begingroup$ "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? $\endgroup$ – username Mar 7 '18 at 11:27
  • $\begingroup$ @username I'm sorry for my poor elaboration. I have elaborated it correctly now. Can you please check it out? $\endgroup$ – user538335 Mar 7 '18 at 17:26
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Perhaps you should see that $f(1)=a+b+c+d=A$ and $f((0,1])=[A,\infty)$? $\endgroup$ – Piquito Mar 7 '18 at 12:29
  • $\begingroup$ 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 $\endgroup$ – user538335 Mar 7 '18 at 17:27
0
$\begingroup$

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...

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

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.