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,148 intrebari

6,314 raspunsuri

14,699 comentarii

1,985 utilizatori

O altfel de problema

2 plusuri 0 minusuri
161 vizualizari
Problema are ca autor pe Ioan Tomescu si e din o veche GM.

Fie multimea M={1,2,.....,1987} ,aratati ca exista o colorare cu 4 culori a elementelor din M astfel incat sa nu avem 10 termeni in progresie aritmetica monocromatici.Ramane valabil si pentru multimea numerelor de la 1 la 2017?
a intrebat zec Experimentat (1,546 puncte) Feb 10 in categoria Matematica
  
Dacă fac o legătură cu problema anterioară, la prima vedere cred că problema se poate rezolva prin metoda pe care a folosit-o Livia Felea la problema cu mulțimile disjuncte.

Cred că se reduce, deși n-am verificat, la o problemă de combinații și cutia lui Drichlet.
Deși nu cred că este chiar comun acest tip de rezolvare, o colorare a lor ținând cont de factorizarea numerelor duce la un rezultat interesant.

Notând cu x suma puterilor factorilor primi ai unui număr din șirul 1,...,1987, iar x=4q+i,  se poate arăta că nu există o progresie aritmetică pentru 10 termeni din șir care au restul i prin împărțirea la 4 a lui x.

Dar să vedem dacă apare o soluție mai simplă, că e cam mult de scris.

1 Raspuns

2 plusuri 0 minusuri
 
Cel mai bun raspuns

Numărul total de progresii aritmetice de 10 termeni din mulțimea M este T =218.317 (vezi problema anterioară). 

Consider că P este o progresie monocromă de 10 termeni din mulțimea M. Cei 1977 membri rămași din mulțimea M pot fi aranjați în 41977 moduri dat fiind că fiecare poate avea una din patru culori. Cum și culoarea progresiei P poate fi de patru feluri avem 4*41977 = 41978 moduri în care poate fi colorată mulțimea M pentru o singură progresie P. Dar sînt T progresii în mulțimea M, deci numărul de moduri în care poată fi colorată mulțimea M astfel încît să existe o progresie aritmetică monocromă este T*41978.  Acest număr trebuie comparat cu numărul de moduri în care poate fi colorată M, acesta fiind 4^1987 ( 1987 elemente cu patru culori posibile).
T*41978 : 41987 -> T : 49 -> Cum T este 218.317 < 49 înseamnă că există în mulțimea M destule configurații colorate (mai exact 49 - 218.317) care să nu conțină o progresie monocromă. Rezultatul este valabil și pentru șirul numerelor pînă la 2017. 

a raspuns Gheorghiţa Experimentat (3,548 puncte) Feb 10
selectat de zec Feb 10

O nelămurire, vă rog, ca să înțeleg mai bine cum ați gândit.

"

Cei 1977 membri rămași din mulțimea M pot fi aranjați în 41977 moduri dat fiind că fiecare poate avea una din patru culori.

"

Cuvântul pe care l-am bolduit și subliniat în exprimarea Dumneavoastră ar trebui să fie colorați sau este corect aranjați ?

Colorați, Domnia voastră.
Da, mi-am dat seama ulterior.

Scuze dacă mesajul anterior a părut să aibă o notă critică..
E foarte elegant raspunsul lui Gheorghita si Ciprian avea o idee interesanta ,daca ai un raspuns la problema poate deveni un cel mai bun raspuns.

...