What's the sum of elements of this multi-set?

46 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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.