II gara a squadre UNIMI- Quesito 1

[Boll]

As usual, posto i problemi della gara a squadre UNIMI...

Sia $ n $ un intero maggiore di 0. Sia $ A $ un sottoinsieme di $ n $ elementi dell'insieme $ \{1,2,3,\dots, 2n-1\} $. E' sempre possibile scegliere alcuni elementi (a due a due distinti) di $ A $ in modo che la loro somma sia divisibile per $ 2n $ ?

[enomis_costa88]

Posso non scegliere nessun elemento cosicchè la somma degli elementi scelti sia 0?
poi avrei $ 0 \equiv 0 $ (mod 2n)

Se (come mi pare d'avere capito) devo prendere almeno un'elemento:

sia n=1
A è un sottinsieme di un'elemento dell'insieme {1}.
Quindi A è {1}.
Devo scegliere almeno un'elemento, ma posso sceglierne solo uno...
Quindi la somma degli elementi scelti è 1.
ma $ 1 \not \equiv 0 $ (mod 2)
quindi per n=1 non è possibile scegliere alcuni elementi di A in modo che la loro somma sia divisibile per 2n=2.

[HiTLeuLeR]

Posso non scegliere nessun elemento cosicchè la somma degli elementi scelti sia 0?
poi avrei $ 0 \equiv 0 $ (mod 2n)

Penso davvero ci sia ben poco da ridere, e molto di cui provar vergogna, casomai... Sia come sia, assumiamo di ragionare di somme non vuote:

----------------

Siano $ A := \{a_1, a_2, \ldots, a_n\} $ ed $ A^* $ l'insieme ottenuto da $ A $ sostituendo ad ogni $ a_i $ il corrispondente residuo $ \bar{a}_i $ minimo assoluto $ \bmod\;\! 2n $. Supposto $ n \ge 2 $, osserviamo che i) $ \overline{1, n-1} \oplus \overline{1-n, -1} = \overline{0, 2n-1} $, in $ (\mathbb{Z}/2n\mathbb{Z}, +) $; ii) ad ogni $ x \in \overline{1, n-1} $ resta associato un unico elemento $ y\in\overline{1-n, -1} $, e viceversa, tale che $ x + y = 0 $. Se dunque $ n\not\in A $, per il principio dei cassetti, esistono $ i, j = 1, 2, \ldots, n $, con $ i < j $, tali che $ \bar{a}_i + \bar{a}_j = 0 $, e non c'è altro da aggiungere.

Se invece $ n\in A $, supposto $ n \ge 4 $, ammettiamo wlog $ a_n = n $ ed $ a_1 < a_2 < \ldots < a_{n-1} $. Considerando quindi che esiste al più un unico $ i = 2, 3, \ldots, n-1 $ tale che $ a_i \equiv a_1 \bmod n $, poniamo $ s_0 := a_1 $, $ s_1 := a_2 $ ed $ s_k := a_1 + a_2 + \ldots + a_k $ ($ k = 2, 3, \ldots, n-1 $), se $ a_2 \not\equiv a_1 \bmod n $; $ s_0 := a_1 $, $ s_1 := a_3 $, $ s_2 := a_1 + a_3 $ ed $ s_k := a_1 + a_2 + \ldots + a_k $ ($ k = 3, \ldots, n-1 $), se $ a_2 \equiv a_1 \bmod n $. Ancora in base al pigeon-hole, esistono $ i, j = 0, 1, \ldots, n-1 $, con $ i < j $, tali che $ s_i \equiv s_j \bmod n $. E allora $ 2n $ divide $ s_j - s_i = a_{i+1} + a_{i+2} + \ldots + a_j $ oppure $ s_j - s_i + a_n $. Se ne conclude, previa verifica "manuale" dei casi $ n = 2 $ ed $ n = 3 $, che la risposta al quesito è affermativa sse $ n = 1 $ vel $ n \ge 4 $. FINE.