Prova de Nivelamento - 1996

Gabarito

Questão 1. Mostre que dados a, b números naturais então se \frac{a^{2}+b^{2}}{ab+1} é um número inteiro, então também é um quadrado perfeito.

Diremos que um par (a, b) de números naturais é uma solução quando ab + 1 divide a^{2} + b^{2}. Seja (a, b) uma solução com b ≠ 0. Tome c = ab + 1. Temos ab = c − 1, logo b divide c − 1 e a = \frac{c−1}{b}. Temos:

\frac{a^{2} + b^{2}}{ab + 1} = \frac{(\frac{c−1}{b})^{2} + b^{2}}{c} = \frac{c^{2} − 2c + 1 + b^{4}}{b^{2}c} ∈ ℕ.

Temos que c divide \frac{c^{2}−2c+1+b^{4}}{b^{2}} , logo c divide c^{2} −2c+1+b^{4} e portanto c divide b^{4} +1. Assim (b, c) é um par de números naturais diferentes de zero com b | c − 1 e c | b^{4} + 1. Um par com tais propriedades será chamado uma solução associada. Temos o seguinte lema:

Lema 1. Seja (a, b) uma solução com b ≠ 0. Então o par (b, c) dado por c = ab + 1 é uma solução associada. Reciprocamente se (b, c) é uma solução associada então (a, b) dado por a = \frac{c−1}{b} é uma solução com b ≠ 0.

Demonstração.

A primeira parte é mostrada pelos cálculos acima. Agora se (b, c) é uma solução associada então como b | c − 1, b ≠ 0, podemos considerar o número natural a = \frac{c−1}{b} e o par (a, b). Como c divide b^{4} + 1, c divide c^{2} − 2c + 1 + b^{4}. Como b divide c − 1, b^{2} divide (c − 1)^{2} + b^{4} = c^{2} − 2c + 1 + b^{4}. Temos que c e c − 1 são primos entre si e, como b | c − 1, b e c também são. Temos que c divide o produto dos inteiros \frac{c^{2}−2c+1+b^{4}}{b^{2}} e b^{2}, com c e b^{2} primos entre si, então c divide \frac{c^{2}−2c+1+b^{4}}{b^{2}} = \frac{(c−1)^{2}}{b^{2}} + b^{2} = a^{2} + b^{2}. Assim, ab + 1 divide a^{2} + b^{2}, ou seja, (a, b) é uma solução com b ≠ 0.

Lema 2. Se (b, c) é uma solução associada então (b, \frac{b^{4}+1}{c}) também é. Se (a, b) é uma solução com b ≠ 0 então (b, \frac{b^{3}−a}{ab+1}) também é uma solução.

Demonstração.

Como c | b^{4} + 1, (b, \frac{b^{4}+1}{c}) é um par de números naturais diferentes de zero. É fácil ver que \frac{b^{4}+1}{c} divide b^{4} + 1, logo só devemos mostrar que b divide \frac{b^{4}+1}{c} − 1. Como b | c − 1 então b | b^{4} + 1 − c. Daí b divide o produto dos inteiros \frac{b^{4}+1}{c} − 1 e c, e de b | c − 1 vem que b e c são relativamente primos e logo b divide \frac{b^{4}+1}{c} − 1. Isto demonstra a primeira parte.

Agora se (a, b) é uma solução com b ≠ 0, pomos c = ab + 1 e vemos que (b, c) é uma solução associada. Logo (b, \frac{b^{4}+1}{c}) também é. Daí se definimos:

a′ = \frac{\frac{b^{4}+1}{c} − 1}{b} = \frac{b^{4} + 1 − c}{bc} = \frac{b^{4} − ab}{b(ab + 1)} = \frac{b^{3} − a}{ab + 1},

vemos que (a′, b) (ou (b, a′)) é solução.

Definimos que o valor de uma solução (a, b) é o número \frac{a^{2}+b^{2}}{ab+1} . Note que se c = ab + 1 (supondo b ≠ 0) o valor fica:

\frac{c^{2} − 2c + 1 + b^{4}}{b^{2}c} = \frac{c − 2}{b^{2}} + \frac{b^{4} + 1}{b^{2}c}.

Temos o seguinte lema:

Lema 3. Se (a, b) é uma solução com b ≠ 0 então as soluções (a, b) e (b, \frac{b^{3}−a}{ab+1}) têm o mesmo valor.

Demonstração.

Em termos de soluções associadas temos os pares (b, c) e (b, \frac{b^{4}+1}{c}) (vide demonstração do lema 2), onde c = ab + 1. Devemos comparar os seguintes números:

\frac{c − 2}{b^{2}} + \frac{b^{4} + 1}{b^{2}c} e \frac{\frac{b^{4}+1}{c} − 2}{b^{2}} + \frac{b^{4} + 1}{b^{2} (\frac{b^{4}+1}{c})}.

Mas o segundo número fica:

\frac{b^{4} + 1 − 2c}{cb^{2}} + \frac{c}{b^{2}} = \frac{c^{2} − 2c + 1 + b^{4}}{cb^{2}} ,

o que coincide com o primeiro número.

Seja S o conjunto das soluções (a, b) com a ≠ 0. Defina φ: S → ℕ × ℕ por φ(a, b) = (\frac{a^{3}−b}{ab+1}, a). Aplicando o lema 2 (trocando a por b no enunciado) vemos que φ está bem definida e que φ(a, b) é sempre uma solução. Além do mais, pelo lema 3, φ(a, b) e (a, b) tem sempre o mesmo valor. Temos mais um lema:

Lema 4. Se (a, b) ∈ S é tal que a ≤ b então pondo (a′, b′) = φ(a, b) temos a′ < b′.

Demonstração.

Temos 0 < a ≤ b e 0 ≤ a^{2} − 1 < a^{2} + 1, donde a(a^{2} − 1) < b(a^{2} + 1). Abrindo os parênteses e desenvolvendo vem a^{3} −b < a^{2}b+a, e logo a^{3} −b < a(ab+1). Como ab+1 > 0 obtemos a desigualdade desejada.

Seja (a, b) uma solução. Devemos mostrar que seu valor é um quadrado perfeito. Trocando a por b se necessário, podemos supor a ≤ b. Definamos uma seqüência (a_{k}, b_{k}) indutivamente fazendo (a_{0}, b_{0}) = (a, b). Supondo (a_{k}, b_{k}) bem definido para algum k, se a_{k} = 0 interrompemos o processo (a seqüência fica finita). Se a_{k} ≠ 0 definimos (a_{k+1}, b_{k+1}) = φ(a_{k}, b_{k}).

Pelo lema 4, temos para todo k natural a_{k+1} < b_{k+1} = a_{k}. Assim a seqüência de números naturais a_{k} é estritamente decrescente, donde tem que ser finita, ou seja, existe um k com a_{k} = 0. Mas, pelo lema 3 o valor da solução é o mesmo para todos os termos da seqüência, donde o valor de (a, b) é igual ao valor de (a_{k}, b_{k}) = (0, b_{k}). Mas este último é b_{k}^{2}, um quadrado perfeito.

Questão 2. Existe uma função f: ℝ → ℝ tal que f(a+b) = f(a)+f(b) para todos a, b ∈ ℝ, mas que não é da forma f(x) = kx? Em caso afirmativo, descreva a função.

Mostraremos que f existe. Para isso considere em ℝ a relação de equivalência ∼ tal que x ∼ y ⟺ x − y ∈ ℚ. É fácil ver que temos uma relação de equivalência.

Seja C o conjunto das classes de equivalência. É fácil mostrar que é possível definir em C uma operação de soma e de multiplicação por escalares racionais fazendo:

[x] + [y] = [x + y], c[x] = [cx], ∀x, y ∈ ℝ, c ∈ ℚ,

onde [x] representa a classe de equivalência de x.

É fácil mostrar também que temos em C uma estrutura de espaço vetorial sobre ℚ. Como C e ℝ não são espaços vetoriais nulos (sobre ℚ), existe uma transformação ℚ-linear T: C → ℝ não nula (escolha uma base em C e defina T nessa base atribuindo valores não nulos). Denote por q : ℝ → C a função ℚ-linear dada por q(x) = [x].

Afirmo que f = T ∘ q: ℝ → ℝ é a função procurada. De fato, f é ℚ-linear, donde em particular f(x + y) = f(x) + f(y) para todos x, y ∈ ℝ. Suponha por absurdo que f seja da forma kx.

Temos k = f(1). Mas f(1) = T (q(1)) = T ([1]) = T (0) = 0, donde f seria identicamente nula. Isso é impossível pois q é sobrejetora e T é não nula (tome x ∈ C com T (x) ≠ 0 e y ∈ ℝ com q(y) = x. Daí f(y) ≠ 0).

Questão 3. É possível construir com régua e compasso um polígono regular de 5 lados? E de 17 lados? Em caso afirmativo, descreva a construção.

Ambas as construções são possíveis. Primeiramente escolha um segmento qualquer (que convencionaremos como sendo a unidade de medida) e use-o como raio para traçar uma circunferência. Se conseguirmos construir segmentos de comprimento cos 2π/5 e cos2π/17 fica fácil dividir a circunferência em 5 e 17 partes e portanto construir os polígonos.

Lembremos que as quatro operações aritméticas e a raiz quadrada são todas construtíveis com régua e compasso (a soma e a subtração são triviais, a multiplicação e a divisão vem da semelhança de triângulos e a raiz quadrada vem da altura do triângulo retângulo). Portanto precisamos apenas mostrar que os números cos 2π/5 e cos2π/17 podem ser obtidos dos números racionais por meio das quatro operações e da raiz quadrada.

Seja ξ = e^{2iπ/5} = cos 2π/5 + i sen 2π/5. Temos que 1=ξ^{0}, ξ^{1}, …, ξ^{4} são as raízes do polinômio x^{5} − 1, donde temos a fórmula:

1 + ξ + ξ^{2} + ξ^{3} + ξ^{4} = 0.

Usando essa fórmula e mais o fato que ξ^{5} = 1 fica fácil mostrar que os números:

a = ξ + ξ^{−1} = 2 cos 2π/5 e b = ξ^{2} + ξ^{−2}

são raízes da equação x^{2} + x − 1 = 0. Como a > 0, b < 0 vem:

a = \frac{−1 + \sqrt{5}}{2},

e portanto:

cos 2π/5 = \frac{−1 + \sqrt{5}}{4}.

Isto completa a construção do pentágono regular. Para a construção do polígono regular de 17 lados, defina η = e^{2iπ/17} = cos 2π/17 + i sen 2π/17. Por considerações análogas às do pentágono temos as fórmulas:

1 + η + η^{2} + η^{3} + ⋯ + η^{16} = 0, η^{17} = 1.

Defina os seguintes números:

\begin{aligned}a_{1} & = η + η^{2} + η^{4} + η^{8} + η^{−8} + η^{−4} + η^{−2} + η^{−1}, \\ b_{1} & = η^{3} + η^{5} + η^{6} + η^{7} + η^{−7} + η^{−6} + η^{−5} + η^{−3}, \\ a_{3} & = η + η^{4} + η^{−4} + η^{−1}, \\ b_{3} & = η^{2} + η^{8} + η^{−8} + η^{−2}, \\ a_{4} & = η^{3} + η^{5} + η^{−5} + η^{−3}, \\ b_{4} & = η^{6} + η^{7} + η^{−7} + η^{−6}, \\ a_{5} & = η + η^{−1}, b_{5} = η^{4} + η^{−4}, a_{2} = b_{1}, b_{2} = a_{1}. \end{aligned}

Como no caso do pentágono, utilizando as fórmulas dadas acima a respeito de η é fácil calcular que os pares (a_{1}, b_{1}), (a_{2}, b_{2}), …, (a_{5}, b_{5}) são respectivamente as soluções das seguintes equações do segundo grau:

\begin{matrix}(1) & x^{2} + x − 4 \\ (2) & x^{2} + x − 4 \\ (3) & x^{2} − a_{1}x − 1 \\ (4) & x^{2} − a_{2}x − 1 \\ (5) & x^{2} − a_{3}x + a_{4}. \end{matrix}

Utilizando aproximações numéricas dos a_{i} e dos b_{i} podemos distinguir entre as raízes de cada uma das equações acima e obter:

\begin{aligned}a_{1} & = \frac{−1 + \sqrt{17}}{2} \\ a_{2} & = \frac{−1 − \sqrt{17}}{2} \\ a_{3} & = \frac{a_{1} + \sqrt{a_{1}^{2} + 4}}{2} \\ a_{4} & = \frac{a_{2} + \sqrt{a_{2}^{2} + 4}}{2} \\ a_{5} & = \frac{a_{3} + \sqrt{a_{3}^{2} − 4a_{4}}}{2} . \end{aligned}

Como cos 2π/17 = a_{5}/2, isto completa a demonstração.

Questão 4. De quantas maneiras é possível colorir um tetraedro com n cores? E o icosaedro? (Dica: um icosaedro tem 20 faces triangulares. Não se esqueça de considerar as simetrias do poliedro).

Seja G o conjunto das simetrias do tetraedro (i.e., o conjunto das transformações do espaço Euclideano que preservam distância, orientação e que levam o tetraedro nele mesmo). Em G podemos considerar a operação de composição. Essa operação é associativa, tem elemento neutro e todo elemento admite um inverso. Essas propriedades caracterizam o que se chama um grupo.

Seja X o conjunto dos colorimentos do tetraedro (sem contar as simetrias), i.e., X é o conjunto das quádruplas de números entre 1 e n. Podemos definir uma aplicação ψ: G × X → X que leva cada par (g, x) ∈ G × X no colorimento que se obtém quando usa-se a simetria g do tetraedro para permutar as cores do colorimento x. Esta aplicação satisfaz as propriedades:

ψ(g_{1}, ψ(g_{2}, x)) = ψ(g_{1} ∘ g_{2}, x) e ψ(e, x) = x,

quaisquer que sejam g_{1}, g_{2} ∈ G, x ∈ X, onde e é o elemento neutro do grupo G. Essas propriedades caracterizam o que se chama uma ação de um grupo G num conjunto X.

Define-se uma relação ∼ em X fazendo x ∼ y quando existe um elemento g ∈ G com ψ(g, x) = y. É fácil mostrar que temos uma relação de equivalência. As classes de equivalência são chamadas órbitas. O número de órbitas é exatamente o número de colorimentos que procuramos. Vale a seguinte fórmula usual para o número de órbitas:

\frac{∑_{g∈G} |X_{g}|}{|G|},

onde X_{g} é o conjunto dos elementos x ∈ X tais que ψ(g, x) = x.

O grupo G tem 12 elementos, sendo que 1 é o elemento neutro, 8 fixam exatamente uma face do tetraedro e 3 não fixam face nenhuma. O elemento neutro fixa todos os n^{4} elementos de X e os outros 11 fixam n^{2} elementos de X. Aplicando a fórmula para o número de órbitas vemos que o número de colorimentos do tetraedro com n cores (contando as simetrias) é:

\frac{11n^{2} + n^{4}}{12} .

Passemos ao caso do icosaedro. A teoria de ação de grupo é a mesma, precisamos apenas analisar a estrutura do grupo G de simetrias do icosaedro e sua ação sobre o conjunto X dos colorimentos (sem simetrias).

Neste caso o grupo G tem 60 elementos. Podemos numerar as faces do icosaedro e escrever explicitamente os elementos desse grupo como produto de ciclos disjuntos. A conclusão final é que temos 24 elementos que fixam n^{4} colorimentos, 20 elementos que fixam n^{8} colorimentos, 15 elementos que fixam n^{10} colorimentos e 1 elemento que fixa n^{20} colorimentos. Usando a fórmula para o número de órbitas vemos que o número de colorimentos do icosaedro com n cores (contando as simetrias) é:

\frac{24n^{4} + 20n^{8} + 15n^{10} + n^{20}}{60} .

Isto completa a questão.

Questão 5. Mostre que existe uma potência de 2 que possui 5 algarismos 1 no início da sua representação decimal.

Seja x um número real não-negativo. Denotaremos por [x] a parte inteira de x (i.e., o maior inteiro menor ou igual a x) e por {x} a parte fracionária de x (i.e., x − [x]). Temos os seguintes lemas:

Lema 1. Seja x ∈ ℝ, x ≥ 0. Se x não é inteiro então existe um inteiro positivo K tal que {Kx} ≥ 1/2.

Demonstração.

Considere a seqüência (2^{n}{x})_{n∈ℕ}. Como x não é inteiro, {x} é positivo e logo a seqüência não é limitada. Em particular ela tem termos maiores que 1. Seja n o maior índice tal que 2^{n}{x} < 1. Basta tomar então K = 2^{n}.

Lema 2. Seja x ∈ ℝ, x ≥ 0. Então dado ϵ > 0 existe um inteiro positivo k com {kx} < ϵ.

Demonstração.

Basta mostrar que existe um inteiro positivo k com {kx} ≤ {x}/2. Podemos supor sem perda de generalidade que 0 ≤ x < 1 (pois podemos trocar x por {x}). Como o caso x = 0 é trivial, supomos 0 < x < 1.

Se 1/x é inteiro, basta tomar k = 1/x e daí {kx} = 0, o que resolve o problema. Caso contrário, podemos aplicar o lema 1 para encontrar um inteiro positivo K com {K/x} ≥ 1/2. Tome k = [K/x] + 1. Temos:

k = \frac{K}{x} + 1 − \{\frac{K}{x} \} ,

e portanto:

kx = K + x − \{\frac{K}{x} \} x,

onde:

x − \{\frac{K}{x} \} x = x (1 − \{\frac{K}{x} \}) ≤ \frac{x}{2}.

Isso mostra que a expressão acima é a parte fracionária de kx e que esta é menor do que x/2.

Lema 3. Seja x um número irracional não-negativo. Sejam dados f ∈ [0, 1), ϵ > 0 e k_{0} inteiro positivo. Então existe um inteiro k ≥ k_{0} tal que {kx} dista de f menos do que ϵ.

Demonstração.

Primeiro use o lema 2 para escolher k_{1} inteiro positivo tal que {k_{1}x} < ϵ. Agora considere a seqüência (n{k_{1}x})_{n∈ℕ}. Como x é irracional, k_{1}x não é inteiro e logo essa seqüência é ilimitada. Considere o primeiro n tal que n{k_{1}x} ultrapassa f. Então tome k = nk_{1} e é fácil ver que {kx} dista de f menos do que ϵ (na realidade, deve-se escolher ϵ < 1 − f para garantir que n{k_{1}x} não passa de 1).

Demonstramos o lema a menos da exigência k ≥ k_{0}. Agora basta aplicar a parte já demonstrada do lema para o número irracional k_{0}x e obter k′ inteiro positivo tal que {k′k_{0}x} dista de f menos do que ϵ. Daí basta tomar k = k′k_{0}.

Utilizaremos o lema 3 para x = log 2 (o logarítmo é sempre na base 10). Precisamos mostrar então que x = log 2 é irracional. De fato, se log 2 fosse p/q então teríamos 2^{p} = 10^{q}, onde o lado direito é múltiplo de 5 e o esquerdo não é, uma contradição.

Escolha então um inteiro k ≥ 4/ log 2 de modo que:

log 1, 1111 ≤ {k log 2} < log 1, 1112.

Agora seja n = [k log 2] − 4. Como k ≥ 4/ log 2, k log 2 ≥ 4, donde n ≥ 0. Temos:

n + 4 + log 1, 1111 ≤ k log 2 < n + 4 + log 1, 1112 ⇒ 11111 · 10^{n} ≤ 2^{k} < 11112 · 10^{n},

ou seja, 2^{k} tem 5 algarismos 1 no início da sua representação decimal.