Weird Minimax

Algebra Level 5

Find ∑ max ⁡ ( x 1 , . . , x 10 ) = 10 min ⁡ ( x 1 , … , x 10 ) \large\sum_{\max(x_1,..,x_{10})=10}\min(x_1,\ldots,x_{10})

where x 1 , … , x 10 x_1,\ldots,x_{10} are positive integers.

Inspiration here and here .


The answer is 10000000000.

Otto Bretscher by Otto Bretscher , 65, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Arjen Vreugdenhil
Mar 30, 2016

In general, ∑ max ( x 1 , … , x n ) = m min ( x 1 , … , x n ) = m n . \sum_{\text{max}(x_1,\dots,x_n) = m} \text{min}(x_1,\dots,x_n) = m^n.

Proof: Let U = { ( x 1 , … , x n ) ∣ 1 ≤ x i ≤ m ) } U = \{(x_1, \dots, x_n) | 1 \leq x_i \leq m)\} , and U k = { x ⃗ ∈ U ∣ max ( x ⃗ ) = k } U_k = \{\vec x \in U | \text{max}(\vec x) = k\} . We must calculate ∑ x ⃗ ∈ U m min ( x ⃗ ) . \sum_{\vec x \in U_m} \text{min}(\vec x).

Now let x ⃗ ∈ U m \vec x \in U_m , and let k = min ( x ⃗ ) k = \text{min}(\vec x) . Define the set S ( x ⃗ ) ⊂ U S(\vec x) \subset U as S ( x ⃗ ) = { ( x 1 − c , x 2 − c , … , x n − c ) ∣ 0 ≤ c ≤ k − 1 } . S(\vec x) = \{ (x_1 - c, x_2 - c, \dots, x_n - c) | 0 \leq c \leq k-1\}. For instance, if n = 3 n = 3 and m = 6 m = 6 , then S ( 6 , 3 , 5 ) = { ( 6 , 3 , 5 ) ; ( 5 , 2 , 4 ) ; ( 4 , 1 , 3 ) } . S(6,3,5) = \{ (6,3,5);\ (5,2,4);\ (4,1,3) \}.

It is not difficult to prove that the S ( x ⃗ ) S(\vec x) (with x ⃗ ∈ U m \vec x \in U_m ) are disjoint and ⋃ x ⃗ ∈ U m S ( x ⃗ ) = U . \bigcup_{\vec x\in U_m} S(\vec x) = U. (In other words, these S ( x ⃗ ) S(\vec x) for a partition of U U .) Moreover, # S ( x ⃗ ) = min ( x ⃗ ) . \#S(\vec x) = \text{min}(\vec x).

Therefore, ∑ x ⃗ ∈ U m min ( x ⃗ ) = ∑ x ⃗ ∈ U m # S ( x ⃗ ) = # ( ⋃ x ⃗ ∈ U m S ( x ⃗ ) ) = # U = m n . \sum_{\vec x \in U_m} \text{min}(\vec x) = \sum_{\vec x \in U_m} \#S(\vec x) \\ = \#\left(\bigcup_{\vec x\in U_m} S(\vec x)\right) = \# U = m^n.

In this case, m = 10 m = 10 and n = 10 n = 10 so that the answer is 1 0 10 = 10 000 000 000 10^{10} = \boxed{10\:000\:000\:000} .

7 Helpful 0 Interesting 0 Brilliant 0 Confused

Yes, that is very clearly explained! Thanks! (+1)

Otto Bretscher - 5 years, 2 months ago

Here is the less fancy way.

Let C a , b C_{a,b} be the number of n n -tuples with values between a a and b b (inclusively). Then C a , b = ( b − a + 1 ) n C_{a,b} = (b-a+1)^n .

Let D a , m D_{a,m} be the number of n n -tuples with maximum value m m and no value less than a a .

Let E ℓ , m E_{\ell,m} be the number of n n -tuples with minimum value ℓ \ell and maximum value m m .

We must calculate ∑ ℓ E ℓ , m ⋅ ℓ \sum_\ell E_{\ell,m}\cdot \ell .

Step 1:

D a , m = C a , m − C a , m − 1 = ( m − a + 1 ) n − ( m − a ) n . D_{a,m} = C_{a,m} - C_{a,m-1} = (m-a+1)^n - (m-a)^n.

Step 2:

E ℓ , m = D ℓ , m − D ℓ + 1 , m . E_{\ell,m} = D_{\ell,m} - D_{\ell+1,m}.

Step 3: ∑ ℓ = 1 m E ℓ , m ⋅ ℓ = ∑ a = 1 m D a , m ⋅ ( a − ( a − 1 ) ) = ∑ a = 1 m D a , m = ∑ a = 1 m ( ( m − a + 1 ) n − ( m − a ) n ) = m n . \sum_{\ell = 1}^m E_{\ell,m}\cdot \ell = \sum_{a = 1}^m D_{a,m}\cdot (a - (a-1)) \\ = \sum_{a = 1}^m D_{a,m} \\ = \sum_{a = 1}^m \left((m-a+1)^n - (m-a)^n\right) \\ = m^n. (Telescoping!)

Arjen Vreugdenhil - 5 years, 2 months ago

Log in to reply

Your first method is really not that fancy; I like it a lot. You are basically just introducing an equivalence relation where the size of each equivalence class is the minimum you want... very neat!

Otto Bretscher - 5 years, 2 months ago

Log in to reply

That's exactly the point-- I am just afraid that many will not catch on to this trick because of all the notation. Therefore I called it "fancy". You are clearly an experienced mathematician who looks straight at the heart of a solution; but that is a skill even many here on Brilliant have not (yet) acquired.

Arjen Vreugdenhil - 5 years, 2 months ago

Log in to reply

@Arjen Vreugdenhil – Based on your original example with n = 2 n=2 and m = 70 m=70 , where the sum was 7 0 2 70^2 , I conjectured that in general we have m n m^n , and I proceeded to prove that result by induction. I have added my solution for the sake of variety. This turned out to be an interesting topic; I want to thank you for bringing it up!

Otto Bretscher - 5 years, 2 months ago

I will also be honest and tell you that I first solved the problem in the second way, through systematic counting. When I found the answer to be 1 0 10 10^{10} , I wondered if I could find a natural mapping between the entire 10-cube U U and the subset U m U_m . Without knowing the answer, I would probably not have cooked up this neater method.

Arjen Vreugdenhil - 5 years, 2 months ago
Saarthak Marathe
Apr 20, 2016

The summation turns out as,

10 + ( 10 1 ) ∑ k = 1 9 k 9 + ( 10 2 ) ∑ k = 1 9 k 8 + . . . . . . + ( 10 8 ) ∑ k = 1 9 k 2 + ( 10 9 ) ∑ k = 1 9 k \displaystyle 10+\dbinom{10}{1}\sum_{k=1}^{9} k^9+\dbinom{10}{2}\sum_{k=1}^{9} k^8+...... +\dbinom{10}{8}\sum_{k=1}^{9} k^2 + \dbinom{10}{9}\sum_{k=1}^{9} k

Which gives the value 10 10 \boxed { {10}^{10} }

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Otto Bretscher
Mar 30, 2016

Let's prove ∑ max ⁡ ( x k ) = N min ⁡ ( x 1 , . . . , x n ) = N n \sum_{\max(x_k)=N}\min(x_1,...,x_n)=N^n by induction on N N . Assume that the formula holds for N N . We can allow x k = 0 x_k=0 without altering the sum; if we do so, the sum will involve ( N + 1 ) n − N n (N+1)^n-N^n summands. Now ∑ max ⁡ ( x k ) = N + 1 min ⁡ ( x 1 , . . . , x n ) = N n + ( ( N + 1 ) n − N n ) = ( N + 1 ) n \sum_{\max(x_k)=N+1}\min(x_1,...,x_n)=N^n+\left((N+1)^n-N^n\right)=(N+1)^n as we raise each component of each list ( x 1 , . . , x n ) (x_1,..,x_n) by 1. For n = N = 10 n=N=10 the answer is 1 0 10 = 10000000000 10^{10}=\boxed{10000000000}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...