terça-feira, 11 de dezembro de 2012

Um problema sobre distorções de curvas

Seja $\gamma$ uma curva simples e fechada em $\mathbb{R}^n$ de comprimento finito L. Dados quaisquer dois pontos distintos $p$ e $q$ sobre $\gamma$, existem exatamente dois arcos sobre a curva que conectam $p$ e $q$ e, pelo menos um deles tem comprimento $D_{\gamma}(p,q)$ menor do que ou igual à metade de L. Definimos a distância em $\gamma$ entre p e q como sendo $D_{\gamma}(p,q)$. De fato, a função $D_{\gamma}$, assim definida, é uma distância sobre a curva $\gamma$. Pois bem,  agora definimos a distorção de $\gamma$ como o supremo dos quocientes $\frac{D_{\gamma}(p,q)}{|p-q|}$ quando $p\neq q$ variam em $\gamma$.

Eis o nosso problema de hoje!

Problema. A distorção de $\gamma$ é sempre maior do que ou igual à metade de $\pi$ e, ocorre a igualdade se, e somente se, $\gamma$ é um círculo.

Na próxima postagem, trarei uma belíssima solução para este problema. 





quinta-feira, 22 de novembro de 2012

Renan, Medalha de Ouro

Renan da Silva Santos, aquele camarada do blog ponto de acumulação, aluno do Bacharelado em Matemática da UFC, conquistou a medalha de ouro no VI SIMPÓSIO NACIONAL / JORNADAS DE INICIAÇÃO CIENTÍFICA que aconteceu no IMPA, Rio de Janeiro, de 04 a 10 de novembro de 2012. O Renan, sob a minha orientação, apresentou uma monografia sobre endomorfismos injetivos de variedades algébricas. O resultado mais conhecido a respeito do tópico acima é o Teorema de Ax-Grothendick o qual diz que, no caso em que temos variedades algébricas sobre corpos algebricamente fechados, tais endomorfismos são necessariamente sobrejetivos. Além de trazer uma prova do Teorema de Ax-Grothendick, a monografia do Renan aborda resultados do tipo Ax-Grothendick quando consideradas variedades algébricas sobre corpos não necessariamente algebricamente fechados, vale a pena conferir.

Parabéns, Renan!

terça-feira, 18 de setembro de 2012

Complementar de conjuntos algébricos em $\mathbb{R}^n$

"Seja $V\subset\mathbb{R}^n$ um subconjunto algébrico não vazio. Então, $\mathbb{R}^n$ e $\mathbb{R}^n-V$ não são homeomorfos"

Abaixo, segue uma prova do resultado acima

Por Rodrigo Mendes Pereira

Primeiramente, meus agradecimentos ao professor Alexandre pelo convite! 

A prova que vou apresentar aqui usa uma versão semialgébrica da Homologia de Borel-Moore. Ressalto que o interesse em trabalhar com uma teoria de homologia dentro da estrutura semialgébrica é, dentre outros fatores, por ter a disposição boas ferramentas (como decomposição celular, descrição por fórmulas e existência de uma boa triangulação). De posse disto, é garantida a existência de uma classe fundamental sobre variedades algébricas que é essencial, em particular, para esta prova. Vamos lá então!

Gostaria de iniciar uma sequência observações sobre conjuntos semialgébricos apresentando o conceito de dimensão de conjuntos semialgébricos. Temos um teorema de decomposição de conjuntos semialgébricos que garante o seguinte: cada $X$ semialgébrico pode ser escrito como união finita e disjunta (a menos de um homeomorfismo semialgébrico) de cubos unitários abertos $(0,1)^{d_i}, \  d_i \in \mathbb{N} \cup \left\{0\right\}, i = 1,2 \ldots, k$. Com isto temos uma definição natural para dimensão de $X$, a saber, $dim X = max\left\{d_1, \ldots, d_k \right\}$ 

Antes de iniciarmos a prova propriamente dita,  vamos definir e fixar mais alguns fatos importantes referentes à teoria de homologia semialgébrica.

  •  Sobre triangulação
Se $X$ é um semialgébrico compacto em $\mathbb{R}^n$, então existem $|\mathcal{K}| \subset \mathbb{R}^n$ complexo simplicial finito e um homemorfismo  $\varphi: |\mathcal{K}| \rightarrow X$ tal que o gráfico de $\varphi$ é um conjunto semialgébrico em $\mathbb{R}^{2n}$ (definição de um aplicação semialgébrica) e tal triangulação pode ser escolhida compatível com uma família $X_1, X_2, \ldots, X_n$ de conjuntos semialgébricos em $X$. Isto significa que $\varphi^{-1}\left(X_i\right) = L_i$ subcomplexo de $\mathcal{K}$. Por outro lado, se X é ilimitado ou não contém todos os seus pontos de fronteira podemos obter uma versão semialgébrica da compactificação de Alexandrov:
 Existem, para X localmente compacto, um subconjunto semialgébrico $X^* \subset \mathbb{R}^{n+1}$ compacto, um mergulho  semialgébrico de $X$ em $X^*$ de forma que  $X^*-X = \left\{p\right\} \in \mathbb{R}^{n+1}$.

Portanto, de posse de uma triangulação de $X$ (localmente compacto) podemos definir a 

  • Homologia semialgébrica de Borel-Moore
      $H_i^{BM}(X,\mathbb{Z}_2 )$, se $X$ for compacto, é definido por  $H_i(X, \mathbb{Z}_2)$ e, se $X$ não for compacto, é definido por $H_i(X^*,X^*-X, \mathbb{Z}_2)$.

$i = 0,1, \ldots, dimX$.

Um comentário: $H_i(X, \mathbb{Z}_2)$ trata-se de um grupo de homologia simplicial (e um espaço vetorial!), induzido pelo quociente entre ciclos e bordos sobre complexo de cadeias $\mathcal{C}_i(X,\mathbb{Z}_2)$, que não depende da triangulação, ou seja, é invariante topológico. Por conseguinte, também independem da triangulação, grupos de homologia relativa induzidos pelo quociente natural entre os respectivos complexos de cadeias (considerando uma escolha compatível de triangulação).

Vamos agora a 3 resultados que serão usados na demonstração (todos os grupos de homologia considerados são com coeficientes em $\mathbb{Z}_2$):

1. Sejam $A \subset B$ semialgébricos compactos em $\mathbb{R}^n$. Temos que
 $H_q(A,B) = H_q^{BM}(A - B)$.


2. Sejam $U \subset V$, $V$ localmente compacto e $U$ subconjunto semialgébrico fechado de $V$. Então existe uma sequência exata longa

      $\ldots H_{q+1}^{BM} (V - U) \rightarrow H_q^{BM}(U) \rightarrow H_q^{BM}(V) \rightarrow H_{q}^{BM}(V - U) \rightarrow \ldots $
   

3. (Existência da classe fundamental) Seja $X$ um conjunto algébrico compacto de dimensão $d$ e considere $\phi:|\mathcal{K}| \rightarrow X$ uma triangulação semialgébrica de $X$. A soma de todos os $d$-simplexos de $\mathcal{K}$ é um ciclo não nulo com coeficientes em $\mathbb{Z}_2$, elemento de $H_d(X,\mathbb{Z}_2)$. Este elemento (que denotaremos por $[X]$) é independente da escolha da triangulação e é dito a classe fundamental de $X$.

 Vamos  agora à prova do teorema: Ah! Nessa altura, vale lembrar o que se deseja provar:

Teorema principal.
O complemento de um subconjunto algébrico de $\mathbb{R}^n$ não é homeomorfo a $\mathbb{R}^n$.

Prova:

Para nossos propósitos vamos tomar grupos de homologia reduzida $\tilde{H}$:

$H_0(|\mathcal{K}|) = \mathbb{Z}\oplus \tilde{H}_0(|\mathcal{K}|)$ e $\tilde{H}_i(|\mathcal{K}|) = H_i(|\mathcal{K}|)$ se $i > 0$.

Considere $V$ algébrico com $dimV < n$ e a seguinte sequência exata:

$\ldots \rightarrow H_i^{BM}(V) \rightarrow H_i^{BM}(\mathbb{R}^n) \rightarrow H_{i}^{BM}(\mathbb{R}^n - V) \rightarrow H_{i-1}^{BM}(V) \ldots $


Sabemos que $H_n^{BM}(\mathbb{R}^n) = \mathbb{Z}_2$ e $H_i^{BM}(\mathbb{R}^n)=0$ para $i < n$. Além disso,

$H_{dimV}^{BM}(V)$ é não trivial e $H_i^{BM}(V) = 0, \ i > dimV$.

Pela exatidão da sequência acima, obtemos ($0 < i < n$)

 $0 \rightarrow H_i^{BM}(\mathbb{R}^n-V) \rightarrow H_{i-1}^{BM}(V) \rightarrow 0$

E, portanto, $H_i^{BM}(\mathbb{R}^n - V) = H_{i-1}^{BM}(V)$, \   $0< i < n$     (I)

Para $i = n$, ficamos com o seguinte:

 $0 \rightarrow \mathbb{Z}_2 \rightarrow H_n^{BM}(\mathbb{R}^n-V) \rightarrow H_{n-1}^{BM}(V) \rightarrow 0$

Como os elementos dessa sequência podem ser vistos como módulos sobre um corpo (espaços vetoriais) temos que: $H_n^{BM}(\mathbb{R}^n-V) = \mathbb{Z}_2 \oplus H_{n-1}^{BM}(V)$ (II).


Nesse ponto, olhando para a equação (II), se fossem $\mathbb{R}^n$ e $\mathbb{R}^n-V$ homeomorfos, não poderia ser $dim V = n-1$ pois

 $ \mathbb{Z}_2 = H_n^{BM}(\mathbb{R}^n) = \mathbb{Z}_2 \oplus H_{n-1}^{BM}(V)$

E nem poderia ser  $0\leq p = dimV < n-1$ pois usando a equação (I) teríamos

$0 = H_{p+1}^{BM}(\mathbb{R}^n) = H_{p}^{BM}(V)$

Logo, $V$ deve ser $\emptyset$ e isto conclui a prova.

sábado, 1 de setembro de 2012

Complementar de curvas algébricas em $\mathbb{R}^2$ II

A postagem de hoje é destinada a apresentação de uma solução para o seguinte problema.


Problema. O complemento de um subconjunto algébrico de $\mathbb{R}^2$ não é homeomorfo a $\mathbb{R}^2$.

Solução. Seja p(x,y) um polinômio irredutível que não muda de sinal em $\mathbb{R}^2$. Mostraremos que o conjuntos dos zeros deste polinômio é finito. De fato, dado (a,b) ponto que anula aquele polinômio, temos que, para qualquer que seja o vetor (u,v), a função real de uma variável real $t$ dada por

f(t)=p(a+tu,b+tv)

possui um ponto de mínimo em t=0, portanto, f'(0)=0, ou seja, o gradiente de  p(x,y) no ponto (a,b)  é ortogonal ao vetor (u,v). Desde que escolhemos o vetor (u,v) arbitrariamente, constatamos que o gradiente de p(x,y) se anula no ponto  (a,b).  Segue do Teorema de Bezout que  o conjunto dos zeros de p(x,y) é finito.

Suponhamos que X seja definido por um polinômio p(x,y). Isto é, X é o conjunto dos pontos (x,y) em que p(x,y)=0. Se os fatores irredutíveis de p(x,y) não mudam de sinal em $\mathbb{R}^2$ temos que X é um conjunto finito (foi o que vimos acima). Assim, o complemento de X  não é simplesmente conexo.

Então, resta-nos supor que p(x,y) possui um fator irredutível q(x,y) que muda de sinal em $\mathbb{R}^2$. Desta forma, os conjuntos abaixo
  • pontos (x,y) em que q(x,y) é positivo
  • pontos (x,y) em que q(x,y) é negativo
são abertos, disjuntos e não-vazios. Como o complemento de X é um subconjunto denso do plano que está contido na reunião dos conjuntos acima, temos que ele não é conexo.

C.Q.D.

Antes de finalizar esta postagem, gostaria de informar que o problema acima possui uma versão em dimensão n, quero dizer, temos o seguinte resultado em $\mathbb{R}^n$.

Teorema. O complemento de um subconjunto algébrico de $\mathbb{R}^n$ não é homeomorfo a $\mathbb{R}^n$.

Recentemente, meu aluno de mestrado, Rodrigo Mendes Pereira, escreveu sua dissertação sobre Homologia Semialgébrica sobre corpos reais fechados e provou uma versão do teorema acima para $\mathbb{K}^n$, em que $\mathbb{K}$ é um corpo real fechado. Por isto, convidei o Rodrigo a escrever uma postagem para este blog  trazendo uma demonstração para o teorema acima. Já estamos esperando, Rodrigo!

sábado, 11 de agosto de 2012

Complementar de curvas algébricas em $\mathbb{R}^2$


Eu e Renan (meu aluno de iniciação científica), recentemente, quando estudávamos o Teorema de Newman (ver abaixo), deparamo-nos com o seguinte problema: se removermos um subconjunto algébrico, próprio, do plano euclidiano o resultado não será homeomorfo ao plano.

Antes de tecer mais alguns comentários sobre o problema acima, gostaria de enunciar o Teorema de Newman

Teorema (Donald J. Newman 1969). Se uma aplicação polinomial $\mathbb{R}^2\rightarrow\mathbb{R}^2$ é injetiva, então ela também é sobrejetiva.

O teorema acima é parte de uma belíssima história na matemática que tem como palavra-chave “Teorema de Ax-Grothendick”. Se você quiser conhecer um pouco dessa história, sugiro o post publicado por Terence Tao em seu blog  What’s new (aqui).

De volta ao primeiro problema descrito acima, gostaria de observar que existe subconjunto semi-algébrico, próprio, do plano euclidiano de sorte que seu complementar continua homeomorfo ao plano. Com efeito, o complementar de uma semi-reta no plano é homeomorfo ao plano. Ora, se não fosse assim, o Teorema de Newman seria consequência imediata desse fato.  Infelizmente, a vida não é tão fácil! Ou não, como diria o Renan.

Então, finalizo esta postagem prometendo trazer uma solução bonita para o seguinte

Problema: Se $X\subset\mathbb{R}^2$ é subconjunto algébrico, próprio, então $\mathbb{R}^2\setminus X$ não é homeomorfo a $\mathbb{R}^2$.


domingo, 15 de julho de 2012

Triângulo Russo


Hoje encontrei um amigo que há muito tempo não via, Professor Ivair. Realmente, foi uma grande satisfação encontrá-lo novamente. Vocês podem estar perguntando por que eu relataria aqui um reencontro com um amigo. Já explico o porquê de um reencontro com  o Professor Ivair gerar uma postagem no Happy Hour Matemático. O negócio é o seguinte: ele conhece muitos e bons problemas de matemática, coleciona-os em apostilas e tem dezenas delas. Ele é, de fato, uma boa fonte para este blog. 

Não há como eu me encontrar com ele e não lembrar de um problema casca grossa. Confesso que hoje não foi diferente! Lembrei-me de um famoso problema de geometria plana conhecido como o Triângulo Russo, o qual, também, foi-me apresentado pelo Ivair em uma de nossas conversas na UFC. 

Abaixo segue o Problema do Triângulo Russo.

Sabendo que AB=AC, encontre o valor do ângulo x.




Até a próxima! 

sexta-feira, 6 de julho de 2012

12th International Workshop on Real and Complex Singularities

International Workshop on Real and Complex Singularities é um congresso de matemática promovido pelo Instituto de Ciências Matemáticas e Computação da USP que ocorre a cada dois anos na cidade de São Carlos (SP). O tradicional evento é marcado pela presença de renomados pesquisadores das áreas de Singularidades, Geometria Algébrica e Teoria de Bifurcações, assim como pela presença maciça de jovens pesquisadores/alunos brasileiros e estrangeiros. A edição deste ano celebrará o 60° aniversário do Professor Shyuichi Izumiya e ocorrerá na semana 22-27 de julho (link).


Vale a pena conferir!

sábado, 9 de junho de 2012

Desigualdade de Weyl


Em 2007, um conhecido stick, um stick que de certa forma é observado pelos seus pares,  um tipo que se expressa com uma mão no bolso de sua calça e a outra livre fazendo movimentos como de um maestro que comanda uma orquestra sinfônica (acho que não sei defini-lo!), apresentou-me o seguinte problema:


É bem conhecido que os autovalores de uma matriz simétrica variam continuamente com a matriz. Podemos afirmar que essa variação é lipschitziana?

Aceitei o desafio e, juntamente com um colega de trabalho, obtive uma resposta positiva para a pergunta acima. Contudo, a solução obtida era muito feia e, para mim, aquela prova merecia ser esquecida. Antes de esquecê-la, refleti bastante sobre a seguinte frase de Michel Atiyah

"Existe teorema bonito com prova feia, mas não existe teorema feio com prova bonita".

Certamente, a dependência Lipschitz dos autovalores de uma matriz simétrica é um teorema bonito e, embora Sir Michael Atiyah trouxesse a permissão de termos provas feias para teoremas bonitos, eu sentia que aquele não seria o caso em que eu deveria me conformar com aquela prova, porque ela era demasiadamente feia. 

Pouco tempo depois, ministrando uma disciplina de álgebra linear, conheci uma prova adequada para a variação lipschitziana dos autovalores de matrizes simétricas.

O objetivo de hoje é mostrar de uma forma muito elegante a Desigualdade de Weyl, desigualdade que responde positivamente à pergunta daquele stick legal.

A partir daqui, passo à apresentação direta da Desigualdade de Weyl e sua prova. 

Inicialmente, lembramos que o espaço das matrizes de ordem $n$ admite uma norma definida da seguinte maneira: dada uma matriz $A$ de ordem $n$, $$\|A \|= max\{|Ax| \ : \ x\in\mathbb{R}^n, |x|=1\}.$$
No caso em que $A$ é uma matriz simétrica é muito fácil mostrar que $\|A\|$ coincide com o maior valor absoluto dos autovalores de $A$.

Antes de enunciarmos a desigualdade de Weyl, consideremos mais algumas notações. Para cada matriz simétrica $M$ de de ordem $n$, estabelecemos que o i-ésimo autovalor de $M$, denotado por $\lambda_i(M)$, respeita a seguinte ordem  $$\lambda_1(M)\geq\cdots\geq\lambda_n(M).$$
Utilizamos $x\cdot y$ para representar o produto interno euclidiano entre os vetores $x$ e $y$ em $\mathbb{R}^n$.

Desigualdade de Weyl
Sejam $A$ e $B$ matrizes simétricas de ordem $n$. Então, vale a seguinte desigualdade: $|\lambda_i(A)-\lambda_i(B) | \leq \| A-B \|, \ i=1,\dots,n$.


Prova. Sejam $\{x_1,\dots,x_n\}$ e $\{y_1,\dots,y_n\}$ bases ortonormais de $\mathbb{R}^n$ em que $x_i$ é autovetor de $A$ associado ao i-ésimo autovalor de $A$ e $y_i$ é autovetor de $B$ associado ao i-ésimo autovalor de $B$. Para cada $j=1,\dots,n$, seja $z_j$ vetor unitário na interseção dos subespaços $span\{x_1,\dots,x_j\}$ e $span\{y_j,\dots,y_n\}$. Como $\lambda_j(A)\leq Az_j\cdot z_j$ e $\lambda_j(B)\geq Bz_j\cdot z_j$, obtemos:

$\lambda_j(A)-\lambda_j(B)\leq \lambda_1(A-B)$.

Substituíndo $A$ por $-A$ e $B$ por $-B$ na desigualdade acima, obtemos:

$\lambda_j(A)-\lambda_j(B)\geq \lambda_n(A-B)$.

Juntando as duas últimas desigualdades, obtemos a almejada desigualdade de Weyl.
Final da Prova


domingo, 27 de maio de 2012

Um tipo de desigualdade isoperimétrica. Solução.

O objetivo da postagem de hoje é apresentar uma prova para a proposição abaixo.

"Se uma curva divide o quadrado unitário em dois pedaços, então o comprimento da curva é maior do que ou igual ao valor da área de um desses pedaços."



Prova. Seja $\gamma$ uma curva que divide o quadrado unitário em pedaços A e B. Mostremos que o comprimento comp($\gamma$) dessa curva é maior do que ou igual ao mínimo das áreas {area(A),area(B)}.


Desde que o quadrado tem área unitária, podemos supor que o comprimento da curva é menor do que 1. 

Suponhamos que area(B) seja maior do que comp($\gamma$). Nesse caso, considerando G como sendo a projeção vertical do quadrado sobre a sua base (veja figura abaixo), temos que area(B) é menor do que ou igual à área do cilindro de base G(B) e altura 1 e, portanto, area(B) é menor do que o comprimento do intervalo G(B). 


Por outro lado, desde que G é uma projeção ortogonal, comp($\gamma$) é maior do que ou igual ao comprimento do intervalo G($\gamma$). Então, existe uma reta vertical que não intersecta $\gamma$ e intersecta B.

Se, também, temos que area(A) é maior do que comp($\gamma$), utilizando a projeção ortogonal F do quadrado sobre a sua lateral direita (veja figura acima), com uma análise semelhante à que fizemos acima, concluímos que existe uma reta horizontal no quadrado que não intersecta $\gamma$ e intersecta A. Desde que retas verticais sempre intersectam retas horizontais no quadrado, temos pontos de A e B que podem ser conectados por um arco poligonal no quadrado que não cruza a curva $\gamma$, resultando que A e B são partes do quadrado que não estão separadas pela curva $\gamma$.

segunda-feira, 21 de maio de 2012

Um tipo de desigualdade isoperimétrica


Hoje, trago um problema do tipo "desigualdade isoperimétrica".

Problema. Se uma curva divide o quadrado unitário em dois pedaços, então o comprimento da curva é maior do que ou igual ao valor da área de um desses pedaços.

De fato, apesar de apresentar a proposição acima como um problema do tipo "desigualdade isoperimétrica", ainda não é claro para mim que essa proposição decorre de algum teorema clássico de desigualdade isoperimétrica. Isso, eu realmente gostaria de saber. Ideias são muito bem-vindas!

Na próxima postagem, trarei uma solução bacaninha para o nosso problema de hoje. Espero!   

segunda-feira, 30 de abril de 2012

Teorema de Sylvester e Gallai


"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).

quinta-feira, 19 de abril de 2012

Um dia de russos na polícia federal


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.

sábado, 31 de março de 2012

O Problema de Monty Hall

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. 


Ah! Vale a pena ver esse filme.




segunda-feira, 12 de março de 2012

... múltiplos irados...


por Bill Bastos e Breno Sampaio


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?"

A questão acima permanece aberta!

sexta-feira, 17 de fevereiro de 2012

Pontos de acumulação e aplicação de um teorema bacana

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 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!