an be the elements of A

Download (0)

Loading.... (view fulltext now)

Full text

(1)

Problem 11520

(American Mathematical Monthly, Vol.117, August-September 2010) Proposed by P. Ash (USA).

Let n and k be integers with1 ≤ k ≤ n, and let A be a set of n real numbers. For i with 1 ≤ i ≤ n, let Si be the set of all subsets of A with i elements, and let σi =P

s∈Simax(s). Express the kth smallest element of A as a linear combination of σ1, . . . , σn.

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

Let a1 ≤ a2 ≤ · · · ≤ an be the elements of A. Then ai = max(s) iff s = {ai} ∪ s where s ⊂ {a1, . . . , ai−1}. Therefore

σk= X

s∈Sk

max(s) =

n

X

i=1

 i − 1 k− 1

 ai. We claim that

ak=

n

X

i=1

(−1)i+k i − 1 k− 1

 σi. This can be verified directly as follows:

n

X

k=1

 i − 1 k− 1



· (−1)k+jk − 1 j− 1



=

n

X

k=1

(−1)k+j (i − 1)!

(k − 1)!(i − k)!· (k − 1)!

(j − 1)!(k − j)!· (i − j)!

(i − j)!

= i − 1 j− 1

 n X

k=1

(−1)k−j i − j k− j



[j ≤ k ≤ i]

= [j ≤ i] i − 1 j− 1

 i−j X

m=0

(−1)mi − j m



= [i = j]

where [Q] is 1 if Q is true and it is 0 otherwise. 

Figure

Updating...

References

Related subjects :