Relação de Euler (prova geométrica).

No último post (confira), provamos a relação de Euler usando grafos. Neste post, provaremos usando geometria.

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

Para a prova do teorema, iremos usar o seguinte

Lema. Todo poliedro pode ser triangularizado de maneira tal que $V - E + F$ se mantenha constante.

Demonstração. Seja $P$ um poliedro qualquer. Suponha que $P$ não seja triangularizado. Seja $f$ uma face não-triangular e suponha que o número de arestas em $f$ é $n$.

Considere um vértice $v$ de $f$. Para cada vértice de $f$ diferente de $v$ e não-adjacente a $v$, trace uma nova aresta ligando $v$ a tal vértice. Como existem $n-3$ tais vértices, adicionaremos $n-3$ arestas. Isto nos dá uma triangularização de $f$. Além disso, $n-3$ faces foram adicionadas, pois cada vez adicionamos uma aresta, uma face existente é repartida em duas.

Como o processo acima não adiciona nenhum vértice e a quantidade de arestas adicionadas é igual a quantidade de faces adicionadas, temos que $V-E+F$ não se altera. Uma vez que fazemos isto para qualquer face não-triangular de $P$, podemos triangularizar todas as faces não-triangulares de $P$ de modo que $V - E + F$ não se altera. Isto conclui a prova do lema.

$\square$

O lema acima nos permite provar o teorema somente para a classe dos poliedros triangularizados. Sim, pois se $P$ é um poliedro qualquer, se tivermos que a relação de Euler é valida para uma triangularização de $P$, teremos ela também é válida para $P$, já que o lema nos assegura que $V-E+F$ não se altera na triangularização $P$. Então, iremos provar o teorema apenas para poliedros triangularizados.

Agora podemos partir para a prova do teorema.

Relação de Euler (prova com grafos).

Num post anterior, Sólidos Platônicos, usamos a famosa relação de Euler para poliedros, que é dada por:

$$ V - E + F = 2, $$

onde $V$ é o número de vértices de um poliedro convexo, $E$ é o número de arestas e $F$ é o número de faces.

A relação de Euler para poliedros é equivalente a relação de Euler para grafos planares conexos. Afinal, existe uma maneira natural de levar uma instância do primeiro problema para uma instância do segundo: sobre uma face do poliedro, "abra" o poliedro de modo que todas as faces esteja sobre um plano.  Iremos prová-la para grafos planares conexos.

Dado um grafo planar, isto é, um grafo desenhado sobre o plano e sem interseções entre arestas, chamamos de faces internas aquelas regiões internas limitadas pelas arestas do grafo que formam um ciclo. A face externa é a (única) região ilimitada. No que segue, consideramos como face tanto a interna quanto a externa.

Teorema (da relação de Euler). Se $G$ é um grafo planar conexo com $n$ vértices, $m$ arestas e $f$ faces, então vale que $$n - m + f = 2.$$

Conjectura de Erdös-Faber-Lovász

Lendo o texto do Béla Bollobás (veja aqui) e parei para pensar em qual problema seria um "sonho" para mim, isto é, um grande problema que eu amaria resolver. Depois de um tempo de reflexão, cheguei a escolha de uma conjectura em Teoria dos Grafos:

Conjectura de Erdös-Faber-Lovász. Se $k$ grafos completos, cada um tendo exatamente $k$ vértices, têm a propriedade de que cada par de grafos compartilham no máximo um vértice, então a união desses grafos pode ser colorida com $k$ cores.

Esta conjectura é de 1972 e pode ser encontrada num artigo do Erdös onde ele fala quais são os problemas que ele gostaria de ver resolvido (veja aqui o artigo).

O seu enunciado não é difícil de entender e esta conjectura tem tentado muitos combinatoristas. E este foi um dos motivos pela qual me interessei por esta conjectura.

A primeira vez que a vi foi num seminário do grupo de pesquisa da qual faço parte, o ParGO (link). Lá, vi a conjectura sendo relacionada com algo sobre b-coloração (um tema para um futuro post), do qual não lembro muito bem como isto era feito.

Confesso que já tentei resolver a conjectura algumas vezes (mais precisamente, cinco vezes). Infelizmente, meus conhecimentos em teoria dos grafos é ainda muito elementar, e o que pude aplicar na conjectura não me retornou nada muito surpreendente (mas ainda sim obtive algumas conclusões).

Cada vez que tentei resolvê-la, esta conjectura me encantava ainda mais. Sim, pois quando eu aprendia algum método novo (como o método probabilístico e o Lema da Regularidade), logo tentava aplicar na conjectura. O interessante é que tais ferramentas eram aplicáveis, em sua maioria, mas o que eu conseguia concluir não era o suficiente para provar a conjectura. É como se a conjectura fosse a prova de métodos fodásticos. Ou até mesmo, eu ainda não sou capaz de aplicá-los de maneira eficiente. Mas também acredito que muitos já devem ter tentado aplicá-los a esta conjectura.

No fim, tentar resolver a conjectura foi um bom exercício para mim. Pretendo mantê-la como um "sonho", e seguindo os conselhos do Bollobás, estudando problemas mais ao meu nível atual.

$\sqrt{2}$ é irracional.

Todo mundo já deve conhecer a prova de que $\sqrt{2}$ é irracional. Se não, deixe eu fazê-la: suponha que $\sqrt{2}$ é racional. Então existem $a$ e $b>0$ inteiros primos entre si com $$\sqrt{2}=\frac{a}{b}.$$ Elevando esta última identidade ao quadrado e multiplicando por $b^2$, temos que $$2b^2 = a^2.$$ Logo $a^2$ é par. Como a raiz quadrada de um número par ainda é par, temos que $a$ é par. Então podemos escrever $a$ como $a = 2c$. Substituindo isto na última equação destacada, temos $$2b^2= 4c^2,$$ logo $b^2 = 2c^2$. E portanto, $b^2$ é par, logo $b$ também é. Neste ponto, chegamos num absurdo! Sim, pois concluímos que se $\sqrt{2}=\frac{a}{b}$ é de fato um número racional, então $a$ e $b$ são pares, logo 2 divide tanto $a$ quanto $b$, contradizendo o fato de $a$ e $b$ serem primos entre si.

Neste post queremos dar uma outra prova de que $\sqrt{2}$ é irracional. Mas para isto iremos provar um resultado mais forte:

Teorema. Se um número real $x$ satisfaz a equação

$$x^n + c_1x^{n-1} + \cdots + c_n = 0$$

com coeficientes inteiros, então ou $x$ é inteiro ou $x$ é irracional.

Em outras palavras, não existe racional não-inteiro que seja raiz de um polinômio mônico com coeficientes inteiros.

$e$ é irracional.

Neste post, daremos um prova rápida de que $e$ é um número irracional.

Da fórmula da expansão em séries de Taylor da função $f(x) = e^x$, sabemos que

$$ e = \sum_{k = 0}^{\infty} \frac{1}{k!} = 1 + 1 + \frac{1}{2} + \frac{1}{6} + \frac{1}{24} + \ldots$$

Suponha que $e$ seja racional, i.e., existem $a$ e $b>0$ inteiros tais que $e = \frac{a}{b}$. Seja $n\geq b$ e considere

$$ N:= n!\left(e - \sum_{k = 0}^{n} \frac{1}{k!} \right).$$

Uma vez que $n!e$ e $\frac{n!}{k!}$ (para $0 \leq k \leq n$) são inteiros, temos que $N$ é um número inteiro positivo. Por outro lado,

$$N = n!\left(e - \sum_{k = 0}^{n} \frac{1}{k!} \right) = n!\left(\sum_{k = n+1}^{\infty} \frac{1}{k!} \right) = \sum_{k = n+1}^{\infty} \frac{n!}{k!}.$$

Dado $k>n$, seja $r = n-k$. Temos que

$$\frac{n!}{k!} = \frac{n!}{(n+r)!} = \frac{n!}{n!(n+1)(n+2)\ldots (n+r)} = \frac{1}{(n+1)(n+2)\ldots (n+r)} \leq \frac{1}{(n+1)^{r}}.$$

Daí,

$$N = \sum_{r = 1}^{\infty} \frac{n!}{(n+r)!} \leq \sum_{r=1}^{\infty} \frac{1}{(n+1)^{r}}.$$

Mas sendo o somatório no lado direito da desigualdade acima uma série geométrica, temos que

$$ \sum_{r=1}^{\infty} \frac{1}{(n+1)^{r}} = \frac{1}{n}.$$

Portanto, $N \leq \frac{1}{n}$, para todo $n\geq b \geq 1$, contradizendo o fato de $N$ ser inteiro positivo.

$\square$

Referências:

[1] Martin Aigner, Günter M. Ziegler; As porvas estão n'O LIVRO. Editora Edgard Blücher, 2002.

Conjecturas de Goldbach.

Um dos problemas mais antigos da matemática é a Conjectura de Goldbach. Talvez esta conjectura recebeu fama pela sua simplicidade. Algo parecido ocorreu com o Último Teorema de Fermat, que foi considerado uma conjectura por 359 anos, até que em 1994, o matemático britânico Andrew Wiles publicou uma prova para tal.

O que hoje chamamos de conjectura de Goldbach surgiu numa das cartas do matemático alemão Christian Goldbach (original de Brandenburg-Prussia) endereçada ao matemático Leonhard Euler, a carta XLIII, datada de 7 de Junho de 1742 (clique na imagem abaixo para ver a carta) [1].

Teorema da Bandeira Britânica

Neste post, quero apresentar um belo teorema em Geometria Euclidiana Plana que recebe o nome de Teorema da Bandeira Britânica. Este teorema nos diz que a soma das áreas dos quadrados vermelhos da figura abaixo é igual a soma das áreas dos quadrados azuis e isto continuaria valendo se movêssemos o pontinho preto no interior do retângulo para qualquer outro lugar ainda dentro do retângulo.

Teorema (da Bandeira Britânica). Seja $ABCD$ um retângulo. Dado um ponto $P$ qualquer dentro de $ABCD$, temos que

$${AP}^2+{CP}^2={BP}^2+{DP}^2.$$

Um texto de Béla Bollobás

Béla Bollobás é um matemático húngaro (sim, esse é um nome de menino, pelo menos na Hungria) da Universidade da Memphis e da Universidade de Cambridge. Nasceu em Budapeste em 3 de agosto de 1943, hoje tem 69 anos. Desde muito jovem se interessou por matemática e foi um dos primeiros medalhistas da IMO ( International Mathematical Olympiads), condecorado com duas medalhas de ouro e uma de bronze (veja). Conheceu Paul Erdös graças ao seu desempenho na IMO e aos 19 anos publicou o seu primeiro artigo junto com o Erdös.

Tem publicado artigos, livros e teses em Análise Funcional, Combinatória, Teoria dos Grafos e Percolação. É, atualmente, uma das principais referências em Percolação e em Combinatória Extremal.

Neste post irei publicar um texto de Béla Bollobás (foto abaixo) que pode ser encontrado no livro The Princeton Companion to Mathematics.

Sólidos Platônicos.

Com certeza, todo mundo já se deparou com os sólidos Platônicos. Pra refrescar a sua memória, temos abaixo tais sólidos. Um sólido Platônico é um poliedro cujas as suas faces são congruentes dois a dois e cada vértice contém o mesmo número de arestas incidentes. O leitor pode verificar rapidamente que em cada um dos poliedros abaixo, cada um de seus vértices contém o mesmo número de arestas incidentes. Já a afirmação de que suas faces são congruentes dois a dois exige um pouco mais, mas podemos ao menos verificar que o número de arestas são iguais em cada face de cada poliedro.

Desde os tempos dos gregos antigos já se sabiam que os únicos poliedros platônicos são aqueles da figura. No livro Elementos de Euclides já se encontrava uma descrição matemática das propriedades destes sólidos (Livro XIII, proposições 13 – 18). 

Neste post, daremos uma demonstração de que os únicos sólidos Platônicos são estes cinco. Para tal prova, iremos assumir a fórmula de Euler: $V – E + F = 2$, onde $V$ é o número de vértices de um poliedro conexo, $E$ é o número de arestas e $F$ é o número de faces. Eu prometo que logo publicarei uma demonstração desta fórmula.

Abaixo, temos uma tabela com os valores de $A$, $V$ e $F$ para os sólidos Platônicos.

Vamos agora a o teorema.

Teorema (da classificação dos sólidos Platônicos). Os únicos sólidos Platônicos são aqueles listados anteriormente.

Partições em Conjuntos Fechados.

Pode o plano ser particionado em uma quantidade enumerável de conjuntos fechados? E o $\mathbb{R}^{n}$?

Grafos: definições, nomenclaturas e notações

Neste texto, irei dar algumas noções elementares sobre grafos baseadas no livro Graph Theory [1].

Um grafo $G$ é um par ordenado $G = (V,E)$, onde $V$ é um conjunto qualquer e $E$ é uma coleção de pares de elementos de $V$, i.e., $E = \{\; \{x,y\} \; | \; x,y \in V, x\neq y\}$. Os elementos de $V$ são chamados de vértices do grafo e os elementos de $E$ são chamados de arestas. Uma aresta $e$, formalmente, é um par $e = \{x,y\}$, onde $x,y$ são vértices do grafo, mas por comodidade iremos representar a aresta $e$ apenas por $xy$, de modo que não haverá confusão ao identificarmos $e=xy=yx$.

Segundo a nossa definição de grafo, não há possibilidade de duas arestas distintas conectarem o mesmo par de vértice. Também não há chance alguma de existir uma aresta que conecte um vértice $x$ a ele mesmo (arestas deste tipo recebem o nome de laços ou loops). Assim, segundo a definição de alguns livros, o nosso grafo é um grafo simples. Mas como este é principal tipo de grafo que nos interessa por enquanto, não iremos nos preocupar em dizer que os nossos grafos são simples. Existem outros tipos de grafos tão interessante quanto os simples: grafos orientados, múltiplos, com fluxos, labelados, entre outros (ver [1]). Outra coisa, não esteremos, por enquanto, interessados em grafo cujo o conjunto dos vértices é infinito. Logo, assumiremos desde já que $|V| < \infty$. Consequentemente, o conjunto das arestas é finito também.

É muito comum e conveniente representar um grafo $G$ por um desenho sobre um plano onde os vértices são representados por pontos no plano e arestas que conectam dois vértices $x$ e $y$ são representados por linhas (retas ou curvilíneas) que contêm os pontos que representam os vértices $x$ e $y$ como extremidades. Claramente, um grafo pode ser desenhado de inúmeras maneiras distintas, logo não devemos nos apegar ao desenho do grafo, mas utilizá-lo para visualizar rapidamente algumas afirmações. Muitas vezes iremos verificar algo através de um desenho, mas isso deve ser feito de modo que fique claro que esta verificação é independente da maneira que desenhamos.

Primeira postagem e o primeiro teorema sobre grafos.

Esta é a primeira postagem do blog Tiorema! Pretendo, neste espaço, postar algumas coisitas matemáticas que acho interessante. Tem tanta coisa que nem sei bem por onde começar. Como gosto muito de combinatória, decidi começar por um dos primeiros teoremas em Teoria dos Grafos: o Teorema de Euler. O leitor que não conhece ainda a Teoria dos Grafos ou que não está muito familiarizado com as definições e notações poderá ler um post que preparei com as principais noções que usarei ao falar de grafos [link], apesar de que neste post a principal definição será feita logo no próximo parágrafo de modo que um conhecimento básico de grafos já é suficiente para uma boa leitura deste texto.

Dado um grafo $G=(V,E)$, um passeio (de tamanho $k$) em $G$ é uma sequência alternada de vértices e arestas

$$P = v_0 e_1 v_1 e_2 v_2 \ldots  v_{k-1} e_{k} v_k, $$

com $v_0, v_i\in V$ e $e_i = \{v_{i-1},v_{i}\} \in E$, pra todo $1 \leq i \leq n$. Os vértices $v_i$ não precisam todos serem distintos; quando são, $P$ é chamado de caminho. Quando as aresta $e_i$ são todas distintas, dizemos que $P$ é uma trilha. Quando $v_0 = v_k$, dizemos que $P$ é um passeio fechado; se $P$ for uma trilha, dizemos que ele é uma trilha fechada. Uma trilha fechada cujos os vértices $v_i$, para $i \geq 1$, são distintos é chamado de ciclo.

Uma trilha fechada $P$ é um circuito Euleriano do grafo $G$ se todas as arestas de $G$ estiverem em $P$. Em outras palavras, queremos percorrer todo o grafo através das arestas começando de um vértice e voltando, no fim, para o mesmo vértice, mas sem passar pela mesma aresta duas vezes. Um grafo que contém um circuito Euleriano é dito ser um grafo Euleriano.

Euler se interessou por esse tipo de passeio quando se questionou se era possível visitar todas as quatro regiões da cidade Königsberg (território da Prússia até 1945, atual Kaliningrado). Estas quatro regiões eram conectadas por sete pontes (ver figura abaixo). Mas Euler não queria visitá-las de qualquer maneira, ele queria passar por cada ponte exatamente um vez.