Pentru a vă înregistra, vă rugăm să trimiteți un email către administratorul site-ului.
Pune o întrebare

3.6k intrebari

6.8k raspunsuri

15.5k comentarii

2.5k utilizatori

1 plus 0 minusuri
896 vizualizari

Fie multimea M= {1,2,3,......,2017} sa se arate ca oricare ar fi o submultime X  de 15 elemente din M ,exista 2 submultimi disjuncte A si B (edit A,B incluse in X)astfel incat suma elementelor lui A si B sa fie egale ,adica:

\sum_{i\in A} i=\sum_{j\in B}j

.Dati exemplu de o multime cu 11 elemente din M, pentru care nu exista submultimile A si B disjuncte cu suma elementelor egale.

Experimentat (2.3k puncte) in categoria Matematica
0 0
Chiar am vrut să întreb detaliul pe care l-ai completat.
Frumoasă problema, o să o analizez o idee.

1 Raspuns

3 plusuri 0 minusuri
 
Cel mai bun raspuns

Daca am inteles bine formularea problemei,raspunsul ar putea fi:

X are 2^{^{15}}-1= 32767 submultimi nevide, acestea putand avea suma elementelor cuprinsa intre 1 si ( 2003+2004+...2017)=30150. Cum 32767>30150, conform principiului cutiei lui Dirichlet, exista 2 submultimi ale lui X care sa aiba aceeasi suma a elementelor. Daca cele 2 submultimi gasite nu sunt disjuncte, se elimina elementele comune si se obtin 2 submultimi disjuncte A si B astfel incat suma elementelor lui A si B sa fie egale .

Pentru pct.2  X= {1,2,4,8,16,32,64,128,256,512,1024}

Junior (398 puncte)
0 0
Foarte bine doar ca ar fi complet daca ai justifica la pct 2 de ce nu are multimea gasita proprietatea ceruta.In rest solutia e identica cu solutia mea.
0 0

Am ales progresia geometrica de ratie 2, astfel  toate cele 11 elemente apartin lui M si un element oarecare al multimii va fi mai mare decat suma elementelor precedente.

n^{_{j}}=2^{j}=1+\sum_{0}^{j-1}\2^{i}

In felul acesta , nu se pot forma 2 submultimi disjuncte avand suma elementelor egala, deoarece ,oricum am incerca sa le alegem, una dintre ele va contine elementul cu cea mai mare valoare si prin consecinta, suma elementelor celeilalte submultimi va fi mai mica.

0 0
O idee mai simpla vine din reprezentarea in baza 2.Orice suma se  reprezinta binar  prin scriere unica in baza 2 a valori sumei respective .
...