Alguns padrões e estratégias para resolver problemas matemáticos

Conteúdo

• 1. Invariantes
• 2. Elementos extremos
• 3. Casos menores
• 4. Problemas correlatos

Originalmente eu havia postado esse conteúdo aqui:

Resposta de Angelo Santos da Cruz para Existe alguma maneira conhecida de se construir novas provas ou de fazer demonstrações em matemática sem que seja por métodos algébricos, geométricos, computacionais ou por meio de lógica proposicional? em Matemática ao Extremo 

Existem algumas estratégias de natureza heurística usadas para abordar vários tipos de problemas como, por exemplo, considerar os pontos extremos de alguma coisa, procurar os "invariantes", ou seja, aquilo que não muda quando alguma operação autorizada é realizada ou resolver casos menores ou degenerados para entender qual é a lógica do problema. As soluções sempre usam métodos algébricos, geométricos ou apenas a Lógica, mas essas estratégias são importantes para se saber qual rumo tomar para resolver certos problemas e eu gostaria de compartilhá-las aqui.
Vou citar alguns exemplos ilustrativos.

1. Invariantes

Uma das principais estratégias para resolução de problemas de olimpíadas é a procura por invariantes. O fundamento do Princípio da Invariância é simples: busca pelo que se mantém constante quando uma operação permitida é realizada. Entre as principais formas de invariantes destacam-se três, que serão apresentadas a seguir através de exemplos resolvidos.

Exemplo 1:

Começando com o conjunto {3, 4, 12}, é permitido apagar dois números a e b e escrever em seus lugares (0,6.a – 0,8.b) e (0,8.a + 0,6.b). É possível chegar ao conjunto {4, 6, 12}?

Resolução: Repare que ${(0,6a – 0,8b)}^{2} + {(0,8a + 0,6b)}^{2} = a^2 + b^2$ , implicando que a soma dos quadrados dos números dos conjuntos obtidos é invariante. Como ${3}^{2} + {4}^{2} + {12}^{2} = {13}^{2}$ e ${4}^{2} + {6}^{2} + {12}^{2} = {14}^{2}$ então não é possível chegar ao conjunto ${4, 6, 12}$.

Exemplo 2:
Em cada um dos 10 degraus de uma escada existe uma rã. Cada rã pode, de um pulo, colocar-se em outro degrau, mas quando uma rã faz isso, ao mesmo tempo, uma outra rã pulará a mesma quantidade de degraus em sentido contrário: uma sobe e outra desce. Conseguirão as rãs colocar-se todas juntas num mesmo degrau?

Resolução: Numeremos os degraus de 1 a 10 e associemos a cada rã o número do degrau que ocupam. O somatório inicial destes valores é S = 1 + 2 + … + 10 = 55. Perceba agora que este somatório é invariante, pois quando uma rã sobe uma certa quantidade x de degraus, temos outra rã que desce x, fazendo com que a soma das numerações destas duas rãs não se altere. Caso todas as rãs ocupem um mesmo degrau (digamos y), então todas as suas numerações são iguais a deste degrau, ou seja, teremos 10y = 55, que não possui solução inteira. Deste modo, é impossível que todas as rãs ocupem um mesmo degrau.
Fonte: Revista Eureka!

2. Elementos extremos

Considere uma fileira de estudantes ordenada em forma decrescente segundo a altura. A maioria deles tem dois vizinhos. Dois "elementos extremos", o mais alto e o mais baixo, tem somente um vizinho, porém estes dois elementos extremos possuem outras propriedades muito úteis. Por exemplo, quando contamos os estudantes na fileira, a melhor maneira é começar com um destes elementos extremos. Em matemática, algumas vezes trabalhamos com conjuntos cujos elementos parecem ser equivalentes e cujas propriedades conhecidas são poucas. Uma estratégia poderosíssima em tais casos é considerar o elemento, ou os elementos, que de alguma forma são elementos extremos. Por exemplo, quando consideramos um conjunto infinito de números naturais, o elemento extremo é seu elemento menor. Para um conjunto finito de números reais os elementos extremos são o máximo e o mínimo do conjunto.
Em muitos casos o elemento extremo é atrativo devido a que suas propriedades adicionais nos permitem obter concluir sobre o mesmo elemento, ou sobre o do conjunto como um todo. Por exemplo, em um triângulo o lado maior se opõe ao ângulo maior e vice-versa.
Fonte: Revista Eureka!

Exemplo 1:

Encontre rapidamente a soma dos números inteiros e positivos de 1 a 100.
Considerando-se os elementos extremos, podemos observar que 1+100 = 2+99 = 3+98=… = 50+51.

Como a ordem das parcelas não altera a soma e existem 50 parcelas iguais a 101, basta fazer $101 \times 50 = 5050$, que é a resposta procurada.

Exemplo 2:

Carlinhos pensa num número ímpar positivo menor do que 10. Pedrinho se dispõe a descobrir que número é esse fazendo a seguinte pergunta, quantas vezes forem necessárias: “O número que você pensou é maior, menor ou igual a x ? ”. Note que x é um número que Pedrinho escolhe.
Quantas perguntas desse tipo Pedrinho poderá ter que fazer até descobrir o número pensado por Carlinhos?

Suponha que o número seja 9 e considere, sem perda de generalidade, o número 5, que é a metade de 10. A primeira pergunta será: “O número que você pensou é maior, menor ou igual a 5? ”

Daí, você saberá que o número escolhido é maior que 5. Agora considere o número 8, que é 5 acrescentado ao maior inteiro maior que 2,5, que é a metade de 5. A segunda pergunta será: “O número que você pensou é maior, menor ou igual a 8? ”
Com a terceira pergunta, Pedrinho descobre o número escolhido.

Em geral, se Carlinhos pensa num número ímpar positivo menor do que n, então sendo 2^{m} a maior potência de 2 menor que n, o número de perguntas necessárias para descobrir o número é m. Por exemplo, se Carlinhos pensa num número ímpar positivo menor do que 1000, serão necessárias 9 perguntas, pois ${2}^{9} = 512 <1000$.

3. Casos menores

Exemplo 1:

(OBM 2004) Dizemos que um número natural é composto quando pode ser escrito como produto de dois números naturais maiores que 1. Assim, por exemplo, 91 é composto porque podemos escrever $91 = 7 \times 13$. Mostre que o número

$\displaystyle 2^{\left(2^{2004} + 2\right)} + 1$

é composto.

Vamos considerar os último algarismos das primeiras potências de 2. As primeiras potências de 2 são os números 2, 4, 8, 16, 32, 64, 128, 256, 512… Veja que os últimos algarismos se repetem nesse ciclo: 2, 4, 8, 6, 2…

Se n é múltiplo de 4, então, ${2}^{n}$ termina em $6$. Se $n$ deixa resto $2$ ao ser dividido por $4$, então ${2}^{n}$ termina em $4$. Como $2004 = 501 \times 4$, o último algarismo de $2^{2004}$ é $6$ e como $2^{2004}$ é múltiplo de $4$, o número $2^{\left(2^{2004} + 2\right)}$ termina em $4$ e $2^{\left(2^{2004} + 2\right)} + 1$ termina em $5$. Qualquer número que termina em $5$ é múltiplo de $5$ e, portanto, é composto.

Exemplo 2:

São desenhadas n circunferências em um plano. Determine o número máximo de áreas distintas não subdivididas que podem ser formadas pelas intersecções dessas circunferências? (Dica: Pense nos diagramas de Venn).

A resposta é $2^{n} - 1$.

Por exemplo, tomando $n = 2$ circunferências, temos o seguinte esquema:

Observe que temos 3 regiões não interceptadas. Podemos intuir que cada sub-região é uma intersecção de pelo menos duas das circunferências. O total de possibilidades é a soma de todas as intersecções possíveis, (a soma das combinações de n elementos tomados de 1 a 1, depois de 2 a 2 e assim por diante), que é igual a

$\displaystyle \sum_{k=1}^n{n \choose k}$

Pelo Teorema da soma de uma linha do Triângulo de Pascal temos que $\displaystyle \sum_{k=0}^n{n \choose k} = 2^n$

Como $\displaystyle {n \choose 0} = 1$, temos que o número de intersecções possíveis é $2^n - 1$

Por exemplo, para $n = 3$ circunferências temos $2^3 - 1 = 7$ intersecções. De fato:

Há outra forma de se chegar a este resultado, por recorrência. Seja $A_{n}$ o número de regiões distintas e não subdivididas formadas pelas intersecções de n circunferências. Cada nova circunferência intercepta cada uma dessas regiões, dobrando o seu número e acrescenta uma nova região, que não é interceptada. Portanto, $A_{n+1} = 2A_{n} + 1$.

Resolvendo-se essa recorrência, obtemos $A_{n} = 2^{n} - 1$.

De fato:

$A_{n + 1} = 2A_{n} + 1 = 2(2^{n} - 1) + 1 = 2^{n + 1} - 2 + 1 = 2^{n + 1} - 1$.

Veja como seriam todas as possibilidades de intersecções para $n = 4$. Neste caso temos que o número máximo de intersecções é $2^4 - 1 = 15$ intersecções. Aqui elas assumem a forma elíptica, mas devemos lembrar que a circunferência é um caso particular de elipse. 

A elipse tem 2 focos, que no caso da circunferência são sobrepostos.

 

4. Problemas correlatos

Exemplo 1:

Prove que não existe uma potência inteira de 2 que seja o resultado de uma reordenação dos algarismos de outra potência de 2?

Considerando que zeros à esquerda não contam, uma potência de 2 pode ser multiplicada por 2 ou 4 ou, no máximo, 8 para formar outra potência de 2 com a mesma quantidade de algarismos.

Um número da forma $10^{n}$ ao ser multiplicado por um número maior que 10 resulta em um número com um algarismo a mais. Logo, uma potência de 2 pode ser multiplicada por, no máximo, 8 para ter outra potência de 2 com a mesma quantidade de algarismos.

Um número formado pela reordenação dos algarismos de outro deixa o mesmo resto que o primeiro na divisão por 9.

Considerando-se um número n, temos que 2n ou 4n ou 8n não deixam o mesmo resto que n na divisão por 9. Isso é possível verificar analisando-se cada um dos possíveis restos da divisão de algum número por 9 (os algarismos de 1 a 9).

Vamos considerar outra situação que envolve a soma dos algarismos de um número inteiro e positivo. Essa soma sempre deixa o mesmo resto na divisão por 9 que o próprio número. Por exemplo, 512 deixa resto 8 na divisão por 9 e a soma dos seus algarismos é 5 + 1 + 2 = 8.

Considerando que zeros à esquerda não contam, uma potência de 2 pode ser multiplicada por 2 ou 4 ou, no máximo, 8 para formar outra potência de 2 com a mesma quantidade de algarismos.

Um número da forma ${10}^{n}$ ao ser multiplicado por um número maior que 10 resulta em um número com um algarismo a mais. Logo, uma potência de 2 pode ser multiplicada por, no máximo, 8 para ter outra potência de 2 com a mesma quantidade de algarismos.

Um número formado pela reordenação dos algarismos de outro deixa o mesmo resto que o primeiro na divisão por 9.

Considerando-se um número n, temos que $2n$ ou $4n$ ou $8n$ não deixam o mesmo resto que n na divisão por 9. Isso é possível verificar analisando-se cada um dos possíveis restos da divisão de algum número por 9 (os algarismos de 1 a 9).

Exemplo 2:

Encontre todas as sequências de números inteiros, positivos consecutivos cujas somas dos seus termos seja igual a 100.

Vamos considerar outra situação que envolve a soma dos termos de sequências de números. A fórmula da soma dos termos de uma progressão aritmética é

$S_n = \displaystyle \frac{({a}_{1} + {a}_{n})n}{2}$

Então, como $a_n = a_1 + (n - 1)r$ e como os números são consecutivos, temos que $r=1$.

Então $a_n = a_1 + (n - 1)$. Substituindo-se isso em $\frac{({a}_{1} + {a}_{n})n}{2}$ e igualando a $100$, temos que:

$(2{a}_{1} + n - 1)n = 200$

$\displaystyle n = \frac{200}{(2{a}_{1} + n - 1)}$

Como $n$ e $(2{a}_{1} + n - 1)$ devem ser um números inteiros e positivos, então $n$ deve ser um divisor inteiro de $200$. Os divisores de $200$ são $d_{1} = 1$, $d_{2} = 2$, $d_{3} = 4$, $d_{4} = 5$, $d_{5} = 8$, $d_{6} = 10$, $d_{7} = 20$, $d_{8} = 25$, $d_{9} = 40$, $d_{1} = 50$, $d_{11} = 100$ e $d_{12} = 200$.

Sendo $1 \leq k \leq 12$, temos que:

$\displaystyle a_1 = \frac{\frac{200}{d_k} + 1 - n}{2}$

$\displaystyle a_1 = \frac{\frac{200}{d_k} + 1 - {d}_{k}}{2}$

Igualando-se $\frac{\frac{200}{{d}_{k}} + 1 - {d}_{k}}{2}$ a cada um dos divisores de $200$, obtemos os possíveis valores de $a_1$ e, caso sejam inteiros e positivos encontramos as sequências procuradas, que são estas:

Por exemplo, se $n=1$, então $(2{a}_{1} + {d}_{1} - 1) = \frac{200}{1} = 200$.

$(2{a}_{1} + {d}_{1} - 1) = 200$

$(2{a}_{1} + 1 - 1) = 200$

$\displaystyle \boxed{a_1 = 100}$

Se $n = 1$, então $a_1 = 100$ e a sequência é $(100)$.

Se $n = 5$, então $a_1 = 18$ e a sequência é $(18, 19, 20, 21, 22)$.

Se $n = 8$, então $a_1 = 9$ e a sequência é $(9, 10, 11, 12, 13, 14, 15, 16)$.

Existem muitas outras estratégias desse tipo, mas as principais que eu conheço são essas.