2
$\begingroup$

Let S be a $\mathbf{multi}$ set of integers such that:

$$S = \left \{\min(\mathbf{C}, a + b - 1) | a \in \left [ \mathbf{A} \right ], b \in \left [ \mathbf{B} \right ] \right \}$$

  • Note that $\mathbf{A}$, $\mathbf{B}$ and $\mathbf{C}$ are positive integers and we know $\mathbf{A} \leq \mathbf{B} \leq \mathbf{C}$

  • Also $\left [ x \right ]$ stands for $\left \{ 1, 2, 3, \cdots , x \right \}$

Can you figure out sum of all S elements using $\mathbf{A}$, $\mathbf{B}$ and $\mathbf{C}$ as parameters?

$\endgroup$
1
$\begingroup$

If $C \ge A+B-1$, then the min against $C$ will have no effect and the sum just reduces to $$\sum_{a=1}^A \sum_{b=1}^B (a + b - 1) = BA(A+1)/2 + AB(B+1)/2 - AB = AB(A+B)/2.$$

Let’s assume now that $A \le B \le C < A+B-1$. Then some of the values $a+b-1$ get replaced by the smaller $C$, so we just need to add up the deficits and subtract this from the previous total $AB(A+B)/2$.

It’s not hard to see that there is one value with maximum deficit $A+B-C-1$, two values with the next highest deficit $A+B-C-2$, etc., down to the minimum possible deficit of $1$ which occurs $A+B-C-1$ times (note that the assumption $A,B\le C$ is essential here, otherwise our count would be too high). The total deficit is thus simply $f(A+B-C)$, where

$$f(n) =\sum_{k=1}^n k(n-k) = (n^3-n)/6.$$

So the sum of the multi set $S$ is:

$$\tfrac12 AB(A+B) - \tfrac16 ((A+B-C)^3 - (A+B-C)),$$

unless $A+B-C < 0$, in which case you can discard the second term.

$\endgroup$
2
  • $\begingroup$ Thanks! By the way, can you explain a bit more why the $A,B\le C$ assumption is essential? $\endgroup$ – CompuPhysics Mar 5 '20 at 5:33
  • $\begingroup$ @CompuPhysics If you count the multiplicities of each value of $r=a+b-1$ you’ll find (assuming $A\le B$) there are $r$ copies of the value $r$ when $r \in [1,A]$; $A$ copies when $r \in [A,B]$; and $A+B-r$ copies when $r\in [B,A+B-1]$. The assumption $B\le C$ ensures that $C$ lies in the third interval and not in the first two intervals, which would affect the way we count. $\endgroup$ – Erick Wong Mar 5 '20 at 5:39

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.