mateforum.ro Forum Index mateforum.ro

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

JBTST I 2008, Problema 2

 
Post new topic   Reply to topic    mateforum.ro Forum Index -> Juniori -> Teoria Numerelor
View previous topic :: View next topic  
Author Message
Laurian Filip
Site Admin


Joined: 25 Nov 2007
Posts: 473
Location: Bucuresti

PostPosted: Sat May 03, 2008 9:09 pm    Post subject: JBTST I 2008, Problema 2 Reply with quote

Sa se arate ca pentru orice n\in \mathbb{N}* exista un multiplu de n cu suma cifrelor egala cu n.
Back to top
View user's profile Send private message Visit poster's website
Ahiles
Euclid


Joined: 17 Apr 2008
Posts: 28

PostPosted: Thu May 15, 2008 7:50 pm    Post subject: Reply with quote

Fie n=2^k\cdot5^p\cdot m, unde m nu se divide nici cu 5 nici cu 2. Atunci
10^{\phi (m)}\equiv 1 \pmod{m}.
Fie \phi (m)=t.
Atunci considerm numarul A=10^t+10^{2t}+\ldots+10^{pn}\equiv n \equiv 0 \pmod m. Deci numarul acesta se divide cu m si are suma cifrelor egala cu n (n unitati).
Daca r=\max\{k,p\} atunci este destul de adaugat la sfirsitul lui a un numar de r zerouri, fiindca atunci a_1 se divide cu m si cu 10^r, c.c.t.d.
Back to top
View user's profile Send private message
Filip Chindea
Newton


Joined: 27 Sep 2007
Posts: 323
Location: Bucharest

PostPosted: Mon May 26, 2008 8:53 pm    Post subject: Reply with quote

Rezolvarea personala este identica (pana la notatii) cu precedenta! Deloc surprinzator, din punct de vedere al problemelor puse de-a lungul timpului (OIM, etc.), astfel de idei reprezinta abordari standard.

Solutia autorului [Dan Schwarz]. Din n^2 - n + 1 = n(n - 1) + 1 puteri distincte ale lui zece, cf. principiului cutiei n vor avea acelasi rest \pmod{n}. Deci suma lor rezolva problema. \qed

Poate neasteptat, dar aceasta (condensata) solutie rezulta foarte natural din consideratii de teoria aditiva elementara. De fapt, se arata ca E(\mathbb{Z}_n) = 2n - 1 (vezi nota), astfel incat acel n^2 - n + 1 poate fi inlocuit cu 2n - 1. Aceasta conduce la solutia si mai concisa:

Aplicati teorema Erdos-Ginzburg-Ziv multimii \{ 10^1, ..., 10^{2n-1} \}. \qed

Insistenta pe acest rezultat ducea in sub 5 minute la solutie. Garantat. Cu toate acestea (desi era nr. 2 pe lista, deci nu putem vorbi de motive psihologice, timp, etc. etc.) suma punctelor elevilor cls 7-8 pe aceasta chestiune a fost... 2!. Doi de 1. Recunosc, nici mie nu mi-a venit in minte sa aplic acest rezultat... decāt peste mult timp (desi parea natural). Rareori apar astfel de contraste.

Sinteza a rezultatelor cunoscute (Teoria aditiva). Pentru G grup aditiv abelian finit, notam f\left(G, S\right), pentru S \subseteq \mathbb{N}^{\ast}, cel mai mic m \in \mathbb{N}^{\ast} cu proprietatea ca pentru orice elemente, nu neaparat distincte, a_1, ..., a_m \in G, exista o multime de indici (x_j)_{j \in \overline{1, k}}, cu k \in S, astfel incat \sum_{j \in \overline{1, k}} a_{x_j} = 0.

Problema determinarii existentei, si apoi valorii lui f(G, S) este cunoscuta sub numele de problema de suma zero pentru G.

Cateva rezultate:

Constanta Davenport a lui G - \mathcal{D}(G) := f(G, \mathbb{N}^{\ast}) \le |G| =: n (Erdos, cunoscuta probabil majoritatii juniorilor, dar nu sub aceasta forma) - aplicati principiul cutiei sumelor 0, a_1, ..., a_1 + \cdots + a_n; \mathcal{D}(\mathbb{Z}_n) = n.

E(G) := f(G, n) \le n^2 - n + 1 (demonstratia este exact cea de mai sus). In particular, E(\mathbb{Z}_n) = 2n - 1 (Erdos, Ginzburg, Ziv, 1961 - corolar al teoremei Chevalley-Warning, dar se cunosc si o solutie combinatorica, si una ceva mai putin elementara).

Doua chestii ceva mai "exotice":

Din 4n - 3 puncte laticiale, n au baricentrul laticial (fosta conjectura a lui Kemnitz, demonstrata de C. Reiher).

In final, teorema generala E(G) = \mathcal{D}(G) + n - 1 (Formula lui Gao, 1996). De asemenea, teorema EGZ este corolar si al acestui rezultat.

Pentru a le revedea in detaliu, dar si lectura ulterioara, vedeti aici si aici (daca aveti MB/s si multa rabdare Smile ).
_________________
Life is complex: it has real and imaginary components.


Last edited by Filip Chindea on Mon May 26, 2008 10:00 pm; edited 2 times in total
Back to top
View user's profile Send private message Yahoo Messenger
Beniamin Bogosel
Co-admin


Joined: 07 Mar 2008
Posts: 760
Location: Chambery, Franta

PostPosted: Mon May 26, 2008 10:45 pm    Post subject: Reply with quote

Teorema asta, EGZ probabil ca e cunoscuta. Cel putin in forma in care era postata la seniori. Smile
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
Dragos Fratila
Newton


Joined: 04 Oct 2007
Posts: 335
Location: Paris

PostPosted: Tue May 27, 2008 10:28 am    Post subject: Reply with quote

Daca e cineva interesat de articolul lui C. Reiher (este scurt si elementar) in care demonstreaza conjectura lui Kemnitz il poate lua de aici:
http://uploadfile.org/download.php?id=gCwfdhVQQfpMkIzXW56e
_________________
"Greu la deal cu boii mici..."
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    mateforum.ro Forum Index -> Juniori -> Teoria Numerelor All times are GMT + 2 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum



Powered by phpBB © 2001, 2005 phpBB Group