/sci/ - Science & Math

[Anonymous No.8995697]

Hey guys, I found this formula used in a proof of some number theory book:
[eqn]max(a, b, c)=a+b+c+min(a, b, c)-min(a,b)-min(a,c)-min(b,c)[/eqn]

It is used without proof, assumed to be trivial.

How do I prove this? Is there a similar formula for general case calculating the maximum through minimums?

[Anonymous No.8995705]

>>8995697
Okay, I managed to prove this.
Assume, without loss of generality that [math]a \le b \le c[/math]:
[eqn]max(a,b,c)=c[/eqn][eqn]a+b+c+min(a,b,c)-min(a,b)-min(a,c)-min(b,c)=a+b+c+a-a-a-b=c[/eqn]
Thus the formula is valid for any a, b, c, since we can just reorder them to get [math]a \le b \le c[/math].


But how do we get to that formula? How to get the general case for [math]a_1, a_2, ..., a_n[/math]?

[Anonymous No.8995709]

>>8995697
Assume a > b > c

min(a, b, c) = c
min(a, b) = b
min( a, c) = c
min(b, c) = c
a+ b + c + min(a, b, c) = a + b + 2c
-1 * (min(a, b) + min(a, c) + min(b, c) ) =
-1 * ( b + c + c) = - b - 2c

Plugging it back in:
a + b + 2c - b - 2c = a, which we said was the max.

[Anonymous No.8995710]

>>8995709
Thanks. Do you have any idea how did we arrive to such a formula, or how can we construct a formula for an arbitrary number of elements?

[Anonymous No.8995720]

>>8995697
Whichever min(a,b,c) turns out to be, it appears exactly twice out of min(a,b), min(a,c) and min(b,c).
The remaining one is going to be the second smallest element.
So when you begin with a+b+c, then add the minimum once and subtract it twice, and finally subtract the next smallest element, you're left with the largest element.
Thus RHS = LHS.

[Anonymous No.8995764]

>>8995710
Just check what all the combinations give you. In your example it works because minimum of each possible pair gives you 2x the smallest element, and once the middle one.
In fact, you can generalize it quite easily. If you have m elements a1 < a2 < ... < am, then the sum of the minimum of all possible pairs is (m-1)a1 + (m-2)a2 + .. + (am-1). Then you can just compensate for that, though it feels pretty trivial and useless to write it like that.

[Anonymous No.8995821]

I'm on my phone so I can't write a detailed reply but you can generalize the formula if you recognize one fact: if c > a, b then min(a, b, c) = min(a, b) (you know that the minimum can't be c so you can ignore it altogether).

Use this simplification in your formula and both the proof and the generalizations become apparent.

[Anonymous No.8995957]

>>8995821
I can't figure out how to get a generalization out of this. Can anyone help a fellow brainlet out?

[Anonymous No.8996500]

>>8995957
Let S be a set of n numbers and let P be its power set.

max(S) = Sum over minima of all singletons in P - Sum over minima of all pairs in P + Sum over minima of all triples in P + ... + (-1)^(n-1) minimum of the single n-tuple in P

Here's the idea behind the proof for n = 3.

According to our formula,

max(a, b, c) = min(a) + min(b) + min(c) - (min(a, b) + min(b, c) + min(a, c)) + min(a, b, c)

Now suppose we know beforehand that the maximum is c, then we can rewrite the sum as follows

max = (min(a) - min(a, c)) + (min(b) - min(b, c)) + min(c) + (- min(a, b) + min(a, b, c))

(Notice how the sum is rearranged. You should prove that such a rearrangement is possible even for a set with n elements)

If x is any element or pair of elements (or any k-tuple in the general case), min(x, c) = min(x) because c cannot be the minimum. So all the terms within the brackets of the above rearrangement go to 0 and

max = 0 + 0 + min(c) + 0 = c

as expected.

With the same principle you can express max(S) as a sum over minima of subsets of different power sets. For example, the power set of the set of all sums of pairs of S, etc.

[Anonymous No.8996716]

>>8996500
Goddamn I need to study more

thanks anon, I got the idea

(i think)