Bine aţi venit pe Scientia QA!
Pentru a putea publica întrebări şi răspunsuri, trebuie să vă înregistraţi.
Atenţie! Este posibil ca e-mailul de confirmare a înregistrării să intre în Spam.
  • Inregistrare
Pune o întrebare

Newsletter


3,187 intrebari

6,348 raspunsuri

14,783 comentarii

2,003 utilizatori

O problema data in 1983 la baraj, dar usor modificata pentru 2017

1 plus 0 minusuri
547 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.

a intrebat zec Experimentat (1,665 puncte) Ian 1 in categoria Matematica
editat de zec Ian 2
  
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}

a raspuns Livia Felea Novice (268 puncte) Ian 2
selectat de zec Ian 2
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.

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.

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 .

...