0
$\begingroup$

$a+b=x$

$b+c=y$

$a

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

  • 0
    They are integers2012-10-12

1 Answers 1

1

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.

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, there is no solution.

  • 0
    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)2012-10-12