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+j}k − 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)^{m}i − j
m

= [i = j]

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