Teorema de Monsky.

Você sabe como dividir um quadrado em dois triângulos de mesma área? Claro que sabe! Dividir um quadrado em três triângulos de mesma área também não deve ser difícil, certo? Espero que você não tenha tentado fazer isto, pois isso não só é difícil como é impossível! Tente dividir o quadrado em quatro triângulos de mesma área. Novamente, isto não parece ser desafiante. Mas tente em cinco pedaços... Em seis... Ok. Você já deve ter chegado a conclusão que em partes pares, o problema não é difícil (veja a figura abaixo), mas em partes ímpares, talvez seja impossível.

De fato, não existe maneira de dividir o quadrado numa quantidade ímpar de triângulos de mesma área. A primeira pessoa a observar isto foi Fred  Richman (1965)[1]. Ele estava preparando um exame de mestrado e queria incluir este problema, mas ele não pode resolvê-lo. Ele então propôs este problema na American Mathematical Monthly. Cinco anos depois, o matemático americano Paul Monsky (foto abaixo) publicou uma prova. Hoje, conhecemos este resultado como Teorema de Monsky.

Teorema de Monsky. Não existe maneira de particionar um quadrado em uma quantidade ímpar de triângulos todos de mesma área.

A prova deste teorema é única. Não se conhece nenhuma outra prova. O mais incrível é que a prova deste teorema de caráter geométrico reúne ideias de teoria dos números, álgebra abstrata e combinatória. De fato, uma das ferramentas chave na prova deste teorema é o conceito de valor $p$-ádico e uma versão da prova do lema de Sperner.  Neste post, veremos tal prova.

Sobre o número cromático do plano.

Com quantas cores podemos pintar o plano de maneira tal que pontos com a mesma cor não estejam a distância unitária?

Dado um conjunto $X$ e um número natural $r$, uma $r$-coloração é uma função $c: X \rightarrow \{1,\ldots ,r \} $. Dado $x \in X$, dizemos que $c(x)$ é a cor de $x$. Coloração é um dos conceitos mais importantes em combinatória, uma vez que diversos problemas podem ser expressados como um problema de colorações. Coloração em grafos, por exemplo, tem se destacado em aplicações práticas como escalonamento de tarefas e alocação de frequências. Neste post, estaremos interessados em colorir o plano (ou $\mathbb{R}^2$, se preferir).

Este é considerado por muitos matemáticos como um dos problemas mais difíceis em geometria plana (para um ensaio histórico sobre este problema e seus correlatos, indico o livro [1]). Quanto a sua origem, Erdös, por exemplo, disse uma vez "I cannot trace the origin of this problem", num artigo de 1961.

Bem, o problema já foi enunciado no início deste post, mas por educação, irei citá-lo mais uma vez:

Qual é o menor número de cores necessárias para colorir o plano de tal maneira que nenhum par de pontos de mesma cor estejam a distância unitária?

Este menor número de cores é o que chamamos de número cromático do plano, e denotamos por  $\chi(\mathbb{R}^2)$, ou somente por $\chi$.

Relação de Euler (prova combinatória)

Nos dois últimos posts, provamos a relação de Euler usando grafos e geometria elementar. Neste post, provaremos usando contagem dupla.

Teorema (da relação de Euler). Se $P$ é um poliedro convexo com $V$ vértices, $E$ arestas e $F$ faces, então vale que $$V-E+F = 2.$$

Demonstração. Primeiro "abra" o poliedro de modo que todas as faces esteja sobre um plano. Fazemos uma contagem dupla da soma S de todo os ângulos internos do poliedro resultante. Sejam $N_1,N_2,\ldots,N_F$ a quantidade de arestas (e de vértices) de cada uma das faces, sendo $N_1$ a da face que delimita todas as outras. Uma vez que a soma dos ângulos interno de um polígono de $n$ lado é $(n-2)\cdot 180º$, temos que

$$ S = (N_2-2) 180º + (N_3-2)180º + \cdots + (N_F-2)180º\\=(N_2 + N_3 + \cdots + N_F)180º - 2(F-1)180º. $$

Fazendo, agora, a contagem através dos vértices, temos que

$$ S = (V-N_1)360º + (N_1-2)180º.$$

Igualando as duas somas, obtemos que

$$ (N_2 + N_3 + \cdots + N_F)180º - 2(F-1)180º = (V-N_1)360º + (N_1-2)180º,$$

que é equivalente a

$$2V -  (N_1 + N_2 + \cdots + N_F) + 2F = 4$$

Observe que a soma $N_1 + N_2 + \cdots + N_F$ é igual a $2E$, pois cada aresta aparece em exatas duas faces distintas. Portanto, $V-E+F = 2$. Isto conclui a demonstração.