We are given ordered sets of positive integers A and B with n elements each and an integer C, how can we find the number of integer roots of the following equation:
$\sum_{i=1}^n floor(\frac{A_i*x}{B_i}) = C $
I have been stuck on this problem for such a long time. I have tried solving using all the properties of floor functions I know till now, it just doesn't fit into any.
An example will be when A = (1,5) and B = (2,4) and C = 3, the number of roots is 1, the root is 5. Any help will be very helpful to me, thanks.

  • $\begingroup$ Welcome to Math.SE Kindly share your thoughts on the question you put up so as to maximize the number of possible contributors. $\endgroup$ – The Dead Legend Apr 28 '17 at 8:39
  • 1
    $\begingroup$ Done :) Thanks for trying to help me out. I am new here. $\endgroup$ – Shreya Halder Apr 28 '17 at 9:11

If $x=x_0$ is a solution then so is any x in a small enough interval to the right or the left of $x_0$, so an equation of this form will not have discrete roots - its solution set will consist of one or more intervals (unless it is empty).

If all the rationals $A_i/B_i$ are positive then the sum of the floor functions is a sum of monotonically increasing functions so it is itself a monotonically increasing function of x. Its solution set is therefore either empty or it consists of a single interval. An example with an empty solution set is A=(1,1), B=(1,1), C=1 i.e. $$2 floor(x) = 1$$

Similar argument holds if all $A_i/B_i$ are negative.

If $A_i/B_i$ are both positive and negative then the solution set can consist of an infinite number of intervals. For example, consider A=(-1,-1,2), B=(1,1,1), C=0 i.e.

$$2floor(-x) +floor(2x)=0$$

  • $\begingroup$ Modified the question, I needed number of integer roots and All A_i and B_i are positive, thank you for your answer :) $\endgroup$ – Shreya Halder Apr 28 '17 at 9:45

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.