Ensino Médio ⇒ (Conjectura) Teoria dos Números Tópico resolvido

[poti]

Fala galera. Vou reproduzir por aqui o que postei no facebook, até porque foi por lá que eu consegui uma prova para a primeira parte dessa conjectura. A segunda parte é bem chatinha, mas se alguém conseguir provar, sinta-se à vontade.

Estava somando uns números mentalmente e cheguei no que vou reproduzir abaixo. É claro que todo esse formalismo eu montei só depois de perceber o padrão, para poder me fazer claro para quem fosse ler o problema.

Notações:
[tex3]a \mid b \to \text{a divide b}[/tex3]
[tex3]a \nmid b \to \text{a nao divide b}[/tex3]
-----
[tex3]S(n) = 1 + 2 + ... + n[/tex3]
-----
[tex3]A[/tex3] é uma função definida da seguinte forma:
[tex3]A: \mathbb{N} \to \{0,1,2,3,4,5,6,7,8,9 \} \\ n \mapsto A(n) = n'[/tex3]
(Caso 1): Se a soma dos algarismos de [tex3]n[/tex3] for um algarismo, [tex3]n'[/tex3] será esse algarismo
(Caso 2): Se a soma dos algarismos de [tex3]n[/tex3] não for um algarismo, então [tex3]n'[/tex3] será a soma dos algarismos dessa soma. Caso ainda não resulte em um algarismo, soma-se até que sobre apenas um algarismo

Exemplos:
[tex3]A(13) = 1 + 3 = 4 \\
A(13) = 4[/tex3]

[tex3]A(199) = 1 + 9 + 9 = 19 \to A(19) = 1 + 9 = 10 \to A(10) = 1 + 0 = 1 \\
A(199) = 1[/tex3]
-----
[tex3]k \in \{1,4,7,...,k'\}[/tex3]
[tex3]k+1 \in \{2,5,8,...,k'+1\}[/tex3]
[tex3]k+2 \in \{3,6,9,...,k'+2\}[/tex3]
-----

Conjectura - Parte 1:
Seja [tex3]S(k) = x[/tex3]
Então [tex3]3 \nmid x \ \ e \ \ A(x) = 1[/tex3]

Conjectura - Parte 2:
Sejam [tex3]S(k+1) = y \ \ e \ \ S(k+2) = z[/tex3] para um mesmo [tex3]k[/tex3]. Vale sempre que [tex3]3 \mid y \ \ e \ \ 3 \mid z[/tex3]. Além disso:
[tex3]A(y) = 3 \to A(z) = 6[/tex3]
[tex3]A(y) = 6 \to A(z) = 3[/tex3]
[tex3]A(y) = 9 \to A(z) = 9[/tex3]

Exemplos:
[tex3]S(1) = 1 \to A(1) = 1 \\
S(2) = 1 + 2 = 3 \to A(3) = 3 \\
S(3) = 1 + 2 + 3 = 6 \to A(6) = 6 \\
\\
S(13) = 1 + 2 + ... + 13 = 91 \to A(91) = 1 \\
S(14) = 1 + 2 + ... + 14 = 105 \to A(105) = 6 \\
S(15) = 1 + 2 + ... + 15 = 120 \to A(120) = 3 \\
\\
S(34) = 1 + 2 + ... + 34 = 595 \to A(595) = 1 \\
S(35) = 1 + 2 + ... + 35 = 630 \to A(630) = 9 \\
S(36) = 1 + 2 + ... + 36 = 666 \to A(666) = 9 \\
\\
S(784) = 1 + 2 + ... + 784 = 307720 \to A(307720) = 1 \\
S(785) = 1 + 2 + ... + 785 = 308505 \to A(308505) = 3 \\
S(786) = 1 + 2 + ... + 786 = 309291 \to A(309291) = 6 \\
\\
S(1051) = 1 + 2 + ... + 1051 = 552826 \to A(552826) = 1 \\
S(1052) = 1 + 2 + ... + 1052 = 553878 \to A(553878) = 9 \\
S(1053) = 1 + 2 + ... + 1053 = 554931 \to A(554931) = 9[/tex3]

[poti]

Prova - Parte 1 (Cortesia do meu colega Tomás Fonseca)

É fácil mostrar que a divisibilidade por [tex3]3[/tex3] só aparece aos pares pela fórmula [tex3]S(n) = \frac{n(n+1)}{2}[/tex3].
Fica para o leitor.

Como [tex3]3 \nmid x[/tex3], então [tex3]x = 3t + 1[/tex3] para algum [tex3]t[/tex3] natural. Usando a fórmula:

[tex3]S(3t + 1) = \frac{(3t+1)(3t+2)}{2}[/tex3]

[tex3]S(3t + 1) = \frac{9}{2}t^2 + \frac{9}{2}t + 1[/tex3]

Usando [tex3]t' = t^2 + t[/tex3]:

[tex3]\boxed{S(3t + 1) = \frac{9}{2}t' + 1}[/tex3]

Para mostrar que [tex3]\frac{t'}{2} \in \mathbb{N}[/tex3], basta mostrar que [tex3]t'[/tex3] é sempre par:

[tex3]t' = t^2 + t = t(t+1), \ t \in \mathbb{N}[/tex3]

Se [tex3]t[/tex3] é par, seu consecutivo é ímpar, e o produto de par por ímpar é par. O mesmo vale para [tex3]t[/tex3] ímpar.

Fazendo outra substituição [tex3]t'' = \frac{t'}{2}[/tex3], temos:

[tex3]S(3t + 1) = 9t'' + 1[/tex3]

A soma dos algarismos de um múltiplo de [tex3]9[/tex3] é sempre um múltiplo de [tex3]9[/tex3], de acordo com os critérios de divisibilidade tradicionais. Como a função [tex3]A[/tex3] é construída somando algarismos até que sobre apenas um algarismo, a soma dos algarismos de [tex3]9t'' + 1[/tex3] resultará sempre em algo do tipo [tex3]9t''' + 1[/tex3]. O único algarismo que pode ser escrito dessa forma é o [tex3]1[/tex3] quando [tex3]t''' = 0[/tex3], pois para [tex3]t''' = 1[/tex3] o valor chega a [tex3]19[/tex3], que já não é mais um algarismo.

[tex3]\boxed{\therefore A(x) = 1}[/tex3]

A segunda parte não parece tão simples, mas espero que alguém tente ou dê uma ideia boa

[poti]

Uma outra forma de escrever o problema seria:

Se [tex3]3 \nmid S(n)[/tex3], então [tex3]A(S(n)) = 1[/tex3]
Se [tex3]3 \mid S(n)[/tex3], então [tex3]3 \mid A(S(n))[/tex3]

Desse jeito você acaba perdendo o padrão que eu observei (3 implica em 6, 6 implica em 3 e 9 implica em 9, sem contra-exemplo até agora) mas é um modo talvez mais fácil pra começar a provar.

[Cássio]

Não entendi algumas coisas:

tem uma parte em que você colocar: [tex3]k\in \{1, 4, 7, \ldots, k'\}[/tex3] (não entendi o que quis dizer com isso e nem as outras duas inclusões). Quando vai calcular [tex3]S(k)[/tex3] você pega qualquer natural [tex3]k?[/tex3]

Seu amigo diz que se [tex3]3\nmid x[/tex3] então [tex3]x=3t+1.[/tex3] Mas x pode ser da forma 3t+2.

Poderia escrever o problema de modo formal, indicando domínio da função e etc?

[poti]

Não entendi algumas coisas:

tem uma parte em que você colocar: [tex3]k\in \{1, 4, 7, \ldots, k'\}[/tex3] (não entendi o que quis dizer com isso e nem as outras duas inclusões). Quando vai calcular [tex3]S(k)[/tex3] você pega qualquer natural [tex3]k?[/tex3]

Seu amigo diz que se [tex3]3\nmid x[/tex3] então [tex3]x=3t+1.[/tex3] Mas x pode ser da forma 3t+2.

Poderia escrever o problema de modo formal, indicando domínio da função e etc?

1) [tex3]k[/tex3] é um natural que só pode ter esses valores, pois minha conjectura usa [tex3]S(k)[/tex3] na Parte 1. Então quando eu pego [tex3]S(k)[/tex3], eu pego qualquer valor desse conjunto [tex3]\{1, 4, 7, \ldots, k'\}[/tex3]. O mesmo vale para [tex3]k+1[/tex3] e [tex3]k+2[/tex3], pois a Parte 2 involve [tex3]S(k+1)[/tex3] e [tex3]S(k+2)[/tex3].

2) Se você usar [tex3]3t + 2[/tex3], o [tex3](n+1)[/tex3] da fórmula fica [tex3]3t + 3[/tex3] que é um múltiplo de 3, então não cobre a Parte 1.

[Cássio]

Só pra confirmar, o que entendi foi o seguinte:

Se [tex3]k\equiv 1\pmod{3},[/tex3] então [tex3]3\nmid S(k)[/tex3] e [tex3]A(S(n))=1[/tex3] (conjectura já provada)

Parte 2: Se [tex3]q\equiv 2\pmod{3}[/tex3] então [tex3]3\mid S(q)[/tex3] e [tex3]3\mid S(q+1).[/tex3] Isso?

[poti]

Essa é uma forma de interpretação mais simples que eu coloquei, mas perceba que não inclui o padrão (3->6, 6->3, 9->9) do primeiro post, que é a parte mais interessante. O que eu quis dizer na Parte 2 foi o seguinte:

Seja [tex3]S(k)[/tex3] divisível por 3 para um [tex3]k[/tex3] natural. Se [tex3]S(k-1)[/tex3] não for divisível por 3, então [tex3]A(S(k-1)) = 1[/tex3] e:

(1): [tex3]A(S(k)) = 3 \to A(S(k+1)) = 6[/tex3]
(2): [tex3]A(S(k)) = 6 \to A(S(k+1)) = 3[/tex3]
(3): [tex3]A(S(k)) = 9 \to A(S(k+1)) = 9[/tex3]

(E estes são os únicos valores assumidos pela função [tex3]A[/tex3] para quaisquer somas do tipo)

Perceba que se [tex3]S(k-1)[/tex3] for divisível por 3, então [tex3]S(k)[/tex3] é o que terá as implicações que botei acima para o [tex3]S(k+1)[/tex3]. Dê uma olhada novamente nos trios de exemplos que eu coloquei. Ocorre sempre aos trios. O primeiro do trio sempre terá [tex3]A = 1[/tex3] e o valor de [tex3]A[/tex3] do segundo implicará o do terceiro (e só varia entre 3, 6 e 9).

[Cássio]

Bom, temos o seguinte:

[tex3]k\equiv 1\pmod 9\Rightarrow S(k)=\dfrac{k(k+1)}{2}\equiv \dfrac{1\cdot (1+1)}{2}\equiv 1\pmod{9}\Rightarrow 3\nmid S(k)\\ \\ \\
\begin{cases}k\equiv 2\pmod 9\Rightarrow S(k)=\dfrac{k(k+1)}{2}\equiv \dfrac{2\cdot (2+1)}{2}\equiv 3\pmod{9}\Rightarrow 3\mid S(k)\\ \\
k\equiv 3\pmod 9\Rightarrow S(k)=\dfrac{k(k+1)}{2}\equiv \dfrac{3\cdot (3+1)}{2}\equiv 6\pmod{9}\Rightarrow 3\mid S(k)\end{cases}\\
\\ \\
k\equiv 4\pmod 9\Rightarrow S(k)=\dfrac{k(k+1)}{2}\equiv \dfrac{4\cdot (4+1)}{2}\equiv 10\equiv 1\pmod{9}\Rightarrow 3\nmid S(k)\\ \\ \\
\begin{cases}k\equiv 5\pmod 9\Rightarrow S(k)=\dfrac{k(k+1)}{2}\equiv \dfrac{5\cdot (5+1)}{2}\equiv 15\equiv 6\pmod{9}\Rightarrow 3\mid S(k)\\ \\
k\equiv 6\pmod 9\Rightarrow S(k)=\dfrac{k(k+1)}{2}\equiv \dfrac{6\cdot (6+1)}{2}\equiv 21\equiv 3\pmod{9}\Rightarrow 3\mid S(k)\end{cases}\\ \\ \\ \
\ \ k\equiv 7\pmod 9\Rightarrow S(k)=\dfrac{k(k+1)}{2}\equiv \dfrac{7\cdot (7+1)}{2}\equiv 28\equiv 1\pmod{9}\Rightarrow 3\nmid S(k)\\ \\ \\
\begin{cases}k\equiv 8\pmod 9\Rightarrow S(k)=\dfrac{k(k+1)}{2}\equiv \dfrac{8\cdot (8+1)}{2}\equiv 9\pmod{9}\Rightarrow 3\mid S(k)\\ \\
k\equiv 9\pmod 9\Rightarrow S(k)=\dfrac{k(k+1)}{2}\equiv \dfrac{9\cdot (9+1)}{2}\equiv 9\pmod{9}\Rightarrow 3\mid S(k)\end{cases}.[/tex3]

Veja que só ocorre: [tex3]3\mid S(k)[/tex3] e [tex3]3\nmid S(k-1)[/tex3] para os [tex3]k\equiv (2, 5, 8 )\pmod{9}.[/tex3]
E nesses casos tem-se o que você falou: [tex3]A(S(k))=3\Rightarrow A(S(k+1))=6;\ A(S(k))=6\Rightarrow A(S(k+1))=3[/tex3] e [tex3]A(S(k))=9\Rightarrow A(S(k+1))=9.[/tex3]

Resposta

---

Lembrando que quando [tex3]k\ge 1[/tex3], temos [tex3]A(S(k))=r,[/tex3] onde [tex3]r\le 9[/tex3] é tal que [tex3]S(k)\equiv r\pmod 9.[/tex3]

[poti]

Excelente sacada com aritmética modular, não tinha pensado nisso. Arrumei a última linha onde faltou um [tex3]A[/tex3] cobrindo [tex3]S(k+1)[/tex3].

Abraço!