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:
- 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.
- Prove que existe um conjunto de $$100$$ números naturais consecutivos de tal maneira que no mesmo conjunto haja exatamente:
- $$7$$ primos;
- $$13$$ primos;
- $$n$$ primos para $$n$$ inteiro e $$\le 20$$.
- (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.
- (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.
- (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.