A Geometria Combinatória se ocupa com a contagem de objetos geométricos. A Geometria Clássica, dos gregos, nunca tratou de tais problemas. Resultados típicos de Geometria Combinatória são:

Dados n pontos no plano, o número de retas distintas que

eles determinam é, no máximo, . (Demonstre isso!).

Dados n pontos no plano , o número de distâncias distintas

entre eles é, pelo menos, .

(A demonstração deste fato é um pouco mais difícil do que a do anterior.
Ainda assim, tente fazê-la).

Um problema bem conhecido é o de saber quantas regiões do plano são determinadas por n retas nele situadas; ou ainda o de saber em quantas regiões n planos decompõem o espaço.

As situações descritas pelas figuras abaixo são facilmente tratadas. Na primeira situação, em que n retas paralelas dividem o plano, teremos uma decomposição em  n + 1 regiões. Na segunda, se tivermos um feixe de n retas concorrentes em um ponto, teremos 2n regiões. Estes resultados podem ser facilmente demonstrados.

Figura l

Proposição l. Dadas n retas paralelas no plano, elas o dividem em  n + 1  regiões disjuntas.

Demonstração:

Seja h₂(n) o número de regiões em que n retas paralelas decompõem o plano. Então, ao traçarmos mais uma reta, paralela às n primeiras, obtendo assim n + 1 retas paralelas, o número h₂ (n + l) de regiões em que estas n + 1 retas decompõem o plano será:

h₂(n + l) = h₂(n) + l                              (A)

pois a nova reta decomporá uma das regiões em duas, ou seja, dará origem a mais uma região. Temos assim o resultado descrito por (A), qualquer que seja o valor de n 1.

A fórmula (A) é uma fórmula de recorrência. Ela nos permite achar uma expressão para h₂(n) em função de n. Com efeito:

Como h₂(l) = 2, o número de regiões em que uma reta divide o plano, temos enfim:

h₂ (n + l) = n + 2

ou ainda

h₂ (n) = n + 1                      (B)

Caso o leitor não goste da demonstração acima, poderá fazer outra, por indução matemática, como abaixo.

Obviamente,

h₂ (1) = 2

Suponha agora que (B) seja válida para n. Então, para  n + 1, temos:

h₂ (n + l) = h₂ (n) + l

visto que a (n + l)-ésima reta aumenta de um o número de regiões. Então, como estamos supondo, pela hipótese de indução, que h₂ (n) = n + l, teremos:

h₂ (n + l) = (n + l) + l = n + 2

que é a fórmula (B) para o caso n + l, o que conclui a demonstração. A desvantagem da demonstração por indução matemática é que ela exige que saibamos, de antemão, qual a resposta procurada.

A demonstração do seguinte resultado é inteiramente análoga e deixada ao leitor:

Proposição 2. Sejam dadas, em um plano, n retas concorrentes em um ponto. O número de regiões em que elas decompõem o plano é 2n.

O mesmo não acontece nos exemplos abaixo:

Figura 3

Na Fig. 3, à esquerda, L₁ é paralela a L₂; à direita, L₁ L₃  e L₄ concorrem em um ponto.

Procuremos então determinar o número de regiões, h₂ (n), em que n retas em posição geral decompõem o plano.

(Observe que h₁(n) = h₁ (n - 1) + l, pois se a reta estiver dividida em = h₁ (n - 1) partes por n - l pontos, a introdução de mais um ponto dividi-rá uma das partes já existentes em duas, ou seja, aumentará de l o número das partes. Então, raciocinando por recorrência, vemos que:

(Observação. Você notou que o raciocínio feito acima é essencialmente o usado para demonstrar a proposição l? Em verdade, a proposição l e o resultado acima sobre h₁ são equivalentes. Para ver isso, dado um feixe de paralelas, trace uma secante L ao feixe e reciprocamente, dada uma reta sobre a qual estão escolhidos n pontos, por cada um deles trace uma perpendicular à reta dada.)

Figura 5                                               Figura 6          

Voltemos agora ao nosso problema sobre a divisão do plano por retas. Suponhamos n l retas em posição geral, que dividem o plano em h₂(n  - l) partes. Consideremos o conjunto {L₁, L₂, ..., L_{n - 1}} em posição geral. Estas n l retas dividem o plano em h₂(n l) regiões.

Adicionemos ao conjunto {L₁, L₂, ..., L_{n - 1}} a n-ésima reta, L_n; como o conjunto
{L₁, L₂, ..., L_n} está em posição geral, vemos que cada uma das n l primeiras retas
L₁, L₂, ..., L_{n - 1} corta L_n em exatamente um ponto, e assim L_n fica dividida em h₁(n l) partes.

Observe, além disso, que cada uma das partes em que L_n está dividida divide uma região do plano em duas, ou seja, cada parte de L_n dá origem a mais uma região do plano; assim:

h₂(n) = h₂(n l) + h₁(n l)

ou seja

h₂(n) = h₂(n - l) + n,

visto que  h₁( n  - l ) = n.

       Então:

Observemos, para fins de generalização posterior, que

Os raciocínios expostos acima constituem uma demonstração dos seguintes resultados:

Teorema l. O numero de partes h₁(n) em que n pontos distintos dividem uma reta é:

Teorema 2. O numero de partes h₂(n) em que n relas em posição geral dividem o plano é:

Atacaremos agora o problema de determinar como n planos em posição geral dividem o espaço. Em primeiro lugar, é necessário definir posição geral para planos. Com isso queremos dizer que entre eles não há pares de planos paralelos, nem teremos ternos de planos que se cortam segundo uma mesma reta.

Procederemos de maneira análoga aos casos já tratados. Ou seja, suporemos n - l planos em posição geral, que dividem o espaço em h₃(n l) regiões, e traçaremos um n-ésimo plano _n , tal que o conjunto esteja em posição geral.

Observe que os n - l primeiros planos, cortam _n segundo  n - l  retas que estarão em posição geral (por quê?). Estas retas dividirão _n em  h₂ (n - l) regiões distintas.

É agora fácil de ver que cada uma destas h₂(n - l) regiões de  _n dividirá em 2 partes cada uma das regiões do espaço, ou seja, cada uma das h₂(n - l) regiões de _n dá origem a uma nova região do espaço. Assim:

         .....................................................................................................

Lembremos agora o seguinte resultado, que pode ser facilmente demonstrado usando indução matemática (faça-o!).

e temos por fim

Demonstramos assim o seguinte resultado:

Teorema 3. O número de regiões em que n planos em posição geral dividem

Podemos portanto resumir nossos resultados como segue:

Teorema 4. Sejam:

h₁(n)  - o número de partes em que n pontos distintos dividem uma reta,

h₂(n)  - o número de regiões em que n retas em posição geral dividem o plano,

h₃(n)  - o número de regiões em que n planos em posição geral dividem o espaço.

Então

Bibliografia

(1)   Berman, G. e Fryer, K. D. — An Introduction to Combinatorics — A. P., cap. I.
(2)   Cohen, D.I.A. — Basic Techniques of Combinatória! Theory — John Wiley, cap. 3.