Matemática - ideia 06

Escrito por Brendon Borck:

Conhecida popularmente como continuidade, mas pelos meios de pesquisa especificamente como continuidade discreta, esse importante artifício em combinatória remete a uma maneira de transcrevermos ao papel aquilo que nossa intuição já enxerga como verdade.

Se saímos de um estado $A$ e chegamos a um estado $B$ de forma que há poucas possibilidades ou uma única possibilidade de caminho entre ambos estados, então se provarmos que um estado $C$ está sempre no meio desse(s) caminho(s) sem sabermos ainda onde, não há outro jeito: precisamos atingir o estado $C$ em algum momento e na maioria dos problemas onde essa técnica é utilizada essa é a resposta que o problema pede. Nos resta identificar dois estados $A$ e $B$ de óbvia passagem e que podem ser definidos por nós.

Observação: é necessário provar no problema que a continuidade de fato ocorre, ou seja, que o caminho é discreto e atinge em algum momento o estado que queremos.

Para elucidar esse conceito, seguem dois exemplo abaixo.

Exemplos resolvidos:

1. Se numa linha temos $20$ pontos, $10$ pintados de azul e $10$ de verde, sendo que numa das extremidades existem $5$ pontos azuis e na outra $5$ verdes. Prove que existe um conjunto de $5$ pontos consecutivos na linha com $3$ pontos azuis e $2$ verdes.

Solução:

Sem perda de generalidade suponha que na extremidade da esquerda há $5$ pontos azuis, note que se variarmos esse conjunto (tirando o ponto mais à esquerda e adicionando o próximo ponto à direita) em algum momento vamos atingir a outra extremidade com $5$ pontos verdes. A cada vez que variamos o conjunto "um passo para direita" nós mantemos quatro pontos, retiramos um e adicionamos outro. Se adicionarmos um ponto da mesma cor que o retirado então a configuração de cores não muda, se a cor for diferente a quantidade da cor adicionada sobe uma unidade e a da retirada desce uma, a variação na quantidade de cores acontece de um em um. No começo há $5$ azuis e $0$ verdes e no final há $0$ azuis e $5$ verdes, logo em algum momento esse conjunto vai ter configuração: $3$ pontos azuis e $2$ verdes.

2. (OBM) Vamos chamar de garboso o número que possui um múltiplo cujas quatro primeiras casas de sua representação decimal são $2008$. Por exemplo, $7$ é garboso, pois $200858$ é múltiplo de $7$ e começa com $2008$. Observe que $200858 = 28694 \times 7$.

(a) Mostre que $17$ é garboso.

(b) Mostre que todos os inteiros positivos são garbosos.

Solução:

(a) $200804 = 17 \times 11812$

(b) Note que qualquer número inteiro é menor que alguma potência $10^k$ para algum $k$, tome essa potência como referência, então certamente há um múltiplo de um inteiro positivo $n$ entre $2008 \times 10^k$ e $2009 \times 10^k - 1 = 20089999...99$ já que os múltiplos de um número $n$ se repetem na reta dos inteiros de $n$ em $n$ e nesse intervalo específico $n < 10^k$, logo não tem jeito: há um múltiplo no intervalo e portanto um número que começa com $2008$.

Problemas:

1. Há $2000$ bolinhas enfileiradas numa linha finita. Sabemos que uma extremidade há $200$ bolinhas vermelhas consecutivas e na outra há $150$ bolinhas azuis consecutivas. Prove que existe um grupo de $100$ bolinhas consecutivas nessa linha de tal modo que há exatamente $50$ vermelhas e $50$ azuis.
2. Prove que existe um conjunto de $100$ números naturais consecutivos de tal maneira que no mesmo conjunto haja exatamente:
   1. $7$ primos;
   2. $13$ primos;
   3. $n$ primos para $n$ inteiro e $\le 20$.
3. (OBM) Sobre uma reta há um conjunto $S$ de $6n$ pontos. Destes, $4n$ são escolhidos ao acaso e pintados de azul; os $2n$ demais são pintados de verde. Prove que existe um segmento que contém exatamente $3n$ pontos de $S$, sendo $2n$ pintados de azul e n pintados de verde.
4. (EUA) Se $n$ é um inteiro maior do que $1$ e são dados $2n$ pontos no plano de modo que entre eles não haja três colineares. Dos $2n$ pontos, $n$ são coloridos de azul e os demais  são coloridos de vermelho. Uma reta do plano é dita balanceada quando passa por um ponto azul e um ponto vermelho e, em cada lado da reta, a quantidade de pontos azuis e vermelhos são iguais. Prove que existem pelo menos duas retas balanceadas.
5. (OBM) Considere todos os círculos cujas circunferências passam por três vértices consecutivos de um polígono convexo. Prove que um desses círculos contém todo o polígono.