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.
Yes, that is very clearly explained! Thanks! (+1)
Here is the less fancy way.
Let C a , b be the number of n -tuples with values between a and b (inclusively). Then C a , b = ( b − a + 1 ) n .
Let D a , m be the number of n -tuples with maximum value m and no value less than a .
Let E ℓ , m be the number of n -tuples with minimum value ℓ and maximum value m .
We must calculate ∑ ℓ E ℓ , m ⋅ ℓ .
Step 1:
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 .
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 . (Telescoping!)
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!
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.
Log in to reply
@Arjen Vreugdenhil – Based on your original example with n = 2 and m = 7 0 , where the sum was 7 0 2 , I conjectured that in general we have 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!
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 1 0 , I wondered if I could find a natural mapping between the entire 10-cube U and the subset U m . Without knowing the answer, I would probably not have cooked up this neater method.
The summation turns out as,
1 0 + ( 1 1 0 ) k = 1 ∑ 9 k 9 + ( 2 1 0 ) k = 1 ∑ 9 k 8 + . . . . . . + ( 8 1 0 ) k = 1 ∑ 9 k 2 + ( 9 1 0 ) k = 1 ∑ 9 k
Which gives the value 1 0 1 0
Let's prove ∑ max ( x k ) = N min ( x 1 , . . . , x n ) = N n by induction on N . Assume that the formula holds for N . We can allow x k = 0 without altering the sum; if we do so, the sum will involve ( 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 as we raise each component of each list ( x 1 , . . , x n ) by 1. For n = N = 1 0 the answer is 1 0 1 0 = 1 0 0 0 0 0 0 0 0 0 0
Problem Loading...
Note Loading...
Set Loading...
In general, max ( x 1 , … , x n ) = m ∑ min ( x 1 , … , x n ) = m n .
Proof: Let U = { ( x 1 , … , x n ) ∣ 1 ≤ x i ≤ m ) } , and U k = { x ∈ U ∣ max ( x ) = k } . We must calculate ∑ x ∈ U m min ( x ) .
Now let x ∈ U m , and let k = min ( x ) . Define the set S ( x ) ⊂ U as S ( x ) = { ( x 1 − c , x 2 − c , … , x n − c ) ∣ 0 ≤ c ≤ k − 1 } . For instance, if n = 3 and m = 6 , then S ( 6 , 3 , 5 ) = { ( 6 , 3 , 5 ) ; ( 5 , 2 , 4 ) ; ( 4 , 1 , 3 ) } .
It is not difficult to prove that the S ( x ) (with x ∈ U m ) are disjoint and x ∈ U m ⋃ S ( x ) = U . (In other words, these S ( x ) for a partition of U .) Moreover, # S ( x ) = min ( x ) .
Therefore, x ∈ U m ∑ min ( x ) = x ∈ U m ∑ # S ( x ) = # ⎝ ⎛ x ∈ U m ⋃ S ( x ) ⎠ ⎞ = # U = m n .
In this case, m = 1 0 and n = 1 0 so that the answer is 1 0 1 0 = 1 0 0 0 0 0 0 0 0 0 0 .