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