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.
