Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$a+b=x$

$b+c=y$

$a<b<c$

$x$ is given, $y$ is given

$a$, $b$, and $c$ have bounds (amin, amax, bmin, bmax, cmin, cmax, etc) which are given.

How many ways are there to write $a-c$ (which is the same as $x-y$) such that all constraints are fulfilled?

All variables are integers.

share|improve this question
    
If $a, b, c$ are real numbers, I suspect the answer is 0, 1 or a truckload, depending on their bounds. If they are integers, then this is a harder question. –  Arthur Oct 12 '12 at 20:56
    
They are integers –  MyNameIsKhan Oct 12 '12 at 21:00

1 Answer 1

up vote 1 down vote accepted

There is only one possible value for $a-c$, as you note it equals $x-y$. To count the number of solutions for $(a,b,c)$, consider the following: $a$ and $c$ are determined once we know $b$. The value of $b$ must fulfill:

  • $b_\min\le b\le b_\max$ by the bounds on $b$
  • $x-a_\max\le b\le x-a_\min$ by the bounds on $a$
  • $y-c_\max\le b\le y-c_\min$ by the bounds on $c$
  • $\lfloor \frac x2\rfloor +1\le b\le \lceil\frac y2\rceil -1$ to ensure $a<b<c$.

Thus we have all in all just one constrainst $m\le b\le n$ with $m=\max\{b_\min,x-a_\max,y-c_\max,\lfloor \frac x2\rfloor +1 \}$ and $n=\min\{b_\max,x-a_\min,y-c_\min,\lceil\frac y2\rceil -1 \}$. If $n\ge m$, there are $n-m+1$ possible values for $b$, leading to the same number of solutions $(a,b,c)$. If $n<m$, there is no solution.

share|improve this answer
    
This is strangely the exact same answer I got myself but for some reason it isn't working for all cases. I will see where I made my mistake in my testing. Thank you. –  MyNameIsKhan Oct 12 '12 at 21:27
    
For what case does it not work? –  Hagen von Eitzen Oct 12 '12 at 21:28
    
Are you sure the conditions for m and n are accurate? I am testing with a large set of values. This heuristic works for small values but not large, which makes me think there is another edge condition missing somewhere (no overflow errors) –  MyNameIsKhan Oct 12 '12 at 22:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.