Introdução

Este artigo foi inspirado pelo Problema 6 da Olimpíada Brasileira de Matemática (OBM) e da Olimpíada Brasileira de Matemática Universitária (OBMU) de 2024. Durante a pesquisa por materiais de referência em português sobre as sequências de Farey, tornou-se evidente a escassez de artigos ou publicações que tratassem do tema de forma acessível e aprofundada. A maioria do conhecimento disponível está restrita a artigos e livros em inglês, limitando o acesso a estudantes e entusiastas da matemática sem fluência nesse idioma.

Com isso, este artigo pretende preencher essa lacuna, reunindo resultados e conceitos de diversas fontes em inglês e organizando-os de forma clara e didática. O objetivo principal é fornecer um material útil tanto para matemáticos amadores curiosos quanto para estudantes avançados envolvidos em olimpíadas de matemática. As sequências de Farey são um tópico rico em propriedades e padrões interessantes, com aplicações que transcendem a teoria dos números, alcançando áreas como geometria e aproximação de números irracionais. Espero que este material inspire o interesse e expanda o horizonte matemático de todos os que explorarem estas páginas.

A História Peculiar das Sequências de Farey

A história das sequências de Farey é marcada por uma curiosa reviravolta, envolvendo um geólogo, um matemático renomado e um matemático menos conhecido. A sequência leva o nome de John Farey, um geólogo inglês que, em 1816, publicou um artigo intitulado “On a curious property of vulgar fractions” na revista Philosophical Magazine. Neste artigo, Farey observou um padrão interessante nas frações entre 0 e 1, organizadas em ordem crescente e com denominadores limitados por um determinado valor. Ele descreveu como construir a sequência, listou os termos da sequência de ordem 5 como exemplo e questionou se a propriedade já havia sido observada ou demonstrada anteriormente.

Um dos leitores do artigo de Farey foi ninguém menos que Augustin-Louis Cauchy, um dos matemáticos mais proeminentes da época. Cauchy, impressionado pela observação de Farey, forneceu uma demonstração rigorosa da propriedade no mesmo ano. A partir de então, a sequência passou a ser conhecida como “sequência de Farey”, consolidando o nome de Farey na história da matemática.

A ironia, porém, é que Farey não foi o primeiro a descobrir as propriedades da sequência. Charles Haros, um matemático menos conhecido, já havia, em 1802, identificado a propriedade e até mesmo explicado como construir a 99^a sequência. Infelizmente para Haros, seu trabalho não recebeu o reconhecimento devido na época, e ele acabou sendo ofuscado pela publicação de Farey.

O caso das sequências de Farey ilustra como a história da matemática, assim como outras áreas do conhecimento, pode ser permeada por acasos e injustiças. Farey, apesar de sua contribuição modesta, acabou imortalizado por uma descoberta que não era originalmente sua. Em A Mathematician’s Apology, G. H. Hardy comenta ironicamente: “... Farey é imortal porque não conseguiu entender um teorema que Haros havia provado perfeitamente quatorze anos antes...”.

Apesar da controvérsia em torno da autoria das descobertas sobre suas propriedades, as sequências de Farey passaram a ser estudadas na teoria dos números, com diversas aplicações, incluindo a aproximação racional de números irracionais e contribuições importantes à geometria.

Construção das Sequências de Farey

Em todos os resultados, demonstrações e soluções daqui em diante, assumiremos que as frações estão em sua forma irredutível, salvo indicação em contrário. Existem diversas formas de introduzirmos as sequências de Farey, desde uma definição pragmática até a construção de diagramas onde os andares nos dão a respectiva sequência de ordem \(n\).

Para fins didáticos, iniciemos com o algoritmo para a construção, que nos levará a um diagrama, e por fim chegaremos à definição limpa e direta. Começamos com a sequência de ordem 1, representada por: \[F_1 = \left\{ \frac{0}{1}, \frac{1}{1} \right\}.\]

Para construir a sequência de ordem \(n\), denotada por \(F_n\), a partir da sequência de ordem \(n-1\), denotada por \(F_{n-1}\), siga os seguintes passos de forma detalhada:

1. Inicialize a nova sequência:

   • Comece copiando todos os elementos da sequência \(F_{n-1}\) para uma nova sequência, que chamaremos de \(F_n\). Assim, a nova sequência \(F_n\) inicialmente é uma cópia de \(F_{n-1}\).

2. Calcule e insira as mediantes:

   • Para cada par de frações consecutivas \(\frac{a}{b}\) e \(\frac{a'}{b'}\) em \(F_{n-1}\), calcule a fração mediante entre elas, dada pela fórmula: \[\text{Mediante} = \frac{a + a'}{b + b'}.\]

   • A fração mediante é obtida somando os numeradores e os denominadores das frações consecutivas.

3. Verifique a condição do denominador:

   • Após calcular a fração mediante \(\frac{a + a'}{b + b'}\), verifique se o denominador resultante, \(b + b'\), é menor ou igual a \(n\). Isto é importante, pois queremos limitar o tamanho do denominador para garantir que a sequência \(F_n\) respeite a ordem definida.

   • Se a condição \(b + b' \leq n\) for satisfeita, então a fração mediante deve ser inserida entre \(\frac{a}{b}\) e \(\frac{a'}{b'}\) na sequência \(F_n\).

   • Caso contrário, se \(b + b' > n\), a fração mediante não é adicionada, e seguimos para o próximo par de frações consecutivas em \(F_{n-1}\).

4. Concluindo a construção da sequência:

   • Repita o processo para todos os pares consecutivos de frações em \(F_{n-1}\). Ao final, a sequência \(F_n\) estará completa, contendo tanto as frações da sequência anterior quanto as novas frações mediantes que foram inseridas, respeitando o limite do denominador.

De forma geral, esse processo pode ser resumido no diagrama a seguir:

Finalmente, uma definição direta da sequência de Farey de ordem \(n\):

Cabe observar que cada elemento da sequência de Farey é uma fração irredutível cujo denominador é menor ou igual a \(n\). Além disso, a sequência \(F_n\) contém todas as frações que podem ser formadas nesse intervalo, de modo que frações consecutivas satisfazem a condição de estarem na menor forma e ordenadas de maneira crescente.

Propriedades básicas

Nesta seção, começamos explorando a relação fundamental entre frações consecutivas, descrita pelo Teorema da Vizinhança de Farey (TVF). Este teorema nos fornece uma condição necessária e suficiente para que duas frações sejam vizinhas em uma sequência de Farey de ordem n. Tal critério é extremamente útil, pois permite identificar quais frações são mais próximas em termos de aproximação racional e também serve como base para outros resultados.

Daqui em diante, sempre que nos referirmos a frações que são termos consecutivos de uma sequência de Farey, usaremos o termo vizinhas de Farey para nos referirmos às mesmas.

O corolário a seguir, que nomearemos de Corolário da Mediante, revela uma característica interessante sobre frações consecutivas: a fração intermediária entre duas vizinhas de Farey é obtida através da soma dos numeradores e denominadores, resultando na chamada fração mediante. Esse corolário reforça a ideia de simetria e estrutura nas sequências de Farey, mostrando que frações mediantes surgem naturalmente e estão posicionadas entre as frações originais, conforme esperado.

Vale notar que uma das consequências importantes do TVF foi estabelecer uma cota mínima para a soma dos denominadores de duas frações vizinhas, cota essa que se verifica ser a melhor possível. Uma pergunta natural que emerge é: será que para três frações vizinhas também existe uma cota mínima para a soma de seus denominadores? A resposta é afirmativa. Por ora, apresentaremos uma cota mínima menos refinada, reservando para a seção de Problemas Olímpicos a demonstração da melhor cota possível (que apareceu como problema 6 na OBM de 2024!).

Como próximo resultado, temos o que chamaremos de Corolário da Aproximação, pois ele quantifica a diferença entre a mediante de duas frações e cada uma destas. Essa estimativa não apenas caracteriza a aproximação entre frações, mas também demonstra como as mediantes são eficientes em dividir o espaço racional de maneira equilibrada. Este resultado, além de sua importância teórica, possui implicações práticas em problemas de aproximação racional de números reais.

O resultado a seguir mostra que, se tomarmos frações vizinhas em uma metade da sequência, há uma correspondência direta com frações na outra metade, formando um espelho perfeito. Essa propriedade é fundamental para compreender a estrutura palíndroma das sequências de Farey, uma característica que será explorada mais a fundo posteriormente.

Por fim, o Lema da Quantidade de Termos (LQT). Ele nos fornece uma fórmula recursiva para determinar quantos termos existem em uma sequência de Farey de ordem \(n\). Essa relação recursiva depende da função Totiente de Euler, \(\varphi(n)\), indicando que a quantidade de termos adicionados de uma ordem para outra está relacionada aos inteiros coprimos a \(n\). Esse resultado também serve de ponto de partida para deduzir outras propriedades, como a fórmula fechada para a quantidade de termos.

Observe que o LQT revela que a quantidade de elementos novos em \(F_{n}\), em comparação com \(F_{n-1}\), é dada por \(\varphi(n)\). Os valores inteiros \(1 \leq k < n\) que são coprimos com \(n\) aparecem no numerador dos novos membros de \(\mathrm{F}_{n}\), com o denominador de cada novo termo em \(\mathrm{F}_{n}\) sendo sempre igual a \(n\). Assim, uma rápida contagem nos leva a

\[\left|F_n\right| = 1 + \sum_{k=1}^{n} \varphi(k).\]

Por outro lado, do seguinte resultado bem conhecido \[\lim _{n \rightarrow \infty} \frac{\sum_{k=1}^{n} \varphi(k)}{n^2}=\frac{3}{\pi^2},\] resulta que \[\lim _{n \rightarrow \infty} \frac{\left|F_n\right|-1}{n^2}=\frac{3}{\pi^2}.\]

Propriedades Especiais

Embora os resultados presentes nesta seção também sejam propriedades das sequências de Farey, eles são menos conhecidos, mas não menos belos e importantes. Para começar, temos o:

Um resultado interessantíssimo sobre a estrutura dos denominadores em uma sequência de Farey é que eles formam uma sequência palindrômica. Antes, cabe a:

Com isso, podemos enunciar o:

Observação. Por comprimento de um palíndromo, entendemos o número de elementos que aparecem nele.

Aplicações

A teoria das sequências de Farey possui diversas aplicações interessantes, especialmente no contexto da aproximação de números reais por frações racionais. Devido às suas propriedades de estrutura e ordenação, as sequências de Farey permitem encontrar aproximações racionais precisas, utilizando denominadores relativamente pequenos. A seguir, apresentamos uma série de resultados que ilustram como as sequências de Farey podem ser aplicadas na resolução de problemas de aproximação racional.

O primeiro teorema desta seção trata da aproximação de um número real \(x\) por uma fração cujo denominador está limitado a um valor específico. Esse resultado é particularmente útil para encontrar boas aproximações racionais com um denominador pré-definido, destacando o papel importante das mediantes no processo de aproximação eficiente de valores reais. Essa abordagem é essencial em contextos onde a simplicidade e praticidade da fração são preferíveis, como na computação numérica e na aritmética prática.

Após esse teorema, estendemos o conceito ao caso dos números irracionais. O objetivo aqui é provar que é sempre possível aproximar um número irracional com a precisão desejada utilizando frações racionais.

Em seguida, apresentamos o famoso Teorema de Hurwitz, que também faz uso das sequências de Farey para garantir a existência de aproximações racionais precisas para números irracionais. O Teorema de Hurwitz vai além ao garantir que, para qualquer número irracional, existem infinitas frações que aproximam este número com um erro menor do que uma constante, que depende do quadrado do denominador.

Problemas Olímpicos

Agora, vamos colocar a teoria em prática, resolvendo alguns problemas olímpicos.
Problema 1. Em uma formação regular de \(n \times n\), há \(n^2\) estudantes dispostos em uma grade. Dois estudantes podem ver um ao outro se a linha direta de visão entre eles não estiver obstruída por outro estudante. Em outras palavras, se três estudantes estão colineares, o estudante do meio bloqueia a linha de visão entre os outros dois. Quantos estudantes o estudante localizado no canto inferior esquerdo da grade pode ver?

Solução. Coloquemos coordenadas nos estudantes, de forma que aquele no canto inferior esquerdo seja o ponto \((0,0)\). Assim, a quantidade de estudantes que o estudante na posição \((0,0)\) enxerga acima da diagonal \(y = x\) é equivalente ao número de frações irredutíveis na sequência de Farey \(F_{n-1}\).

Ao restringirmos apenas aos pontos \((x, y)\) com \(x \leq y\), estamos contando o número de frações irredutíveis entre \(0\) e \(1\) com denominador no máximo \(n-1\). A resposta final é, então, \(2|F_{n-1}| - 1\), onde \(|F_n|\) representa o número de termos na sequência de Farey de ordem \(n\). 0◻
Problema 2. Sejam \(P\) e \(Q\) polinômios inteiros. Suponha que, para todos os inteiros \(a\) e \(b\), \(aP + bQ\) possui uma raiz inteira. Então \(P\) e \(Q\) possuem uma raiz inteira em comum.

Solução. Suponha que \(P\) e \(Q\) não têm raízes inteiras em comum. Vamos demonstrar que isso leva a uma contradição. Da suposição que \(P\) e \(Q\) não têm raízes inteiras em comum, temos que \((P(n),Q(n))\neq (0,0)\). Para cada \(n\in\mathbb{N}\), a aplicação linear \(T_n:\mathbb{R}^2\to\mathbb{R}\) dada por \(T(x,y)=xP(n)+yQ(n)\) é sobrejetiva e seu kernel é um subespaço de dimensão 1 que passa pela origem. Em outras palavras, o kernel de \(T_n\), que chamaremos de \(R_n\), é uma reta que passa pela origem e com coeficiente angular racional. Seja \[\mathbb{Z}_n^2/{\sim} = \{[(a,b)] : (a,b) \in \mathbb{Z}^2, 0 < |a|, |b| \leq n\},\] onde \([(a,b)] = \{(c,d) \in \mathbb{Z}^2 : bd = ac\}\). Defina a função

\[\begin{aligned} A:\mathbb{Z}_n^2/{\sim} &\to R=\{R_n;n\in\mathbb{Z}\} \\ A([(a,b)]) &= R_k, \text{ onde } (a,b)\in R_k. \end{aligned}\]

Como para todo \((a,b)\in\mathbb{Z}^2\) existe \(k\) inteiro tal que \(aP(k)+bQ(k)=0\), então \(A\) está bem definida. É imediato também que \(A\) é injetiva. Se \(aP(k)+bQ(k)=0\), então, pelo Critério de Pesquisa de Raízes Racionais, temos \[k\leq \mid aP(0)+bQ(0)\mid\leq 2n\cdot\text{máx}\{\mid P(0)\mid,\mid Q(0)\mid\}\]

Logo, usando o Problema 1, concluímos que

\[2(2\mid F_N\mid-1)\leq 2n\cdot \text{máx}\{\mid P(0)\mid,\mid Q(0)\mid\},\]

um absurdo, já que \(\lim _{n \rightarrow \infty} \frac{\left|F_n\right|}{n^2}=\frac{3}{\pi^2}\). Segue o resultado.0◻

Problema 3. A sequência de Fibonacci é definida como \(f_1 = f_2 = 1\), \(f_{n+2} = f_{n+1} + f_n\) \((n \in \mathbb{N})\). Suponha que \(a\) e \(b\) são inteiros positivos tais que \(\frac{a}{b}\) está entre as duas frações \(\frac{f_n}{f_{n-1}}\) e \(\frac{f_{n+1}}{f_n}\). Mostre que \(b \geq f_{n+1}\).

Solução. De fato, podemos usar a mesma estratégia da prova do TVF para mostrar que, se \(|ad - bc| = 1\), para cada fração \(\frac{p}{q}\) que está entre \(\frac{a}{b}\) e \(\frac{c}{d}\), temos que \(q\) é maior ou igual a \(b + d\).

Tome \(\frac{a}{b} < \frac{p}{q} < \frac{c}{d}\) e \(ad - bc = -1\). Então, \(\frac{p}{q} - \frac{a}{b} \geq \frac{1}{bq}\) e \(\frac{c}{d} - \frac{p}{q} \geq \frac{1}{dq}\) (pois \(pb > aq\) e \(cq > pd\)). Somando-as, temos \[\frac{c}{d} - \frac{a}{b} \geq \frac{1}{bq} + \frac{d}{q}.\] Como \(\frac{c}{d} - \frac{a}{b} = \frac{1}{bd}\), temos \(\frac{1}{bd} \geq \frac{b + d}{bdq}\). Assim, obtemos \(q \geq b + d\).

Neste caso, \(|f_n^2 - f_{n-1} f_{n+1}| = 1\). Logo, para qualquer \(\frac{p}{q}\) entre \(\frac{f_{n+1}}{f_n}\) e \(\frac{f_n}{f_{n-1}}\), temos \(q \geq f_n + f_{n-1} = f_{n+1}\).0◻
Problema 4 Existe um conjunto de esferas \(\mathcal{S}\), duas a duas disjuntas, tal que para cada ponto \(P \in \mathbb{Q}^2\) existe uma esfera \(s \in \mathcal{S}\) tangente ao plano no ponto \(P\)?

Solução. Sim, existe tal conjunto de esferas. Vamos construir explicitamente esse conjunto de esferas disjuntas, associando a cada ponto \(P \in \mathbb{Q}^2\) uma esfera tangente ao plano no ponto \(P\).

Começamos considerando as sequências de Farey \(F_n\). Definimos então \(F_n^2 = F_n \times F_n\), que é o conjunto de pontos no quadrado unitário \([0,1]^2\) com coordenadas racionais e denominadores limitados por \(n\).

Observamos que \(F_n^2 \subseteq F_{n+1}^2\) e que a união de todos os \(F_n^2\) é exatamente \(\mathbb{Q}^2 \cap [0,1]^2\). Para cada \(n \geq 1\), definimos o conjunto dos novos pontos introduzidos na etapa \(n\) como \(S_n = F_n^2 \setminus F_{n-1}^2\), com a convenção de que \(F_0^2 = \emptyset\).

Nosso objetivo é associar esferas disjuntas aos pontos em \(F_n^2\) de forma que, para cada \(P \in F_n^2\), exista uma esfera tangente ao plano no ponto \(P\), e que essas esferas sejam disjuntas entre si. Faremos isso por indução em \(n\).

Suponha que já tenhamos associado esferas disjuntas aos pontos em \(F_{n-1}^2\), todas com raios menores ou iguais a \(r_{n-1}\). Na etapa \(n\), queremos associar esferas aos pontos em \(S_n\) de modo que:

1. As esferas associadas aos pontos em \(S_n\) sejam disjuntas entre si. 2. As esferas associadas aos pontos em \(S_n\) não intersectem as esferas já atribuídas aos pontos em \(F_{n-1}^2\).

Para garantir isso, escolhemos um raio \(r_n\) suficientemente pequeno. Como \(S_n\) é um conjunto finito de pontos cujas coordenadas têm denominadores entre \(n-1\) e \(n\), existe uma distância mínima positiva \(\delta_n\) entre quaisquer dois pontos distintos em \(S_n\), e uma distância mínima positiva \(\epsilon_n\) entre um ponto em \(S_n\) e um ponto em \(F_{n-1}^2\). Escolhemos então \(r_n\) tal que: \[r_n < \frac{1}{3} \min\{\delta_n, \epsilon_n, r_{n-1}\}.\] Com essa escolha, associamos a cada ponto \(P \in S_n\) uma esfera de raio \(r_n\), centrada em \((x_P, y_P, r_n)\), onde \((x_P, y_P)\) são as coordenadas de \(P\). Essa esfera é tangente ao plano \(z = 0\) no ponto \(P\).

Verifiquemos que as esferas associadas aos pontos em \(S_n\) são disjuntas entre si:
Para quaisquer dois pontos distintos \(P, Q \in S_n\), a distância entre eles no plano é pelo menos \(\delta_n\). Portanto, a distância entre os centros das esferas é também pelo menos \(\delta_n\), e como \(2r_n < \delta_n\), as esferas não se intersectam.

Além disso, as esferas associadas aos pontos em \(S_n\) não intersectam as esferas associadas aos pontos em \(F_{n-1}^2\). A distância entre um ponto \(P \in S_n\) e um ponto \(Q \in F_{n-1}^2\) é pelo menos \(\epsilon_n\), e a soma dos raios das esferas correspondentes é menor que \(r_n + r_{n-1} \leq \frac{1}{3} \epsilon_n + r_{n-1} \leq \epsilon_n\), pois \(r_n \leq \frac{1}{3} \epsilon_n\) e \(r_{n-1} \leq \frac{1}{3} \epsilon_n\). Portanto, as esferas não se intersectam.

Procedendo dessa forma para cada \(n\), atribuímos esferas disjuntas a todos os pontos em \(\mathbb{Q}^2 \cap [0,1]^2\). Para pontos em \(\mathbb{Q}^2\) fora do quadrado unitário, podemos estender a construção por translações inteiras, cobrindo todo o plano racional \(\mathbb{Q}^2\).0◻
Problema 5 (OBM 2024 - Nível 3 - Problema 6) Seja \(n > 1\) um inteiro positivo. Enumere em ordem crescente todas as frações irredutíveis do intervalo \([0,1]\) que têm denominador positivo e menor ou igual a \(n\):

\[\frac{0}{1} = \frac{p_0}{q_0} < \frac{p_1}{q_1} < \cdots < \frac{p_M}{q_M} = \frac{1}{1}.\]

Determine, em função de \(n\), o menor valor possível de \(q_{i-1} + q_i + q_{i+1}, 0 < i < M\).

Solução. Seja \(S_n\) a menor soma dos denominadores de três frações consecutivas na sequência de Farey de ordem \(n\). Do Corolário da Cota Mínima, temos que

\[S_n \geq \left\lceil \frac{4(n+1)}{3} \right\rceil.\]

Pela prova do Corolário, essa cota seria atingida assumindo \(d \geq 1\) (mantendo a notação usada na prova do corolário). Repetindo os mesmos cálculos, se a cota mínima fosse atingida para \(d \geq 2\), então teríamos

\[S_n \geq \left\lceil \frac{3(n+1)}{2} \right\rceil.\]

Usaremos essas estimativas para provar que, para \(k \geq 1\), a tripla de frações cuja soma dos denominadores é mínima é:

\[\begin{aligned} & n = 6k \rightarrow \left(\frac{1}{2k+1}, \frac{2}{4k+1}, \frac{1}{2k}\right), \\ & n = \begin{cases} 6k+1, \\ 6k+2, \\ 6k+3 \end{cases} \rightarrow \left(\frac{1}{2k+2}, \frac{2}{4k+3}, \frac{1}{2k+1}\right), \\ & n = 6k+4 \rightarrow \left(\frac{k}{2k+1}, \frac{2k+1}{4k+4}, \frac{k+1}{2k+3}\right), \\ & n = 6k+5 \rightarrow \left(\frac{1}{2k+3}, \frac{2}{4k+5}, \frac{1}{2k+2}\right). \end{aligned}\]

Note inicialmente que, pelo TVF, cada trio de frações é de fato composto por frações consecutivas das respectivas sequências. Também é imediato pelo Corolário da Cota Mínima que, para os casos \(n=6k\) e \(n=6k+3\), as respectivas frações já atingem o mínimo ótimo, sendo portanto a melhor cota. Mostremos para os demais casos que, de fato, as frações citadas nos fornecem a melhor cota possível. A tabela a seguir detalha as cotas mínimas para cada estimativa:

\[\begin{array}{|c|c|c|c|} \hline n & \text{Cota mín. }& \text{Cota mín. }& \text{Cota mín.}\\ &\text{para }d=1&\text{para }d=2& \text{conjecturada}\\ \hline 6k+1 & 8k+3 & 9k+3 & 8k+6 \\ 6k+2 & 8k+4 & 9k+3 & 8k+6 \\ 6k+4 & 8k+7 & 9k+6 & 8k+8 \\ 6k+5 & 8k+8 & 9k+8 & 8k+10 \\ \hline \end{array}\]

Note que, para \(k > 3\), as estimativas para \(d \geq 2\) já superam as cotas conjecturadas. Então, deixamos os casos \(k = 1, 2, 3\) como exercício e voltamos nossa atenção para quando \(d = 1\).

Quando \(d = 1\), temos \(S_n\) par e, portanto, para o caso \(n = 6k+4\), concluímos que \(S_{6k+4} = 8k+8\). Veja os demais casos a seguir:

Casos \(n = 6k+1\) e \(n = 6k+2\): Faremos as contas para \(n = 6k+1\), mas o caso \(n = 6k+2\) é totalmente análogo. Suponha que \(\frac{a}{b} < \frac{x}{y} < \frac{u}{v}\) é um trio em \(F_{6k+1}\) tal que \(b + y + v = 8k + 4\). Assim, temos \(y = b + v = 4k + 2\). Como \(b + y \geq 6k + 2, y + v \geq 6k + 2\) e \((b, y) = (y, v) = 1\), segue que \(b = v = 2k+1\). As equações do TVF nos dão

\[\left\{ \begin{array}{l} 2k(a + u) - a(2k+1) = 1, \\ (2k+1)u - 2k(a + u) = 1 \end{array} \right. \Rightarrow \left\{ \begin{array}{l} 2ku - a = 1, \\ u - 2ka = 1, \end{array} \right.\]

chegando à contradição \((2k+1)(u-a) = 2\). Logo, \(S_{6k+1} = 8k+6\).

Caso \(n = 6k+5\):

Mantendo a notação do caso anterior, suponha agora que \(b + y + v = 8k + 8\). Devemos ter \(b + y \geq 6k + 6, y + v \geq 6k + 6\) e \(y = b + v = 4k + 4\). Com isso, \(b \geq 2k+3\) e \(v \geq 2k+3\), já que \(y\) é par, o que leva a uma contradição, pois a soma já supera \(4k+6\). Daí, \(S_{6k+5} = 8k+10\).

Concluímos, portanto, que as cotas mínimas para \(n \geq 6\) são:

\[S_n = 8 \cdot \left\lfloor \frac{n}{6} \right\rfloor + \begin{cases} 2, & \text{se } n \equiv 0 \pmod{6}, \\ 6, & \text{se } n \equiv 1, 2, 3 \pmod{6}, \\ 8, & \text{se } n \equiv 4 \pmod{6}, \\ 10, & \text{se } n \equiv 5 \pmod{6}. \end{cases}\]

Os casos iniciais são \(S_1 = 2, S_2 = 4, S_3 = 6, S_4 = 8, S_5 = 10\). Assim, concluímos o problema.
0◻

Exercícios

Exercício 1. Seja \(a_1, a_2, \ldots, a_n\) uma sequência finita de inteiros. Dizemos que essa sequência é regular se existe um número real \(x\) tal que

\[\lfloor kx \rfloor = a_k \quad \text{para } 1 \leq k \leq n.\]

Dado um índice \(1 \leq k \leq n\), o termo \(a_k\) é chamado de forçado se a única forma de completar a sequência \(a_1, a_2, \ldots, a_{k-1}, b\) para ser regular é tomando \(b = a_k\) (ou seja, \(a_k\) é forçado se não houver outra opção para \(b\) que mantenha a regularidade da sequência). Encontre o número máximo possível de termos forçados em uma sequência regular com \(1000\) termos.

Exercício 2. Observe as seguintes frações. No primeiro passo temos \(\frac{0}{1}\) e \(\frac{1}{0}\), e em cada passo escrevemos \(\frac{a+b}{c+d}\) entre \(\frac{a}{b}\) e \(\frac{c}{d}\), e fazemos isso indefinidamente.

\[\begin{array}{ccccccccccccccccccccccccc}\frac{0}{1}&&&&&&&&\frac{1}{0}\\ \frac{0}{1}&&&&\frac{1}{1}&&&&\frac{1}{0}\\ \frac{0}{1}&&\frac{1}{2}&&\frac{1}{1}&&\frac{2}{1}&&\frac{1}{0}\\ \frac{0}{1}&\frac{1}{3}&\frac{1}{2}&\frac{2}{3}&\frac{1}{1}&\frac{3}{2}&\frac{2}{1}&\frac{3}{1}&\frac{1}{0}\\ &&&&\dots\end{array}\]

• Prove que cada uma dessas frações é irredutível.

• No plano, colocamos infinitos círculos de diâmetro 1, sobre cada inteiro na reta real, um círculo. Indutivamente, colocamos círculos de forma que cada círculo seja tangente a dois círculos adjacentes e à reta real, e continuamos isso indefinidamente. Prove que os pontos de tangência desses círculos são exatamente todos os números na parte (a) (exceto \(\frac{1}{0}\)).

Exercício 3. (IMO Shortlist 2016) Considere frações \(\frac{a}{b}\) onde \(a\) e \(b\) são inteiros positivos.

• Prove que, para todo inteiro positivo \(n\), existe tal fração \(\frac{a}{b}\) tal que \(\sqrt{n} \leq \frac{a}{b} \leq \sqrt{n} + 1\) e \(b \leq \sqrt{n} + 1\).

• Mostre que existem infinitos inteiros positivos \(n\) tais que nenhuma fração \(\frac{a}{b}\) satisfaz \(\sqrt{n} \leq \frac{a}{b} \leq \sqrt{n} + 1\) e \(b \leq \sqrt{n}\).

Exercício 4.(OBM 2024 - Nível U)Para cada inteiro positivo \(n\), enumere em ordem crescente todas as frações irredutíveis do intervalo \([0, 1]\) que têm denominador positivo e menor ou igual a \(n\): \[\frac{0}{1} = \frac{p_0}{q_0} < \frac{1}{n} = \frac{p_1}{q_1} < \cdots < \frac{1}{1} = \frac{p_{M(n)}}{q_{M(n)}}.\]

Seja \(k\) um inteiro positivo. Definimos, para cada \(n\) tal que \(M(n) \geq k - 1\), \[f_k(n) = \min \left\{ \sum_{s=0}^{k-1} q_{j+s} : 0 \leq j \leq M(n) - k + 1 \right\}.\]

Determine, em função de \(k\), \(\lim_{n \to \infty} \frac{f_k(n)}{n}\).

Exercício 5. (USOMO 2020) Suponha que \((a_1, b_1), (a_2, b_2), \dots, (a_{100}, b_{100})\) são pares ordenados distintos de inteiros não negativos. Seja \(N\) o número de pares de inteiros \((i, j)\) que satisfazem \(1 \leq i < j \leq 100\) e \(|a_i b_j - a_j b_i| = 1\). Determine o maior valor possível de \(N\) considerando todas as escolhas possíveis dos 100 pares ordenados.

Exercício 6. (USAMO 1999) Seja \(p > 2\) um número primo e sejam \(a, b, c, d\) inteiros não divisíveis por \(p\), tais que \[\left\{\frac{r a}{p}\right\} + \left\{\frac{r b}{p}\right\} + \left\{\frac{r c}{p}\right\} + \left\{\frac{r d}{p}\right\} = 2\] para qualquer inteiro \(r\) não divisível por \(p\). Prove que pelo menos dois dos números \(a + b, a + c, a + d, b + c, b + d, c + d\) são divisíveis por \(p\).

Carlos Augusto D. Ribeiro é professor associado na Universidade Federal do Delta do Parnaíba (UFDPar) e um ex-olímpico com prêmios na OBM, OCM, Rioplatense e outras competições. Consciente do impacto transformador que a Olimpíada de Matemática teve em sua trajetória, hoje ele retribui participando da organização da OBM, colaborando com a ONG Cactus na criação de materiais de treinamento que alcançam milhares de estudantes da rede pública e atuando no Projeto CQD, onde tem a alegria de trabalhar com amigos dos tempos de olimpíada. Nerd assumido, viciado em Star Wars e apaixonado por sua esposa, Keyv Lany, ele tenta manter o bom humor (mesmo quando seus pets, Ahsoka e Yoda, decidem causar!).

Bibliografia