Arquivo mensais:agosto 2012

O teorema do sanduíche de presunto

Rookie

Comentei em outro post sobre um de meus teoremas favoritos, o das quatro cores, mas, em termos de nomenclatura, o que leva a taça é o teorema do sanduíche de presunto, ou do misto quente.

É um resultado bem geral e impressionante, de um ramo da matemática chamado “teoria da medida”, que estuda o conceito de “tamanho” dos objetos, quais podem ser medidos e o que seria essa medida. Essa área possui diversos resultados interessantes (como a relação do axioma da escolha com a impossibilidade de medir todos os conjuntos, ou com o aparecimento de aparentes paradoxos), sendo um deles esse teorema bem poderoso que nos permite dividir em duas metades bastante coisa.

Teorema (de Stone-Tukey, ou do sanduíche de presunto): dado um sanduíche com qualquer distribuição de pão, presunto e queijo, sempre é possível, com um único corte, dividir o sanduíche em duas metade contendo cada uma metade do presunto, metade do queijo e metade do pão.

Eu poderia formular como “um sanduíche de três ingredientes”, mas você seria tentado a pensar no bauru, e o pão conta como ingrediente. Teríamos, para dar certo, que tirar o tomate, e, como se sabe, por teorema, bauru sem tomate é misto.

O teorema é muito geral, vale para qualquer distribuição de ingredientes e qualquer formato de sanduíche. De forma geral, dizemos que é possível com um único corte plano dividir três elementos em pedaços de mesma medida. O teorema não nos dá o corte, tampouco diz que ele é único, mas garante que existe ao menos um, e isso já é bem impressionante.

Em duas dimensões, podemos chamar esse de teorema da panqueca. Cobrindo uma panqueca com geléia e manteiga de amendoim, existe sempre um corte, uma linha, que divide a panqueca em duas metades contendo, cada uma, metade da geléia e metade da manteiga de amendoim.

Esse resultado certamente se aplica a um caso discreto, não contínuo. Na falta de exemplos, tomo uma piscina de bolinhas com três cores de bolas. O teorema nos garante que existe sempre ao menos uma maneira de “fatiar” a piscina, ou seja, há um plano que a corta, de forma a separá-la em duas metades contendo cada uma a mesma quantidade de cada cor de bolinha. O caso em duas dimensões pode ser visto nessa figura:

Nesse caso, possuo, em cada metade, 7 vermelhas e 8 azuis. Esse corte não é necessariamente único, o teorema se encarrega apenas da existência.

Que fique, portanto, como conclusão do teorema isto: não há desculpa para pegar a maior metade, pois, dado um misto quente, sempre existe uma maneira justa de, com uma faca, reparti-lo com justiça.

A hipocicloide do futuro

Rookie

Essa semana, assisti ao filme Total Recall, que, pelos motivos mais misteriosos, resolveu ser traduzido em português para O Vingador do Futuro (ainda, poderia ser pior, eu esperava algo como Rebobinado). Esse post contém um leve spoiler, nada que não seja visto nos primeiros dez minutos de filme: ele se passa em um futuro distante onde a humanidade usa, como meio de transporte, uma forma de trem que atravessa o centro da Terra. Fiquei encantado com o meio de transporte, porque ele inspira diversas questões bem interessantes, que vamos tratar aqui.

A primeira é o que considerei um pecado no filme: a gravidade é considerada binária, ou seja, ou é ativada, ou desativada. A ideia é legal, tentar lembrar o espectador de que no centro do planeta a gravidade é zero, mas ele esquece de lembrar um detalhe: ela não se torna completamente zero no núcleo e volta a ser 9,8m/s² logo em seguida, ela decresce linearmente (considerando a Terra de densidade uniforme) até atingir o zero e depois volta a crescer conforme nos afastamos do centro. Isso resultaria em personagens ficando mais e mais leves até não sentirem a gravidade e, então, começarem a ser atraídos pelo teto ao invés de pelo chão.

Vou explicar melhor. Imagine nosso herói cavando um buraco na Terra. Ele cava diversos quilômetros e atinge um terço do caminho, ficando embaixo da superfície como na figura:

A gravidade, para ele, será equivalente a estar pisando em um planeta cujo raio é o que falta para ele chegar ao centro da Terra, ou seja, um planeta bem menor. Em outras palavras, se ele estiver a essa profundidade, a gravidade que sentirá será como estar pisando em um planeta menor, desenhado em vermelho:

Isso parece estranho, pois simplesmente ignorar toda a massa que não está no vermelho parece desonesto, ela ainda exerce força gravitacional sobre nosso herói. Mas porque as equações da gravitação são tão lindas, um fenômeno muito interessante acontece. Certamente há muita coisa além do vermelho puxando nosso herói, mas o que está acima de sua cabeça o puxa para cima, enquanto o que está do outro lado do planeta vermelho o puxa para o outro lado, de tal forma que eles se cancelam exatamente e a única massa que efetivamente puxa nosso herói é a que está no planeta vermelho. Se você achar isso estranho porque parece haver muito mais massa o puxando para a direção de seus pés (e há, de fato), deve se lembrar que essa massa também está mais distante e isso conta muito na gravitação. Confie em mim ou faça a conta, o que não está no vermelho até puxa, mas nesse cabo de guerra todas as forças se anulam mutuamente.

Assim, a gravidade tende a diminuir de forma gradual até o centro, como se o planeta ficasse cada vez menor. No filme, aproximando-se do núcleo, a gravidade torna-se zero e depois volta a ser o que conhecemos, há vários problemas com isso.

Os que conhecem o princípio da equivalência podem dizer: “Ah, Ricardo, a máquina pode estar acelerando no sentido certo para ajudar aquela gravidade fraca a se tornar forte”, e eu até concordo que esse pode ser o caso para quando o trem está se afastando do centro: uma aceleração no mesmo sentido do movimento poderia compensar a falta de planeta; mas na descida não há desculpa. É realmente crível que uma nave dessas aceleraria contra o sentido de seu trajeto apenas para manter seus tripulantes, que são fixos às cadeiras por mais travas que brinquedos da Disney, em gravidade 9,8m/s²? Não dá para engolir, o filme realmente acha que a gravidade é sempre a mesma até o núcleo, onde, do nada, se torna zero.

Mas não foi apenas isso que me deixou intrigado. As regiões conectadas pelo trem parecem ser Inglaterra e China (Wikipédia diz Austrália), se eu entendi o filme direito, mas nenhuma dessas hipóteses explica a razão do trem ter que passar pelo núcleo da Terra onde há gravidade zero. Todo bom engenheiro podendo cavar um túnel pelo interior da Terra iria se preocupar em cavar o melhor possível, e a pergunta natural é qual o formato do melhor túnel possível.

Vamos primeiro definir qual é o melhor túnel como aquele que te leva mais rápido de um lado para outro. Como dinheiro e recursos não parecem ser problemas para esse povo, queremos minimizar o tempo de voo, ou de queda. Essa é uma pergunta difícil e é um exercícios fascinante aos que gostam de mecânica analítica, um dos melhores do Goldstein, cuja solução pode ser encontrada aqui. A melhor curva que liga dos pontos passando pelo interior da Terra, aquela capaz de transportá-los no menor tempo possível, é uma hipocicloide.

Essa curva pode ser desenhada se você conseguir traçar a trajetória de um ponto em um cilindro menor que rola dentro de um maior. Para ligar três pontos sobre a superfície terrestre que estão na mesma longitude e são igualmente distantes, a melhor curva é a desde gif da Wikipédia:

E como vocês podem ver, essa curva passará pelo centro apenas se os pontos forem antipodais, ou seja, se o trem tiver de conectar um lugar ao outro lado do mundo, seu ponto diametralmente oposto na Terra. Não preciso nem de um site para saber que Inglaterra e Austrália não são opostos; o oposto da Austrália é o norte do Atlântico, sendo o da Inglaterra o Pacífico! Em honra ao filme, a escolha não é tão ruim, mas Sidney ainda está a 3.000Km do oposto de Londres no globo.

Assim, podemos nos divertir pensando: qual seria a profundidade máxima desse túnel, e quanto seria sua menor gravidade possível. Supondo as capitais ligadas Sidney e Londres, podemos usar a solução do problema acima e calcular que o túnel atinge uma profundidade de aproximadamente 5.400Km, faltando ainda bons 1.000Km para se atingir o centro da Terra. Precisamos apenas considerar a gravidade exercida pelo núcleo em nosso herói, mas aí eu vou chamar uma precisão importante, vamos abandonar a hipótese de que a Terra é homogênea e estudar a composição do núcleo terrestre para calcular essa gravidade.

Com raio de 1.000Km, estamos falando da parte mais interna do núcleo, que é sólida e composta essencialmente de ferro e níquel. Sua densidade não é bem determinada, mas confio no site desse professor que diz entre 12,6 e 13g/cm³. A massa de uma esfera desse tamanho (1.000Km) com essa densidade é de 5,5.10^{22}Kg. A massa da Terra total é 6.10^{24}Kg (aproximadamente 100 vezes maior que a do núcleo) e o raio total é 6,4 vezes o raio do núcleo que calculamos. Fazendo uma conta rápida, percebemos que a menor gravidade atingida por nosso herói é de 40% a gravidade total da Terra. O valor que esperávamos era de 17%, se a gravidade decrescesse linearmente, mas devemos levar em conta o fato do núcleo ser muito mais denso que o resto da Terra. Assim, um túnel que liga Londres a Sidney, se construído pelo melhor caminho possível (o que conduz os passageiros no melhor tempo), atinge uma gravidade mínima de 40%, que é entre duas a três vezes a gravidade da Lua.

Curiosamente, o sul da América do Sul e a Ásia do leste são as únicas massas continentais urbanas antípodas, sendo a única explicação para o filme a de retratar uma metrópole opressora e cruel que não pode ser outra além de Porto Alegre, Buenos Aires, Santiago ou Montevideo.

Esses três parágrafos anteriores são exagero de minha parte. O filme queria gravidade zero pela trama, as belas cenas de ação, eu entendo. Não sou chato em filmes, juro. Quando me sento na cadeira do cinema, o Super-Homem pode voar e eu não ligo, em Lost, a ilha podia até flutuar, desaparecer, rodar que eu não me espantaria; mas se um filme tenta passar a imagem de cientificamente correto, tem que cumprir o que promete. Se explosão barulhenta no espaço é crime na ficção científica, gravidade binária, por mais relevante que tenha sido para a trama, fica bem difícil de engolir.

O corolário do relógio cruel

Geek

Hoje falamos de álgebra, mas não aquela álgebra linear, coisa séria, de gente grande. Comento com vocês um resultado interessante e bonito da teoria de grupos, chamado teorema de Lagrange. E antes de enunciá-lo, apresento seus elementos, vamos conversar sobre o que é um grupo.

A definição formal não é difícil, mas prefiro definir com palavras a símbolos. Um grupo é um conjunto de elementos que podem ser “somados”, não importando muito o que essa ideia de soma seja. É importante que haja um elemento do conjunto “eleito” como o elemento neutro, aquele que, somado a qualquer um, não afeta esse qualquer um. Na soma convencional, ele é o zero. Na multiplicação, ele é um 1. Nas multiplicação de matrizes, é a identidade. Também é importante que você, tendo somado um elemento, sejá capaz de “subtrai-lo”, ou seja, realizar a operação inversa. Na soma tradicional, o inverso de a é -a, na multiplicação, é 1/a. Nas matrizes, teremos a matriz inversa, o que nos prova que as matrizes não formam um grupo na multiplicação delas. Por fim, queremos que o conjunto seja fechado, ou seja, é impossível, com somas de gente do conjunto, obter alguém de fora dele.

Exemplos de grupos são fáceis de se encontrar: os inteiros com a operação soma, os reais sem o zero com a operação vezes, o conjunto de matrizes quadradas inversíveis de ordem n e os conjuntos de restos de divisão. Esse último merece alguma atenção, pois não só tem aplicações interessantes como é crucial em algumas áreas dessa matéria.

Ao fazer uma divisão por, digamos, 5, temos cinco opções como resto, 0, 1, 2, 3 e 4. Se um número dividido por 5 deixa resto 3 e outro número deixa resto 3, a soma deles deixará resto 1, essa será a regra de nosso grupo “resto de 5”, denotado \mathbb{Z}/5\mathbb{Z}. É como se você somasse números normalmente e, a cada vez que eles passam 5, você tira 5 do número. Nesse grupo, 1+1=2, 2+2=4 e 3+3=1. É fácil ver que todos possuem inverso, sendo, por exemplo, o inverso de 3 o número 2, o inverso de 4 o número 1 e assim por diante. Em particular, ele é um grupo finito, e por isso gosto dele. Neste post, vou falar apenas de grupos finitos, eles já atingem uma complexidade suficiente para deixar qualquer matemático feliz.

Se você acha o grupo descrito acima artificial, veja seu relógio. Ele é o grupo \mathbb{Z}/24\mathbb{Z}, pois 3+3=6, 6+6=12, mas 12+12=0, somar doze horas ao meio-dia não é ir à hora vinte e quatro, é voltar à meia-noite, hora zero.

E se falamos de grupos, podemos falar de subgrupos. Algum subconjunto de nosso grupo pode ser, em si só, um grupo. No caso do relógio, os elementos 0, 3, 6, 9, 12, 15, 18 e 21 formam um subgrupo. Eles herdam a operação do grupo original e operados entre si continuam entre si, não há como você, somando esses horários, atingir um horário que não esteja nessa lista. O grupo total possui 24 elementos, e esse subgrupo possui 8 elementos. E o que o teorema de Lagrange nos diz é isso:

Teorema (de Lagrange): O número de elementos de um subgrupo de um grupo finito é sempre um divisor do número total de elementos do grupo.

No nosso caso, teremos que 8 é um divisor de 24. Como consequência, podemos perceber que todo grupo que possui um número primo de elementos não possui subgrupo que não seja ou ele mesmo, ou um subgrupo composto apenas pela identidade. Por mais elaborada que seja a construção de seu grupo, se ele possui 11 elementos, não possui nenhum subconjunto que em si seja um grupo, e esse é um resultado bem divertido.

A prova desse teorema não é tão trivial para quem começou agora a ver grupos, então dou apenas uma ideia da demonstração. Se G é um grupo finito e H \subset G é também um grupo com a mesma operação, logo é um subgrupo, então vamos chamar os elementos de H de h, h_2, h_3\ldots. Se H=G, o teorema está provado para esse caso, então vamos supor que H \neq G, tomemos um g\in G que não está em H. Note que se g\not\in H, então a operação de g com qualquer elemento de H também não está em H. Por quê?

Sabemos que H é um grupo, então todos lá possuem inverso. Se gh_i = h_j, poderíamos operar os dois lados da equação com h_i^{-1} pela direita e obter g = h_jh_i^{-1}. Se escrevemos g como uma composição de elementos de H, ele tem que estar em H, o que é absurdo por hipótese.

Intuitivamente, a ideia é pensar em G como um cilindro e H como um disco desse cilindro, como essa figura mostra:

O subgrupo H gera, para cada elemento que não pertence a si, todo um anel novo de elementos, apesar de eu hesitar em chamar isso de anel porque, em álgebra, esse nome já é usado para outra coisa, então prefiro chamar de círculo. Ora, dá pra perceber que todo elemento de G pertencerá ou a H ou a um desses círculos formados por H. Todos os círculos possuem a mesma quantidade de elementos (pois se gh_i = gh_j, podemos cortar g dos dois lados e provar que h_i = h_j), logo, o número total de elementos de G deve ser um múltiplo do número de elementos de H.

Esse teorema é um jeito de interessante de entender a razão de nossas horas serem contadas em 12 ou 24, esses números possuem muitos divisores! Como se houvesse um corolário do relógio cruel: não são feitos relógios com um número primo de horas, como, por exemplo, esse relógio cruel:

Nesse caso, nenhuma hora inteira seria sensata para se prescrever um medicamento, pois todas elas atravessariam todo o relógio antes de voltar para a mesma hora. Em outras palavras, percorrer este relógio de duas em duas, três em três ou quatro de quatro horas atravessará todo o relógio antes de repetir a primeira hora, pois o número de elementos de qualquer subgrupo deve ser um divisor do número de elementos do grupo. Isso faria o paciente acordar em todas as horas inteiras que deveria estar dormindo, e o mesmo aconteceria se, em nossos relógios, um médico receitasse um comprimido de sete em sete horas. Pode parecer uma aplicação estúpida, mas não é; o fato de nossa divisão do dia em vinte e quatro horas tem como razão histórica a grande quantidade de divisores que possui.

Você certamente pode chegar a essa mesma conclusão usando propriedades elementares de MMC e MDC, mas essa visão, mais abrangente dos grupos finitos, é capaz de nos levar a abstrações mais profundas e a grupos mais complexos, alguns nem numéricos, mas este resultado ainda vale. Muita coisa é grupo, e, em todos os finitos, vale o teorema de Lagrange.

Férias

Geek Hardcore Rookie

Nesse post, declaro férias do blog por catorze dias. Depois de seis meses em uma frequência de mais de um post por semana, preciso de um tempo para respirar e colocar os posts em dia sem comprometer a qualidade. Estou de férias, e isso significa que a inspiração é fraca enquanto não estou estudando e trabalhando. Férias são férias, e isso inclui dos textos desse blog.

Aos que ficam, ou que passam por aqui pela primeira vez, deixo uma lista de meus quatro posts favoritos, caso ainda não os tenham visto:

No cassino de Parrondo.

A pior forma de governo.

Aniversários.

Informação e demônios.

Até dia 17.