AIME 1983

[Vinci]

Per $\left\{ 1,2,3,\ldots ,n\right\}$ e tutti i suoi sottoinsiemi non vuoti, una "somma alternata" è definita come segue. Messi i numeri in ordine decrescente ed iniziando dal più grande, aggiungere e sottrarre i numeri successivi alternati. Per esempio la somma alternata di $\left\{ 1,2,4,6,9\right\}$ è $9-6+4-2+1=6$ e per $\left\{ 5\right\}$ è semplicemente $5$.
Trovare la somma di tutte le somme alternate per $n=7$.

[Talete]

Testo nascosto:

Dimostriamo che per ogni $n$ la soluzione è $n\cdot 2^{n-1}$. Non serve neanche l'induzione...

Definizioni. Dato $\{1,\ldots,n\}$ chiamiamo $U_n$ l'insieme dei suoi sottoinsiemi non-vuoti; e dato $U_n$ chiamiamo $\sigma_n$ la somma delle somme a segni alterni dei sottoinsiemi contenuti in $U_n$.

Ora, consideriamo $U_n$. Avrà $2^{n}-1$ elementi. Di questi,
(a) uno sarà il sottoinsieme $\{n\}$,
(b) $2^{n-1}-1$ saranno della forma $Q\in U_{n-1}$,
(c) i rimanenti $2^{n-1}-1$ saranno della forma $Q\cap\{n\}$, con $Q\in U_{n-1}$.

$\sigma_n$ sarà dunque la somma delle somme delle somme a segni alterni dei tre sottoinsiemi composti dagli elementi di tipo (a), (b) e (c).

(a) contiene un solo elemento, che ha come somma a segni alterni $n$.

(b) contiene $2^{n-1}-1$ elementi, che hanno come somma delle somme a segni alterni $\sigma_{n-1}$.

(c) contiene $2^{n-1}-1$ elementi, ciascuno avente somma a segni alterni $n-x$, dove $x$ è una somma a segni alterni di un elemento di (b). In altre parole, la somma delle somme a segni alterni di (c) è $(2^{n-1}-1)\cdot n-\sigma_{n-1}$.

Il totale è facilmente calcolabile:
\[\sigma_n=n+\sigma_{n-1}+(2^{n-1}-1)\cdot n-\sigma_{n-1}=n\cdot 2^{n-1}.\]

Certo che, tra somme a segni alterni, somme delle somme a segni alterni e soprattutto la famigerata somma delle somme delle somme a segni alterni io mi sono un po' confuso... (che si traduce come "in gara sarei impazzito")

EDIT: ah sì vabbè per $n=7$ il risultato è $\boxed{448}$

[Vinci]

Giusta