FANDOM


Existem vários problemas em que aparece combinatória e geometria.

Uma das estratégias é transformar problemas de combinatória em problemas de geometria.

Exemplo (OBM 1999 - 3ª Fase - Nível 2)Editar

Um reino é formado por dez cidades. Um cidadão muito chato foi exilado da cidade $ A $ para a cidade $ B $, que é a cidade do reino mais longe de $ A $. Após um tempo, ele foi expulso da cidade $ B $ para a cidade $ C $ do reino mais longe de $ B $. Sabe-se que a cidade $ C $ não é a mesma cidade $ A $. Se ele continuar sendo exilado dessa maneira, é possível que ele retorne à cidade $ A $?

Solução: Vamos nomear as outras cidades: $ D $, $ E $, $ F $, $ G $, $ H $, $ I $ e $ J $. Como $ C $ é a cidade mais distante de $ C $, segue que $ AB< BC $. Se repetirmos o mesmo raciocínio para outras cidades, teremos

$ AB<BC<CD<\dots<HI< IJ. $

Para podermos fechar o ciclo, precisamos que $ A $ seja a cidade mais longe de $ J $. Porém, como $ B $ é a cidade mais longe de $ A $ e pela desigualdade anterior

$ AJ< AB < IJ. $

Contradição. Logo, é impossível que as cidades cumpram as condições do enunciado.

Exemplo (Putnam 1956)Editar

Considere um conjunto de $ 2n $ pontos no espaço (com $ n>1 $). Suponha que eles estão unidos por pelo menos $ n^2+1 $ segmentos. Mostre que pelo menos um triângulo é formado. Mostre também que para cada $ n $ é possível ter $ 2n $ pontos unidos por $ n^2 $ segmentos sem que um triângulo seja formado.

Solução: Vamos usar indução em $ n $. Comecemos com $ n=2 $. Suponha que ligamos $ 2.2=4 $ pontos por $ 2^2+1=5 $ segmentos. No máximo, podemos ligar $ 4 $ pontos por $ 6 $ segmentos. Então, se traçarmos $ 5 $ segmentos, existem $ 2 $ pontos que não estão ligados (que chamaremos de $ A $ e $ B $). Assim basta pegarmos um destes e os outros dois, para termos três pontos e todos eles ligados entre si, ou seja, um triângulo.

Considere agora que a afirmação seja válida para $ n-1 $ (com $ n>2 $), ou seja, quaisquer $ 2(n-1)=2n-2 $ pontos ligados por $ (n-1)^2+1=n^2-2n+2 $ segmentos tem um triângulo formado. Provaremos que o resultado vale para $ n $.

Suponha que temos $ 2n $ pontos ligados por $ n^2+1 $ segmentos. Tome dois pontos, digamos $ P $ e $ Q $, que estão ligados por um segmento. Nenhum dos outros pontos está ligado a $ P $ e $ Q $ ao mesmo tempo, pois se estivesse, teríamos um triângulo formado.

Se retirarmos $ P $ e $ Q $ ao mesmo tempo (junto com os segmentos que se juntam a eles), eliminaremos, no máximo, $ 2(n-1)+1=2n-1 $ segmentos (pois $ P $ e $ Q $ estão ligados e cada um dos outros pontos está ligado com, no máximo, um deles).

Então, sobrarão $ 2n-2 $ pontos e $ n^2+1-(2n-1)=n^2-2n+2 $ segmentos e, por hipótese de indução, existe um triângulo formado.

Resta a segunda parte do exercício: aqui basta dividirmos os $ 2n $ pontos em dois conjuntos disjuntos de $ n $ pontos cada e ligarmos cada ponto de um conjunto com todos os outros pontos do outro. Com isso, teremos $ n^2 $ segmentos e nenhum triângulo formado.

Exemplo (Cone Sul 1998) Editar

O Prefeito de uma cidade deseja estabelecer um sistema de transportes com pelo menos uma linha de ônibus, no qual:

(i) cada linha passe exatamente por três paradas;

(ii) cada duas linhas distintas tenham exatamente uma parada em comum;

(iii) para cada duas paradas de ônibus distintas exista exatamente uma linha que passe por ambas.

Determine o número de paradas de ônibus da cidade.

Solução: Vamos transformar este problema em um de geometria. Para isto, representaremos as linhas por retas e as paradas por pontos. Desta forma, uma linha passa por uma parada, se e somente se, a reta passa pelo ponto correspondente.

Agora, podemos reescrever o enunciado em termos de geometria:

(i) cada reta passe exatamente por três pontos;

(ii) cada duas retas distintas tenham exatamente um ponto em comum;

(iii) para cada duas retas distintas exista exatamente uma reta que passe por ambas.

Vamos desenhar as possibilidades. Observe que precisamos de pelo menos três pontos. Além disso, note que uma reta que passa pelos pontos, que chamaremos de $ A,B $ e $ C $, cumpre as condições do enunciado.

ConeSul1998q6

Existe algum caso com mais pontos? Suponha que exista um ponto $ D $. Por (i), ele deve estar fora da reta. Por $ A $ e $ D $ passa uma outra reta que deve ser diferente daquela que passa por $ A,B $ e $ C $ (elas são diferentes, pois $ D $ não pode pertencer a esta última reta).

Além disso, por (i), existe um terceiro ponto nesta reta que passa por $ A $ e $ D $. Chamaremos ele de $ E $. Analogamente, conseguimos construir pontos $ F $ e $ G $ pertencentes às retas $ BD $ e $ CD $, respectivamente.

ConeSul1998q61
Acabemos de provar que se tivermos mais de $ 3 $ pontos, então precisamos de pelo menos $ 7 $. Dá para colocar o oitavo ponto? Suponha que sim, conseguimos colocar um ponto $ H $.

Sabemos que duas retas distintas tem exatamente um ponto em comum. Então a reta $ DH $ deve cortar a reta que passa por $ A,B $ e $ C $ em algum destes três pontos. Mas se isso acontecesse, alguma das retas $ AD $, $ BD $ ou $ CD $ teria dois pontos de intersecção com $ DH $, o que contradiz (ii). Logo, o número máximo de pontos é $ 7 $.

Existe alguma solução com exatamente $ 7 $ pontos? Sim:

ConeSul1998q62

Repare que a linha que passa por $ B,E $ e $ G $ é circular.

Portanto, a cidade só pode possuir $ 3 $ ou $ 7 $ paradas.

Exemplo (Cone Sul 2001) Editar

Três triângulos acutângulos estão inscritos em uma mesma circunferência, de modo que seus vértices são nove pontos distintos. Demonstre que se pode escolher um vértice de cada triângulo de maneira que os três pontos escolhidos determinem um triângulo cujos ângulos sejam menores ou iguais a $ 90^{\circ} $.

Solução: Sejam $ A_1A_2A_3 $, $ B_1B_2B_3 $ e $ C_1C_2C_3 $ os triângulos. Vamos pensar em termos de arcos. Para que um triângulo $ XYZ $ inscrito na circunferência é acutângulo, precisamos que os arcos $ \widehat{XY} $, $ \widehat{YZ} $ e $ \widehat{ZX} $ tenham medidas menores que $ 180^{\circ} $.

E como fazer isto? Uma estratégia é escrever diâmetros e colocar cada dois vértices da figura no "mesmo lado" de um diâmetro. Vamos começar traçando um diâmetro então. Tome o ponto $ A_1 $ e considere $ A $ de tal forma que $ A_1A $ seja um diâmetro. Vejamos quais são os outros dois pontos dos outros triângulos que podemos tomar para formar um triângulo acutângulo.

Podemos supor, sem perda de generalidade, que dentre os pontos $ B_1,B_2,B_3,C_1,C_2 $ e $ C_3 $, o mais próximo de $ A $ é $ B_1 $. Observe que $ \widehat{A_1B_1}<90^{\circ} $.

Seria legal se conseguíssemos um ponto do triângulo $ C_1C_2C_3 $ para montarmos o triângulo acutângulo desejado. Observe que este ponto não pode ficar do "mesmo lado" do diâmetro $ A_1A $ que o ponto $ B_1 $. Mas realmente existe algum ponto neste "outro lado"?

Sim: note que os três pontos não podem ficar do "mesmo lado" do diâmetro $ A_1A $, pois neste caso algum dos arcos terá medida maior que $ 180^{\circ} $ e assim $ C_1C_2C_3 $ não será um triângulo acutângulo.

Qualquer ponto $ C_j $ neste arco faz com que $ \widehat{C_jA_1}<90^{\circ} $, mas nada garante que $ \widehat{CjB_1}<90^{\circ} $. Seria legal se cercássemos $ B_1 $ e $ C_j $ no "mesmo lado" de um diâmetro.

Dentre os pontos $ C_1,C_2 $ e $ C_3 $, suponha, sem perda de generalidade, que o ponto no arco $ \widehat{AA_1} $ que contém $ B_1 $ mais próximo de $ A $ é $ C_1 $. Observe que $ B_1 $ deve estar entre $ C_1 $ e $ A $, pois $ B_1 $ é o ponto dentre $ B_1,B_2,B_3,C_1,C_2 $ e $ C_3 $ mais próximo de $ A $. Qual a vantagem de construirmos deste jeito? É que $ C_2 $ e $ C_3 $ não estão no arco $ \widehat{C_1A} $ que contém $ B_1 $.

ConeSul2001q3

Considere o diâmetro $ CC_1 $. Observe que existe um ponto $ C_i $ no mesmo lado do arco $ CC_1 $ que o ponto $ B_1 $. Basta verificarmos que se os pontos $ C_2 $ e $ C_3 $ ficassem do outro lado, o triângulo $ C_1C_2C_3 $ não seria acutângulo.

Como $ C_1 $ é o mais próximo dentre $ C_1,C_2 $ e $ C_3 $ de $ A $ que está no arco $ \widehat{AA_1} $ que contém $ B_1 $, segue que $ C_i $ está no arco menor $ \widehat{AC} $. Desta forma, $ \widehat{A_1C_1}<90^{\circ} $ e $ \widehat{B_1C_i}<90^{\circ} $. Portanto, o triângulo $ A_1B_1C_i $ é acutângulo.

Exemplo (OBM 2013 - 3ª Fase - Nível 2) Editar

Considere um inteiro positivo $ n $ e dois pontos $ A $ e $ B $ em um plano. Partindo do ponto $ A $, são traçadas $ n $ semirretas e partindo do ponto $ B $, são traçadas $ n $ semirretas de modo que todas elas estejam no mesmo semiplano definido pela reta $ AB $ e que os ângulos formados pelas $ 2n $ semirretas com o segmento $ AB $ sejam todos agudos. Defina circunferências passando pelos pontos $ A $, $ B $ e cada ponto de encontro entre as semirretas. Qual a menor quantidade de circunferências distintas que podem ser definidas por essa construção?

OBM2013q6n2

Solução: O principal problema aqui é: como saber se dois pontos formam com $ A $ e $ B $ circunferências iguais ou distintas? Vamos começar explorando quando dois pontos $ C $ e $ D $ estão sobre a mesma circunferência. Façamos isso em termos do ângulos formados pelas semirretas. Observe que $ A $, $ B $, $ C $ e $ D $ pertencem a mesma circunferência se, e somente se,

$ \angle ADB = \angle ACB \Leftrightarrow \angle DAB + \angle DBA = \angle CBA + \angle CAB. $

E quem garante que todas as semirretas se encontram no mesmo semiplano? Isto vem do fato de que todos os ângulos são agudos. Agora sim, podemos marcar os ângulos e ver quando eles satisfazem a igualdade anterior.

Chamemos as medidas dos ângulos entre as semirretas saindo de $ A $ e $ AB $ de $ \alpha_1, \alpha_2, \dots, \alpha_n $ de forma que $ \alpha_1>\alpha_2> \dots > \alpha_n $.

Da mesma forma, as medidas dos ângulos entre as semirretas saindo de $ B $ e $ AB $ serão $ \beta_1, \beta_2, \dots, \beta_n $ de forma que $ \beta_1>\beta_2> \dots > \beta_n $.

Cada medida diferente para $ \alpha_i+\beta_j $ nos dá uma circunferência distinta. Se determinarmos a quantidade mínima de valores que esta soma pode assumir, também conseguiremos a quantidade mínima de circunferências, que é justamente o que estamos procurando.

Observe que

$ \alpha_1+\beta_1>\alpha_1+\beta_2>\dots>\alpha_1+\beta_n>\alpha_2+\beta_n>\dots>\alpha_n+\beta_n. $

Logo, existem ao menos $ 2n+1 $ valores diferentes para a soma $ \alpha_i+\beta_j $, ou seja, pelo menos $ 2n+1 $ circunferências distintas. Existe algum caso com exatamente $ 2n+1 $ circunferências distintas?

Sim: basta definirmos

$ \alpha_i=\beta_i=\frac{N+1-i}{N}.\theta $

para $ 0^{\circ}< \theta < 90^{\circ} $. Mostremos que ao escrevermos $ \alpha_1+\beta_1,\alpha_1+\beta_2,\dots,\alpha_1+\beta_n,\alpha_2+\beta_n,\dots,\alpha_n+\beta_n $ já teremos todos os valores possíveis para $ \alpha_i+\beta_j $.

Note que

$ \alpha_i+\beta_j = \alpha_M + \beta_P \Leftrightarrow i+j=M+P $.

Assim, para quaisquer outros $ \alpha_i $ e $ \beta_j $, a soma já vai estar na lista que fizemos anteriormente.

Logo, este é o caso com exatas $ 2n+1 $ circunferências e este é o valor mínimo que podemos obter.

Fecho Convexo Editar

Dados $ n $ pontos, podemos tomar alguns deles de tal forma que teremos o único convexo que contém, junto com o seu bordo e o seu interior, todos os $ n $ pontos. Este polígono é chamado de fecho convexo.

Exemplo (Cone Sul 1996) Editar

Achar todos os números inteiros $ n \geq 3 $ tais que exista um conjunto $ S_n $ formado por $ n $ pontos do plano que satisfaçam as duas condições seguintes:

1. Três pontos quaisquer não são colineares.

2. Nenhum ponto se encontra no interior do círculo cujo diâmetro tem por extremos dois pontos quaisquer de $ S_n $.

NOTA: Os pontos da circunferência não são considerados interiores ao círculo.

Solução: Antes de atacarmos o problema, precisamos entender quando um ponto $ P $ está no interior de um círculo de diâmetro $ AB $. Sabemos que ele está na circunferência se, e somente se, $ \angle APB = 90^{\circ} $. E quando ele está no interior da circunferência? E no exterior?

Podemos mostrar que $ P $ pertence ao interior de um círculo de diâmetro $ AB $ se, e somente se, $ \angle APB > 90^{\circ} $ e assim $ P $ pertence ao exterior de um círculo de diâmetro $ AB $ se, e somente se, $ \angle APB < 90^{\circ} $ (você pode encontrar a prova deste fato aqui).

Comecemos vendo que o polígono formado pelos $ n $ pontos é convexo. De fato, suponha, por absurdo, que exista algum ponto no interior do fecho convexo dos $ n $ pontos. Se dividirmos este polígono convexo de $ m $ em $ m-2 $ triângulos, de modo que os vértices destes triângulos e os dos fechos convexos coincidem e cada lado do fecho convexo faz parte de um e somente um triângulo.

Algum destes triângulos contém $ P $. Chamaremos ele de $ ABC $. Então $ \angle APB + \angle BPC + \angle CPA = 360^{\circ} $.

Porém, como $ P $ está no exterior das circunferências de diâmetros $ AB $, $ BC $ e $ CA $, segue que $ \angle APB $, $ \angle BPC $ e $ \angle CPA $ são menores que $ 90^{\circ} $, de onde segue que

$ \angle APB + \angle BPC + \angle CPA < 270^{\circ}. $

Contradição. Logo, o polígono formado pelos $ n $ pontos é convexo. Agora que já sabemos disso, podemos usar as propriedades de polígonos para terminarmos de resolver o problema. Todos os ângulos do polígono são menores ou iguais a $ 90^{\circ} $ (pois nenhum ponto se encontra no interior de uma circunferência com o diâmetro de extremos iguais a outros dois pontos). Então a soma dos ângulos é menor ou igual a $ 90^{\circ}n $. Mas já sabemos também que a soma dos ângulos internos de um polígono é $ 180^{\circ}(n-2) $. Desta forma,

$ 180^{\circ} (n-2) \leq 90^{\circ} n \Leftrightarrow n \leq 4. $

Então $ n $ só pode ser $ 3 $ ou $ 4 $. Existem soluções neste caso? Sim: o triângulo equilátero e o quadrado.

BibliografiaEditar