somme e sottoinsiemi

[ma_go]

beh, non credevo che avrei mai postato un problema di combinatoria...
comunque non è nulla di che

sia dato $ I_n = \{1,2,\cdots n\} $, e sia, per ogni $ i $, $ 1 \le a_i \le i $ un intero. per ogni $ C \subset I_n $ definiamo $ S(C) = \sum_{i \in C} a_i $.
dimostrare che esistono due insiemi disgiunti $ A, B $ tali che l'unione dia $ I_n $ e tali che $ S(A) = S(B) $ se e solo se $ S_(I_n) $ è pari.

[HumanTorch]

Se ho ben capito basterebbe prendere in ogni insieme $ k $ e $ S-k $
dove $ S $ è pari a $ \frac{n(n+1)}{2} $.
Tuttavia chiedo chiarimenti: $ a_i $ è un elemento di $ I_n $?

[enomis_costa88]

Scusatemi per il non utilizzo di la tex..ma non sono ancora riuscito ad impararlo..riparerò il prima possibile, promesso.

Se S(In) è dispari: S(In)/2=S(A)=S(B) è assurdo perché S(A),S(B) sono interi perché somma di interi mentre S(In)/2 no.
TH2: posso ottenere qualsiasi b come somma di a_i con i<b+1
1) 1=a_1
2)hp: ottengo m ( e i numeri <m..)
th: ottengo m+1: 0<a_m+1<m+2
K=m+1-a_m+1 quindi -1<K<m+1
Per l’hp induttiva posso ottenere K come somma di a_i. quindi posso ottenere m+1 e tutti gli 0<m<n+1.
Strategia per creare i due insiemi:
Scelgo i primi K’ a_i (in ordine crescente) in modo da creare un insieme C tale che
S(C) = < S(In)/2 ma S(D)+a_k’+1>S(In)/2.
Chiamo D l’insieme dei primi k'+1 a_i.
E ottengo: S(In)/2 +a_k'+1>=S(D)>S(In)/2;
chiamo c = S(D)-S(In)/2 e ottengo c<a_k'+1
ora devo togliere a D un insieme E con S(E)=c e per quanto dimostrato induttivamente posso farlo.
A=D-E e In-A=B con S(A)=S(In)/2=S(B). da cui la tesi QED

Secondo me questo è un problema carino.. peccato che se ne postino così pochi di belli (ok dipende da cosa intendo per bello..) in combinatoria!
Buon Pomeriggio a tutti Simone