"Seja S um conjunto finito de pontos no plano euclidiano. Suponha que cada reta que passa por dois pontos de S, necessariamente, contém um terceiro ponto de S. Então, os pontos de S estão sobre uma mesma reta."
O problema acima foi proposto na postagem anterior e, como prometido, hoje trago uma solução para ele. De fato, o primeiro matemático a propor esse problema foi James Joseph Sylvester em 1893.
James Joseph Sylvester
Acredita-se que Sylvester não conhecia uma solução desse problema. A primeira prova desse resultado veio algumas décadas depois que Sylvester o propôs e é devida a Tibor Gallai. Abaixo, apresentamos a prova de Leroy Milton Kelly para o Teorema de Sylvester e Gallai.
Prova. Suponha que os pontos de S não estejam sobre uma única reta. Seja L(S) o conjunto de todas as retas que passam por dois pontos de S. Sejam p ponto de S e r reta de L(S) tais que a reta r não contém p e a distância de p a r seja a menor possível dentre tais pares. Por hipótese, a reta r contém 3 pontos de S. Digamos A, B e C (com B entre A e C). Sem perda de generalidade, podemos supor que o pé da perpendicular por p e r, o qual denotamos por Q, não está entre C e B (como na figura abaixo).
Seja t a reta que passa por P e C (reta azul na figura acima). Denotemos por D o pé da perpendicular por B e a reta t. Assim, t é uma reta de L(S) e B é um ponto de S que não pertence à reta t. Por outro lado, desde que os triângulos PQC e BDC são semelhantes, vemos que a distância de B à reta t é menor do que a distância de P à reta r. O que é um absurdo.
(Fonte: "As provas estão n'O LIVRO" de Aigner-Ziegler ed. Edgar Blucher LTDA).
Em uma manhã de muito calor em Fortaleza, dois sticks russos de São Petersburgo estão submetidos à burocracia brasileira para solicitação de visto permanente. Essa é exatamente a situação em que ocorre a cena abaixo.
Embora não exista uma grande fila na Polícia Federal para realização de tal procedimento, os desencontros de informações, a lista de documentos e os caprichos que envolvem tal processo deixam qualquer um nervoso.
Mas, como estamos falando de sticks russos de São Petersburgo, a fala da cena acima não é um comentário sobre a situação chata e de ansiedade em que eles estão submetidos. Isso mesmo, a fala acima é uma proposta de desafio matemático que, obviamente, foi imediatamente aceita pelo outro stick. O problema proposto foi o seguinte:
Problema. Dados n pontos no plano euclidiano, suponha que cada reta por dois desses pontos, necessariamente, contém um terceiro ponto do conjunto dado. Mostre que todos os pontos do conjunto dado estão sobre uma mesma reta.
Na próxima postagem, trarei uma solução do problema acima.
Créditos: problema comunicado pelo Professor Lev Birbrair da UFC.
Convido você a participar de um jogo (fictício) em que, ao final, você pode ganhar ou bem um carro 0km ou um bode velho e magro. O jogo é o seguinte:
Atrás das portas abaixo há um carro 0km e dois bodes velhos e magros,
ou seja, o carro está atrás de uma das portas acima e atrás de cada uma das outras duas portas há um bode velho e magro.
Como informação importantíssima sobre esse jogo, eu sei o que há atrás de cada uma das portas.
Início do Jogo
Primeiro movimento: você escolhe uma das portas
Segundo movimento: uma vez que você escolheu uma porta eu abro uma das outras duas portas que restaram, e revelo para você um bode (Ressalto que eu não abro essa porta aleatoriamente, pois, como informei, eu sei exatamente o que há atrás de cada porta)
Terceiro movimento: você escolhe permanecer com a porta que escolheu no primeiro movimento ou trocar pela outra porta que restou fechada
Final do jogo
Você ganha o que tiver atrás da porta que você escolheu no terceiro movimento.
Problema.Partindo do pressuposto que você está interessado em ganhar o carro 0km e não um bode velho e magro, qual seria a melhor estrategia a seguir no terceiro movimento, permanecer com a porta escolhida no primeiro movimento ou efetuar a troca?
O problema acima é conhecido como o Problema de Monty Hall. Monte Halperin (Monty Hall) foi apresentador do game show norte-americano Let's Make a Deal onde ele propunha o jogo acima para seus convidados
(Fonte: Wikipedia "The Monty Hall Problem").
Solução do Problema. É fato que a decisão que você deve tomar está no terceiro movimento. Agora, observe o que ocorre no primeiro movimento. Você escolhe uma entre três portas, portanto a probabilidade de você ter escolhido a porta que esconde o carro é de 1/3 e, portanto, a probabilidade do carro está comigo é de 2/3. No segundo movimento, quando eu abro uma porta que está em meu poder, revelando um bode, eu não mudo as probabilidades acima, pois, como informei, eu não abro essa porta aleatoriamente. Assim, no terceiro movimento, você tem a oportunidade de permanecer com a probabilidade de 1/3 (de estar com o carro) ou trocar pela probabilidade de 2/3. Logicamente, do ponto de vista probabilístico, a melhor estrategia é trocar de portas no terceiro movimento.
Final da solução.
Abaixo segue uma cena do filme 21 (traduzido por: Quebrando a banca) em que o Problema de Monty Hall é discutido e solucionado.
Ao final de mais uma tarde de verão, três amigos se reúnem em uma refrigerada cafeteria de um shopping Center de Fortaleza para tomar algumas xícaras de café, falar de matemática e outros assuntos correlatos. Antes da primeira rodada de café, um problema sobre múltiplos irados, o qual foi proposto na revista RPM 77, veio à mesa.
Aqui, faz-se necessaria a apresentação do conceito de número irado. Dizemos que um número natural é irado se ele é escrito, na base decimal, somente com 0's e 1's.
De volta à narração, simultaneamente aos primeiros exemplos de números irados, chegou à mesa a primeira rodada de café: 3 expressos duplos!
Problema. Mostrar que todo número natural possui um múltiplo irado.
Assim, sobre a mesa estavam o conceito de números irados, o problema acima e 3 expressos duplos.
Senso comum: era hora de tomar um pouco de café, filosofar um pouco mais, encontrar a naturalidade da proposição acima.
A aparente descontração daquele grupo ia se transformando em tensão. Aos olhos de quem se servia ao balcão da cafeteria e, de lá, estava à espera de um lugar mais confortável para se acomodar, um silêncio inexplicável também se punha sobre aquela mesa.
Momentos que antecediam ao arremate final do problema, ainda antes de terminar a primeira xícara de café, os pensamentos convergiam para um único resultado.
Teorema de Euler. Se $a$ e $n$ são números naturais relativamente primos, então $n$ divide $a^{\phi(n)}-1$.
Acima, $\phi$ é a função "phi" de Euler que é definida da seguinte forma: $\phi (n)$ é o número de naturais menores do que $n$ e relativamente primos com $n$.
Isso! O Teorema de Euler era suficiente para a construção de uma prova de que todo número natural possui um múltiplo irado.
Solução do Problema. Seja $n$ um número natural. Escrevamos $n$ da seguinte forma: $n=2^a\cdot 3^b\cdot 5^c\cdot m$ em que $m$ é relativamente primo com $2,3,5$.
Desde que 10 e $3^{b+2}\cdot m$ são relativamente primos, pelo Teorema de Euler, existe um número natural $k$ de sorte que
$k\cdot 3^{b+2}\cdot m = 10^{\phi(3^{b+2}\cdot m)}-1$
isto é,
$k\cdot 3^{b+2}\cdot m = 99\dots 9$
e, portanto,
$k\cdot 3^b\cdot m = 11...1$.
Finalmente, recebemos que
$(2^c\cdot 5^a\cdot k)\cdot n = 11\dots 10\dots 0$
é um múltiplo irado de $n$.
CQD
Para finalizar a postagem, vale ressaltar que essa prova da existência de múltiplos irados é puramente existencial no seguinte sentido: não apresentamos um algoritmo decente para o cálculo do menor múltiplo irado de um número natural qualquer.
Por exemplo, se utilizamos a demonstração acima para encontrar um múltiplo irado do número 13 obtemos o seguinte: pelo Teorema de Euler, 13 divide $10^{12}-1$, ou seja, 13 divide $999.999.999.999$ e, daí, 13 divide $111.111.111.111$. Essa prova produziu um múltiplo irado de 13 que, aparentemente, não possui relação com o menor múltiplo irado de 13, a saber, 1001.
As outras rodadas de café foram dedicadas à seguinte questão:
"há uma fórmula para obter o menor múltiplo irado de $n$ olhando apenas para a sua fatoração em primos?"
Como havíamos prometido, esta postagem é destinada a uma solução do problema abaixo, o qual foi proposto na postagem anterior.
Problema A. Não é possível escrever o plano real como reunião de quadrados fechados dois a dois disjuntos.
Para esse fim, recorremos a um teorema bacana relacionado ao conceito de ponto de acumulação.
Antes de apresentarmos o conceito de ponto de acumulação, para evitar qualquer sentimento paranoico do tipo que compele o indivíduo a associar qualquer conceito matemático ao cotidiano, deixamos claro que, aqui, pontos de acumulação não têm relação com programas de cartões de crédito, milhagens de companhias aéreas ou ainda com o bem-humorado blog do Renan. De toda sorte, no parágrafo seguinte, apresentamos a definição de ponto de acumulação de um subconjunto da reta real.
Dizemos que um número real r é um ponto de acumulação de um subconjunto X da reta real se qualquer intervalo aberto contendo r contém, necessariamente, um elemento do subconjunto X o qual é diferente de r.
Denotamos por X' o subconjunto da reta real formado pelos pontos de acumulação de X.
Teorema Bacana. Seja X um subconjunto não-vazio da reta real. Se X=X', então X não é enumerável.
Pode-se encontrar uma prova do teorema acima no livro "Curso de Análise Vol. 1" (Projeto Euclides, IMPA) do Professor Elon Lages Lima.
Como aplicação do Teorema Bacana, vejamos a versão 1-dimensional do problema proposto no início da postagem. A versão abaixo foi proposta por Rafael na seção de comentários da postagem anterior.
Versão 1-dimensional do Problema A.Não é possível escrever a reta real como reunião de intervalos fechados dois a dois disjuntos.
Prova da versão 1-dimensional do Problema A. De fato, por contradição, suponhamos que exista uma cobertura da reta real por intervalos fechados dois a dois disjuntos. Denotemos por F essa família de intervalos e por X o subconjunto da reta formado pelos extremos dos intervalos da família F. Considere a função que a cada intervalo dessa família associa um racional no interior desse intervalo. Desde que os intervalos dessa cobertura são dois a dois disjuntos, temos que essa função é injetiva. Portanto, a família F é enumerável e, em particular, o conjunto X também o é. Por outro lado, é fácil ver que X=X'. Agora, pelo Teorema Bacana, temos uma contradição.
Solução do Problema A. Por contradição, suponhamos que exista uma cobertura do plano real por quadrados fechados dois a dois disjuntos. Denotemos por Q essa família de quadrados. Considere a função que a cada quadrado dessa família associa um ponto no interior desse quadrado que tem coordenadas racionais . Desde que os quadrados dessa cobertura são dois a dois disjuntos, temos que essa função é injetiva. Portanto, a família Q é enumerável. Em particular, o conjunto formado pelos vértices dos quadrados da família Q é enumerável. Assim, temos uma R reta no plano real que não intersecta esse conjunto de vértices descrito acima. Agora, pela construção da reta R, a interseção de R com cada quadrado da família Q ou bem é vazia ou é um intervalo fechado da reta R. Daí, temos que a reta R é coberta por uma reunião enumerável de intervalos fechados dois a dois disjuntos. O que contradiz a versão 1-dimensional do Problema A.
C.Q.D.
Para finalizar esta postagem, gostaria de dizer que quem tiver interessado em conhecer a prova do Teorema Bacana, e não tiver acesso a uma referência, é só me enviar um mensagem que posso retorná-la com uma cópia da prova apresentada no livro Curso de Análise Vol. 1. É isso!
"O plano euclidiano não pode ser escrito como reunião de quadrados fechados e dois a dois disjuntos".
- Êpa! Grita um stick atento e com espírito cético dos jovens matemáticos. - Veja o contra-exemplo abaixo! Temos um plano coberto por uma reunião de quadrados que não se sobrepõem.
De fato, a figura acima não representa um contra-exemplo para o que afirmamos no início da postagem. Com efeito, se o pedreiro responsável pela colocação desse piso trabalhou bem, então entre cada quadrado de cerâmica acima há uma massa rejunte (assim não temos uma cobertura do plano somente pelos quadrados). Agora, se o tal pedreiro não trabalhou bem, então os quadrados de cerâmica adjacentes possuem interseção em suas fronteiras (assim a reunião não é por quadrados dois a dois disjuntos).
É isso aí! Fica o desafio para provar ou dar um contra-exemplo para a proposição acima. Na próxima postagem, espero trazer uma solução para esse enigma.
Meus amigos, é isso mesmo que vocês estão pensando! A cena acima é de um stick bravo soltando o verbo contra um stick confuso. Explico! Os nobres sticks promoveram uma partida de futebol não convencional, Flamenguinho versus Peñarol. O inusitado é por conta de que cada time seria composto de infinitos atletas. Isso mesmo, infinitos atletas em cada equipe, coisas do mundo stick! Até aí, os nobres estavam em acordo. Contudo, no dia do evento, no momento da apresentação dos atletas escalados, vejam a surpresa.
Flamenguinho (Azul e Amarelo) Peñarol (Vermelho e Branco)
Camisa 1 - Umberto Camisa 0 - Zeromildo
Camisa 2- Doisberto Camisa 1 - Umildo
... ...
Camisa N - Nberto Camisa N - Nmildo
... ...
Imediatamente após a apresentação dos atletas da equipe do Peñarol, o nobre representante da equipe do Flamenguinho protestou alegando que estaria com um jogador a menos, pois o Flamenguinho escalou jogadores com as camisas 1,2,...,n,... e o Penãrol escalou jogadores com tais camisas e, além disso, escalou um jogador com a camisa 0.
É isso, na cena do início da postagem temos o nobre flamenguista bravo por entender que iniciaria a partida com um jogador a menos enquanto o representante do Peñarol estava confuso pois para ele infinito é infinito... Sabe-se lá o que passava na cabeça dele!
Momento de reflexão...
Até que um velho e sábio stick resolveu interferir na discussão e sugeriu que o Flamenguinho utilizasse o seu uniforme reserva, o qual contém as camisas 0,1,2,...,n,... , e reescalasse a equipe da seguinte forma
Nova escalação do Flamenguinho
Camisa 0 - Umberto
Camisa 1 - Doisberto
Camisa 2 - Trêsberto
...
Camisa n - (n+1)berto
...
Acima, temos os mesmos jogadores inicialmente escalados no Flamenguinho, porém, agora com as camisas 0,1,2,...n,... assim como o Peñarol!
Depois da solução apresentada pelo velho e sábio stick, não temos mais um stick bravo e outro confuso, agora temos dois sticks confusos
Segue uma explicação para razoável sugestão apresentada pelo velho e sábio stick.
Para decidirmos se dois conjuntos (finitos) A e B têm a mesma quantidade de elementos fazemos um emparelhamento entre os elementos de A e B. Por exemplo, se A representa o conjunto de cadeiras em uma sala de aula e B representa o conjunto de alunos nessa sala de aula. Pedimos para que cada aluno sente-se sozinho em uma cadeira (emparelhamos). Se alguns alunos ficarem sem cadeiras, então B tem mais elementos do que A. Se algumas cadeiras ficarem vazias, concluiremos que A tem mais elementos do que B. E, finalmente, se em cada cadeira tivermos um único aluno, concluiremos que A e B possuem a mesma quantidade de elementos. Essa última situação, isto é, quando cada aluno está sentado em uma única cadeira e não sobra cadeira, corresponde ao fato matemático que existe uma bijeção entre os conjuntos A e B.
O que observamos na solução do problema de escalação dos times acima é que existe uma bijeção entre os conjuntos
{1,2,...,n...} e {0,1,2,...,n,...}. Portanto, utilizando a ideia de emparelhamento (ou bijeção) para estabelecer uma noção de que pares de conjuntos infinitos possuem a mesma quantidade de elementos, concluímos que o Flamenguinho e o Peñarol possuem a mesma quantidade de atletas escalados.
Um conceito matemático
Quando um conjunto infinito X está em bijeção com o conjunto dos números naturais {1,2,...,n,...} significa que podemos escrever o conjunto X da seguinte forma
nesse caso, dizemos que o conjunto infinito X é enumerável.
Com um pouco de criatividade, é possível mostrar que existe bijeção entre os conjuntos {...,-2,-1,0,1,2,...} e {1,2,...,n,...}., ou seja, o conjunto dos números inteiros é um exemplo de conjunto infinito enumerável.
Dois fatos relevantes :
O conjunto dos números racionais é enumerável
O conjunto dos números reais não é enumerável. Lembre-se disso, NÃO é possível escrever o conjunto dos números reais da seguinte forma
Abaixo, segue um vídeo muito interessante (e informal) sobre conjuntos infinitos enumeráveis e algumas propriedades.
.jpg)
