O princípio do pombal

Rookie

Em física e matemática, é bem comum encontrarmos princípios que parecem óbvios com consequências complicadas. Meu exemplo favorito é a relação conhecida como equação mestra na física estatística que, se lida em português, seria: “o quanto variou é o quanto entrou menos o quanto saiu”. Por mais evidente que isso seja, essa equação toma formas cabulosas em situações não muito complicadas e exige bastante suor para ser resolvida.

Mas o assunto de hoje não é a equação mestra, mas outro princípio, talvez ainda mais simples: o princípio da casa dos pombos, ou princípio do pombal.

Princípio da casa dos pombos: se há mais pombos que casas em um pombal, alguma casa terá mais de um pombo.

Eis uma aplicação desse princípio:

E por mais óbvio que ele pareça, não é nada inútil se lembrar dele como técnica de demonstração de resultados bem interessantes. Um deles, meu favorito, é uma espécie de jogo com sequências. Para ilustrar, imagine uma rua com $n$ casas. Cada casa deve possuir um número, e você pode escolher o número que quiser. Eu afirmo que existe um grupo de casas vizinhas cujos números, somados, resultam em um múltiplo de $n$.

Vejamos um exemplo. Imagine treze casas que possuem os seguintes números: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 e 14. Se houvesse uma casa com o número 13, ela seria sozinha o múltiplo de 13 que quero, isso não me serve de muita coisa. Note que, nessa rua, temos os vizinhos 5, 6, 7 e 8, e 5+6+7+8=26, que é um múltiplo de 13.

Mas podemos pegar sequências mais complicadas, como, por exemplo, um antigo telefone meu: 41921561. Eu tenho certeza absoluta de que existem números vizinhos que, somados, resultam em um múltiplo de oito (que é o tamanho da sequência). Basta caçar um pouco para encontrar que 4+1+9+2=16.

Ou, ainda, tomemos essa permutação de meu RG: 158313734. Cacemos os vizinhos que somados dão um múltiplo de nove, e uma leve busca nos leva a 5+8+3+1+3+7=27. Você certamente pode encontrar combinações mais simples, eu não disse que era única, apenas que existe.

Esse resultado, que é um divertido jogo quando se está profundamente entediado em uma sala de espera ou durante uma viagem de trem, é provado com o princípio do pombal. Para tal, tome sua sequência de tamanho $n$, da forma $a_1,a_2,\ldots a_n$. Pense agora em todas as possíveis sequências com a mesma ordem dessa sua original que começam no $a_1$, ou seja, as sequências:

\[a_1\]

\[a_1,a_2\]

\[a_1,a_2,a_3\]

E assim por diante. Pense agora na soma dos elementos delas. Se alguma dessas somas já dá um múltiplo de $n$, nosso problema está resolvido, então vamos supor o pior dos casos, nenhuma delas é um múltiplo de $n$. Assim, a soma dessas sequências, dividida por $n$, deve dar algum resto, e haverá $n-1$ possibilidades de resto.

Ainda em um exemplo, se minha sequência possuísse quatro elementos, as somas dessas subsequências teriam que ter resto ou 1, ou 2, ou 3. Se o resto fosse zero, seria divisível.

Como você tem $n$ sequências possíveis e apenas $n-1$ restos possíveis, então, pelo princípio do pombal, terá, necessariamente, duas sequências diferentes cuja soma tem o mesmo resto na divisão por $n$. Ora, subtraia uma da outra que você terá uma sequência de vizinhos cuja soma, dividida por $n$, possui resto zero, logo, é divisível!

Para entender melhor, vou aplicar esse raciocínio a uma sequência específica: 1 2 1 3 6. As subsequências possíveis são 1, 1 2, 1 2 1, 1 2 1 3 e 1 2 1 3 6. Suas somas serão, respectivamente, 1, 3, 4, 7 e 13. Note que, dividindo por 5, esses números produzem respectivamente resto 1, 3, 4, 2 e 3. A segunda e a última sequência possuem o mesmo resto! Então tirando a segunda da última teremos os elementos 1 3 6 que, somados, dão 10, um múltiplo de 5.

Não sei se ficou claro, na verdade, acho que ficou confuso, mas vou deixar assim enquanto não encontro maneira melhor de escrever. Provar o princípio do pombal, no entanto, me parece mais difícil que esse resultado que acabei de enunciar, talvez usando algum resultado dessa parte mais fundamental de teoria dos conjuntos, propriedades com bijeções, injeções e sobrejeções, a noção de cardinalidade, teria que pensar um pouco. Por enquanto, fica o resultado das sequências, das casas, e a demonstração dos pombos.

2 respostas

Fogo e chama

Rookie

Um dia desses, tive vontade de escrever um post sobre o fogo. Sempre fui fascinado pela chama, o brilho, o calor, seu movimento. Não conseguiria, contudo, escrever nada mais didático que esses dois vídeos combinados:

[youtube http://www.youtube.com/watch?v=5ymAXKXhvHI]

[youtube http://www.youtube.com/watch?v=ITpDrdtGAmo]

Enjoy.

Deixe um comentário

Coleção completa

Geek

Quando era criança, fui atingido pela mania dos tazos da Elma Chips como todos os meus colegas. Abria o salgadinho antes mesmo de chegar à aula, longe ainda do recreio, e recolhia o precioso prêmio do pacote: um disco plástico que servia de moeda de aposta e demonstração de habilidade no intervalo. Eu não era muito bom nisso, e não tinha tantos amigos, então minha principal fonte de Tazos eram o fandangos.

Via colegas com tubos repletos de tazos, coleções completas, era invadido por essa inveja e, talvez mais, por uma pergunta séria: como aquilo era possível? Eu colecionava havia meses e não chegara perto da metade da coleção, possuía muitos repetidos e aquele do Papa-Léguas era mais difícil de encontrar que filhote de pomba. Não imaginava como aquilo era possível, culpava os pais do garoto sortudo, deviam ter comprado caminhões de baconzitos, e, no fundo, queria saber: de quantos fandangos eu precisaria para completar minha coleção?

Essa pergunta está mal-feita, vamos melhorá-la. Mais interessante seria perguntar: qual o número médio, o valor esperado, de salgadinhos que preciso comprar para completar minha coleção? Em outras palavras, a partir de qual número de fandangos é mais provável que eu já tenha a coleção completa que o contrário? E, como pergunta bônus, quão improvável se torna, a partir desse número, não obter os preciosos tazos?

Havia tazos mais raros, é verdade, mas a pergunta já está bem difícil, então tomo como hipótese que a chance de tirar qualquer um dos tazos é a mesma. E para continuar, precisamos primeiro saber quantos são eles, e eis a coleção toda:

Se você está interessado na resposta, mas não conhece tanto de probabilidade, o que segue não será tão interessante (vou fazer as contas, é o que faço da vida, não consigo evitar). Mas você pode pular para o final do post e ver as conclusões sem culpa, se confiar em mim. Se, no entanto, você entende de probabilidade, jamais confie em mim. Suponha que eu já tenha $ k$ tazos diferentes, sendo $ n$ possíveis, a chance de eu tirar um repetido é $ \frac{k}{n}$. Assim, a probabilidade de eu precisar de exatamente $ s$ salgadinhos para tirar um diferente é $ \left(\frac{k}{n}\right)^{s-1} \left(1-\frac{k}{n}\right)$, que é uma parte a chance de eu tirar $ s-1$ repetidos e outra parte, no $ s$-ésimo salgadinho, tirar um diferente. Essa é $ P(s)$, a chance de eu precisar de $ s$ fandangos para tirar meu tazo diferente. Para calcular o valor esperado de salgadinhos até o próximo tazo diferente, ou seja, de $ s$, basta tomar:

\[ \sum_{s\geq 0}P(s).s=\sum_{s\geq 0}\left(\frac{k}{n}\right)^{s-1}\left(1-\frac{k}{n}\right).s=\frac{1}{1-\frac{k}{n}}\]

Essa última passagem fiz na malandragem, vale a pena explicar. Vou chamar $ \frac{k}{n}$ de $ x$ porque digitar essas coisas no WordPress cansa. Vou aplicar a distributiva, manobrar os índices e converter tudo em uma progressão geométrica de soma bem fácil:

\[\sum_{s\geq 0}x^{s-1}\left(1-x)\right).s=\sum_{s\geq 0}x^{s-1}s-\sum_{s\geq 1}x^s.s=\sum_{s\geq 0}x^s(s+1)-\sum_{s\geq 0}x^s.s=\sum_{s\geq 0}x^s=\frac{1}{1-x}\]

Então o número esperado de salgadinhos que devo comprar é a soma dos salgadinhos esperados para cada tazo que vou tirando, ou seja:

\[ \sum_{k=0}^{n-1}\frac{1}{1-\frac{k}{n}}=\frac{n}{n}+\frac{n}{n-1}+\ldots+\frac{n}{2}+\frac{n}{1}\]

Sem magia até agora, eu apenas expandi a série. Eu poderia calcular exatamente esse valor para $ n=80$, mas gosto de resultados mais gerais, e noto que essa soma é $ n$ vezes a série harmônica. Ela diverge, e não é surpreendente que eu precise de infinitos fandangos para tirar infinitos tazos, mas felizmente conhecemos razoavelmente bem o comportamento dessa série. O número esperado de salgadinhos necessários para completar uma coleção de $ n$ tazos é, portanto, $ nH_n$, onde $ H_n$ é o n-ésimo número harmônico. Para $ n$ grande, podemos usar a aproximação $ H_n\approx \log n+\gamma$, onde $ \gamma$ é a constante de Euler-Mascheroni (aproximadamente 0,5772).

Chegamos ao valor $ 80*(\log(80)+\gamma)=396,74$, certamente aproximado. Esse é o número médio de vezes que crianças completam suas coleções. Temos a média, a próxima pergunta é: quão provável é estar longe da média? Ao invés de tentar calcular com manobras intrincadas as flutuações desse número em torno da média, tomarei, a princípio, o exemplo de cinco crianças: Aline, Bruno, Carlos, Daphny e Eduardo. Eles começam suas coleções juntos e têm poucos amigos, logo, contam apenas com os salgadinhos para obter os preciosos discos. Eis uma simulação que fiz do resultado da coleção dessas cinco crianças:

Notamos algumas coisas interessantes. Primeiro, teremos que gastar aproximadamente metade dos salgadinhos totais necessários apenas para conseguir os dez últimos tazos; a matemática é cruel com coleções quase completas. Segundo, o valor necessário para completar é muito diferente nos cinco casos, isso exige um estudo mais sério.

Para tal, calibramos o computador para simular a coleção de tazos, ou o álbum de figurinhas (o problema é o mesmo) de 20.000 crianças. Fiz um histograma com a quantidade de salgadinhos necessária para completar toda a coleção e a porcentagem das crianças simuladas que precisaram daquela quantidade de salgadinhos para obterem o último tazo.

Notamos a larga variância dessa distribuição: haverá um grande número de crianças sortudas e um grande número de azaradas! Confirmamos o valor esperado, 396 parece de fato uma boa média dessa distribuição, e confirmamos o quão sórdido é o raciocínio da Elma Chips: algumas crianças precisariam de 900 salgadinhos para terem a coleção completa!

Contudo, esse modelo não representa bem a realidade, talvez apenas a minha, mas a maior parte das crianças tinha como maior objetivo as trocas de tazos, as disputas, completar a coleção contando com o salgadinho dos outros. Eu mesmo consegui dois amigos para fazer uma sociedade, ainda que cada um quisesse, para si, uma coleção completa. E esse será meu modelo de trocas: os amigos são amigos perfeitos, todo tazo repetido é compartilhado e o objetivo maior é, para $ y$ amigos, formar $ y$ coleções completas.

De forma não surpreendente, o número de fandangos que cada criança deve comprar reduz drasticamente com as trocas. Se ele antes precisava gastar quase um ano de lanches de salgadinho para encontrar os dez últimos, esses famigerados dez podem ter sido encontrados por algum colega que já até o tirou uma vez. Simulei o resultado com grupos de 1, 5, 10 e 30 crianças, sendo os resultados no histograma abaixo:

Esses valores são quantos fandangos cada um precisará comprar, ou seja, no grupo de dez, se dez amigos precisaram de 2000 fandangos para fechar a conta, contabilizo 200 para cada criança. Os valores médios de salgadinhos individuais obtidos para 1, 5, 10 e 30 são, respectivamente e aproximadamente, 398, 194, 154 e 120. Fiquei curioso para estudar a convergência dessa série, se vai para algum lugar (certamente converge, sendo decrescente e limitada em 80) e se esse lugar é 80, uma utopia em que todas as crianças do país montam suas coleções juntas; mas esse post já está longo e tanto salgadinho não deve fazer bem a esses meninos.

Por fim, noto que a amizade é o melhor investimento, você pode, em poucos meses de lanche, completar sua coleção de tazos ou figurinhas se encontrar, em uma sala de aula, trinta amigos perfeitos. A probabilidade desse fato, no entanto, mesmo em um modelo bem otimista, é extremamente baixa.

2 respostas

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.

2 respostas

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.

2 respostas