JBTST I 2008, Problema 2

[Laurian Filip]

Sa se arate ca pentru orice \( n\in \mathbb{N}* \) exista un multiplu de \( n \) cu suma cifrelor egala cu \( n \).

[Ahiles]

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.

[Filip Chindea]

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 ).

[Beniamin Bogosel]

Teorema asta, EGZ probabil ca e cunoscuta. Cel putin in forma in care era postata la seniori.

[Dragos Fratila]

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=g ... pMkIzXW56e