Arquivo mensais:dezembro 2012

Amigo secreto

Geek

Inspirado nesse clima de fim de ano, pensei em problemas que combinariam com essa última semana, e nenhum me pareceu mais adequado que o do amigo secreto. Todos já participamos de algo parecido, você é obrigado a tirar aleatoriamente um amigo que, via de regra, você mal conhece e deve comprar a ele um presente de até um determinado valor. É uma excelente oportunidade de ter que comprar coisas para quem não conhece e receber algo pífio de quem não gosta, porque presentes dependem do presenteado e, com pouca informação a respeito, esse processo tende a receber uma camiseta tamanho M que nunca na vida você usará.

Mas estes não são os únicos problemas do amigo secreto, há outros, que ao menos têm solução. Vou propor duas perguntas sobre a brincadeira, que envolvem pequenos defeitos que podem acontecer na seleção. Encontrar suas soluções é um interessante exercício de combnatória.

1) Qual a probabilidade de alguém tirar a si mesmo?

A primeira pergunta parece simples, mas tanto está longe de ser que ganhou um nome: o problema do chapeleiro. Suponha que o responsável por uma chapeleira perdeu o livro que dizia o dono de cada chapéu. Sem saída, ele distribui aleatoriamente os chapéus a quem vem buscar o seu. Qual a probabilidade de ele não ter acertado nenhum?

A resposta, apesar de bonita, não tem demonstração simples. Se peco na precisão, é por amor à clareza, vou tentar explicar o princípio desse cálculo. Você sabe que todas as permutações possíveis dos chapéus são $N!{}$, onde $N$ é o número de chapéus. Para saber a probabilidade de isso não acontecer, calculamos a chance de acontecer e tomamos a complementar. Para tal, basta somar as permutações que mantêm alguém constante (alguém recebeu o chapéu errado). Mas teremos um problema com isso, como veremos.

  • Missão: calcular a chance de alguém ter recebido o próprio chapéu.

Sabemos que para calcular a chance de uma pessoa $i$ receber seu próprio chapéu basta somar quantas permutações de chapéu resultariam em ele terminando com seu chapéu na mão, e essa conta é simples, são $(N-1)!{}$ (com o dele fixo, calculamos as permutações dos demais). Mas não podemos apenas somar esse número para todos os $i$, pois estaremos contando muitas coisas duas vezes! Para entender, uso de exemplo os quatro irmão, G, B, R e Y, que decidiram ir a uma festa deixando seus chapéus na chapelaria. Eles chegaram da seguinte forma:

hats2

Há $4!=24$ configurações possíveis de distribuição de chapéus na saída, mas há apenas 6 configurações em que o verde recebe seu chapéu corretamente, vejamos:

hats1

Note que seria ingênuo apenas somar essas configurações para todos os irmãos e dizer que esse seria o número de permutações em que alguém recebe seu chapéu corretamente, pois notamos que poucas são as vezes em que apenas o verde recebe seu chapéu, ou seja, na conta do verde há vezes em que outros recebem seu chapéu e essas configurações serão contadas novamente na vez desses outros que receberam o chapéu correto. Felizmente isso pode ser corrigido, basta retirar o número de vezes em que dois recebem os chapéu correto.

Vamos colocar isso em uma linguagem matemática decente. Chamaremos $A_n$ o conjunto das permutações tais que o número $n$ recebe seu chapéu correto. Sabemos que $|A_n|=(N-1)!{}$. Mas o que queremos é $|\cup_n A_n|$, ou seja, o número total de permutações em que alguém é fixo.

Começamos calculando $\sum_n |A_n|$, mas provamos que contamos muita gente duas vezes. Pegamos esse resultado e subtraímos $\sum_{i<j} |A_{i,j}|$, onde $A_{i,j}$ é o conjunto das permutações que deixam $i$ e $j$ fixos, ou seja, eles recebem o chapéu correto.

Agora sofremos de outro mal, o remédio causou um novo sintoma. Ao excluirmos todos os que possuem dois fixos, excluímos duas vezes aqueles que possuem três fixos, e assim por diante, pois eles foram contados mais de uma vez nessa subtração. Isso não é problema, basta colocarmos de volta esses elementos, somando ao resultado o fator $\sum_{i<j<k} |A_{i,j,k}|$. O problema é que nessa soma contamos duas vezes os que possuem quatro fixos.

Deu para entender o mecanismo. Felizmente, como há um número finito de chapéus, ele algum dia terminará. E sabemos que o número de permutações possíveis com $n$ chapéus fixos é $(N-n)!{}$, isso nos permitirá calcular a soma total. Mas precisamos também lembrar que ao calcularmos $\sum_{i<j<k}|A_{i,j,k}|$, por exemplo, temos que somar $(N-3)!{}$ um número de vezes equivalente ao número de configurações possíveis na escolha de $i,j,k$, ou seja, um número ${N\choose 3}$ de vezes. Calculando ${N\choose 3}(N-3)!{}$, abrindo a fórmula binomial, nos resta apenas um fator, nesse caso, de $\frac{N!}{3!}$. É fácil deduzir que com os demais será a mesma coisa:

\[|\cup_n A_n|=\sum_n|A_n|-\sum_{i<j}|A_{i,j}|+\sum_{i<j<k}|A_{i,j,k}|+\ldots\]

\[= \frac{N!}{1!}-\frac{N!}{2!}+\frac{N!}{3!}+\ldots = N!\sum_{j=1}^{N-1} (-1)^{j+1}\frac{1}{j!}$

Esse é o número total de configurações em que alguém recebe seu chapéu corretamente. Para descobrir a chance de alguém receber o chapéu, basta dividir esse valor pelo número total de configurações, ou seja, $N!{}$. Concluímos aquela missão estabelecida acima, mas queremos a chance do complementar acontecendo, e para encontrar a probabilidade de ninguém ter o chapéu correto basta tomar 1 e subtrair esse valor calculado. Teremos:

$P(N)=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+\ldots +(-1)^N\frac{1}{N!}$

E essa é a probabilidade, no amigo secreto, de ninguém tirar a si mesmo:

hat_check_graph

É fácil perceber que essa soma tende rapidamente a $\frac{1}{e}$, pois nosso resultado são exatamente as somas parciais da série de Taylor de $\frac{1}{e}$, e é interessante perceber como esse valor já é quase exato já a partir de cinco participantes, a convergência do fatorial sempre impressiona. Como toda boa série de Taylor, o erro é da ordem do último termo somado, então é natural que a partir de 5 participantes a diferença entre essa probabilidade e $ \frac{1}{e}$ seja menor que 1/120. É notável também o fato de, com apenas um participante, a chance ser zero de ninguém tirar a si mesmo, o que era, pelo bom senso, esperado.

O resultado é interessante também por outro motivo. Se aumentamos o número de participantes, a chance de uma pessoa escolhida tirar a si própria é cada vez menor, mas o número de pessoas que podem tirar a si mesmas aumenta, a resposta de “para onde vai a probabilidade” não é trivial e é bem interessante que nenhum desses elementos domine o outro, ou seja, a probabilidade não vai nem para zero, nem para um, mas para um valor intermediário e longe de ser evidente.

2) Qual a chance da brincadeira do amigo secreto não para no meio, ou seja, não “fechar o ciclo” antes de terminar e alguém ser obrigado a recomeçar o jogo?

Essa resposta é mais simples e possui menos imagens. Começamos por um participante qualquer. Para que o jogo não pare, ele não pode tirar a si mesmo, sobram $N-1$ opções. Ao tirar algum deles, essa próxima pessoa não pode tirar nem ela mesma, nem o primeiro, então sobram apenas $N-2$ opções a ela. Assim sucessivamente, é fácil ver que o número de ciclos possíveis que não serão interrompidos será de $(N-1)!{}$. Naturalmente, basta apenas dividir pelo número total de permutações, $N!{}$, para ter a probabilidade de isso acontecer, e ela é $\frac{1}{N}$. Como esperado, quanto maior o grupo de pessoas, mas difícil é obter uma configuração que forneça um jogo sem interrupções.

Depois desse post de combinatória um pouco árido, termino desejando a vocês um excelente ano novo, boas férias e todas as permutações possíveis daqueles votos de fim de ano que não canso de lhes desejar, mas que cansaria de escrever.

Nobel 2012 – Medindo sem destruir

Rookie

Eu estava em uma conferência no centro da França sobre física estatística quando recebemos a notícia do prêmio nobel, o auditório explodiu em aplausos, ainda que o premiado não estivesse entre nós. Não aplaudiram o cientista, provavelmente, mas o que ele representa: reconhecimento da comunidade científica a uma área, um raciocínio, uma ideia, muito mais que uma pessoa. Conhecido da maior parte dos conferencistas daquele evento, esse gigante na física experimental certamente merece os aplausos, e mais outros, que virão. Dedico o post de hoje ao prêmio nobel da física de 2012, o mago dos fótons e íons e pesquisador do laboratório Kastler Brossel, Serge Haroche. Também necessário dizer, também ao outro ganhador do prêmio, David Wineland.

Antes, assistir ao seguinte vídeo é necessário:

[youtube=http://www.youtube.com/watch?v=2dRr-fnPCwM]

Dificilmente consigo explicar melhor que isso, mas vou tentar dizer coisas a mais do que isso. Há uma diferença sutil entre os trabalhos de Haroche e Wineland. É uma simetria bonita: o primeiro lança partículas para medir a luz, o segundo usa a luz para medir partículas. A razão desses experimentos, e a grandeza deles, não é apenas conseguir medir a luz sem a destruir, como o vídeo nos conta, mas provar algo mais profundo: que ao medir um estado quântico, a própria régua que usamos para medir é afetada.

Um estado quântico, que é como chamamos a situação em que se encontra a maior parte das coisas muito, muito pequenas, não é o que medimos. Por mais estranho que isso possa parecer, um estado quântico pode ser algo como A+B e, ao medirmos, podemos encontrar A com uma probabilidade e B com outra. É aquela história do gato de Schrodinger, que pode estar vivo e morto ao mesmo tempo; só saberemos ao abrir a caixa, ao fazer a medida. Um átomo pode estar em uma situação dessas, em um estado entre dois níveis de energia, sem necessariamente “escolher” um até que a medida seja feita. Haroche e Wineland foram capazes de, usando fótons e caixas super-refletoras, medir o estado desse átomo sem precisar fazê-lo “escolher” entre um dos dois níveis de energia. Basta lançá-lo em meio a fótons, partículas de luz, que o átomo se mesclaria aos fótons, conduziria as partículas de luz a um estado coerente com o estado do átomo e, para medir o átomo, bastaria medir os fótons. É como medir a velocidade de um barco através das ondas que ele forma na água, sem precisar parar o barco para perguntar o que consta no velocímetro.

Esse tipo de medida preservando o estado quântico de “indecisão” dos átomos é fundamental para uma aplicação em particular: a computação quântica. Eu teria que escrever um post com bastante calma sobre isso, mas o princípio do computador quântico reside nessa ideia de “indecisão” dos estados quânticos entre duas situações, forçar o sistema a escolher um dos estados seria destruir toda a vantagem de se ter um computador quântico. Decerto, a computação quântica ainda engatinha, os experimentos de Haroche e Wineland datam de 1995, desde então as coisas avançaram mais.

O comitê do prêmio Nobel de física, mais uma vez (como no caso de 2010), prestigia uma área científica nova, recente, pesquisadores ainda ativos, com o prêmio máximo da ciência. Merecidamente. Haroche e Wineland, com grande intuição experimental e realização impecável das experiências, ganham lugar ao lado dos maiores na física, gigantes experimentalistas, mestres do mundo do muito pequeno.

Data venia

Rookie

É o terceiro post seguido em que cito a ciência na mídia, peço desculpas por não comentar um problema interessante de matemática ou um fenômeno bonito em física, mas, dessa vez, um problema sério e um fenômeno nada bonito. Li na Folha a excelente resposta do físico Marcelo Knobel aos comentários do ex-presidente do STF Ayres Britto sobre física quântica e espiritualidade. Eu dificilmente teria me expressado de forma mais clara que Knobel, e faço minhas suas palavras; data maxima venia, o ministro caprichou no nível da bobagem.

Dificilmente encontro um físico brasileiro que não tenha passado por uma situação dessas. Ao dizermo-nos físicos, às vezes somos recebidos com empolgação, quase admiração, de alguém que diz ter estudado física quântica, que aprendeu bastante dessa parte da ciência em seu curso de meditação, que adora como esse ramo do conhecimento confirma as bases espiritualistas de sua crença e, para coroar os comentários, pede-nos uma palavra, uma explicação e, de certa forma, uma aprovação. É uma sinuca de bico, uma situação bem espinhosa com que precisamos lidar.

Isso porque física quântica não é difícil, mas exige muito treinamento e a compreensão de muita coisa antes que se possa tentar entender seus mais básicos fundamentos. Na graduação em física somos apresentados à física quântica não antes do terceiro ano, temos que dominar uma quantidade alta de física e matemática para acompanhar a primeira equação dessa matéria e, ainda que não seja exatamente uma matéria difícil, as implicações na realidade do que as equações nos contam são estranhas, contraintuitivas, quase desrespeitosas ao senso comum. Nós, físicos profissionais, não temos a audácia de repetir nada perto do que disse o ministro, e, garanto, como escreveu Knobel, sabemos de muito mais coisa estranha que acontece no mundo do muito pequeno.

Não digo que física quântica é para poucos, mas é melhor deixada com profissionais; você pode e deve se interessar, como faz lendo esse blog, mas deve sempre ter em mente que, para realmente entender o que está acontecendo, precisa de bastante matemática e física, extraindo, portanto, seu conhecimento de profissionais respeitados da área. Não imagino como o ministro reagiria se grupos de crenças esotéricas começassem a ganhar dinheiro com termos como “o habeas corpus da alma e suas aplicações”, vendo a noção do termo jurídico ser mutilada em uma cacofonia de frases de autoajuda.

Mas não termino esse post sem comentar algo sobre física, e talvez minha parte favorita da introdução da física quântica, desmentindo o que disse no começo que não contaria nenhum fenômeno interessante. Knobel cita “Como físico, acredito em coisas incríveis, como entes que são ondas e partículas simultaneamente”, e ele escolheu esse primeiro tópico a dedo, é conhecido como “a dualidade onda-partícula” na física quântica. Foi talvez o primeiro grande empasse experimental dessa área, e a fonte de debates acalorados nos anos 20, até a invenção de um gato que estaria vivo e morto ao mesmo tempo. Essa história começa com duas paredes, uma delas com duas fendas, um físico e uma metralhadora. No caso da figura (de Arthur Vergani) que segue, Erwin Schrodinger.

schrodinger_gato_dupla_fenda

Imagine-se segurando uma metralhadora. À sua frente, uma parede com duas fendas verticais não muito grandes. Essa parede é bem resistente e a metralhadora não irá machucá-la, mas a parede que está logo depois dela, que não possui fendas, é mais frágil e ficará machucada. Você começa a atirar nas fendas, sem qualquer critério e com pouca mira. Como ficará a parede frágil que fica atrás?

A primeira parede servirá de “escudo”, deixando apenas passar balas pelas fendas. O esperado, então, é encontrar a região da parede frágil imediatamente em frente às fendas mais destruída. Ou seja, depois da saraivada de balas, sua parede deve estar com as seguintes marcas:

fenda_dupla_1

Marquei com linhas pontilhadas onde ficam as fendas da outra parede, que deixaram as balas passarem. Claro, há balas que não caem imediatamente em frente às fendas, há ricochetes, estou atirando como um maníaco nas paredes.

Isso acontece com balas, e o grande problema da física quântica é a descoberta de que elétrons não são balas. Ainda na analogia, imagine-se com uma nova metralhadora, que lança elétrons. Você metralha as paredes, e vamos imaginar, pela analogia, que as marcas deixadas nas paredes são as mesmas. Se você tivesse metralhado suas paredes com elétrons, sua parede de fundo teria uma imagem parecida com essa:

fenda_dupla_2

Vou deixar alguns instantes para você tentar digerir essa imagem.

Essa descoberta, conhecida como a experiência da dupla-fenda, chocou a comunidade científica. Não porque esse padrão era novo, pelo contrário, porque esse padrão é conhecido e pertencente a outra categoria de objeto, as ondas. Se você lançar luz por fendas pequenas o suficiente, você terá exatamente esse padrão de difração, como chamamos. Se você quer uma foto, apresento a que eu tirei quando, na faculdade, lancei um feixe laser em duas fendas bem pequenas. A figura formada do outro lado foi:

fenda_dupla_3

Esse padrão concorda exatamente com a parede metralhada por elétrons que passaram pela fenda dupla. Nessa experiência, conseguimos ver o caráter ondulatório do elétron. As ondas formam esse padrão se atravessam duas fendas, como as ondas de água formariam se a parede fosse capaz de medir a altura da água e colocássemos a parede com fendas duplas na beira do mar. Essa figura psicodélica da Wikipédia talvez ajude a ver, ou talvez desperte algum distúrbio neurológico que você ignorava possuir. As cores são a altura da água, quanto mais vermelha, mais alta:

Desde a primeira experiência com elétrons, os físicos tentaram responder a pergunta: afinal, por qual fenda o elétron passou? A onda do mar não passa por nenhuma fenda exatamente, passa pelas duas ao mesmo tempo, afinal, a onda não está em lugar nenhum, mas em vários. Ondas não possuem a nossa noção convencional de posição, e isso não assusta ninguém; mas o elétron é e sempre foi uma partícula, ele deveria passar por alguma fenda.

A primeira ideia é colocar um medidor de elétrons nas fendas. Fazendo isso, conseguimos medir a presença de um elétron e nem é preciso absorvê-lo, basta jogar algo nele que, se rebater, ele está lá. E de fato nunca teremos duas medições do mesmo elétron, ele irá realmente passar por uma das duas fendas; mas, ao olharmos para a parede no final da experiência, a figura que veremos será a da primeira parede cheia de balas, não a segunda. Como uma pegadinha cruel, se medimos por qual fenda o elétron passa, teremos o resultado esperado por partículas. Se não medimos, ele se comporta como onda! A única analogia válida, porque todas são difíceis nessa área, é aquele brinquedo de sua infância que não funcionava de jeito nenhum, aquele computador em pane que, quando seu pai chegava para consertar, funcionava cinicamente na primeira tentativa.

Com o tempo, descobrimos a intrincada complexidade dessa experiência. A perda do padrão de onda do elétron ocorre porque medimos ele e, nessa medida, damos muita energia ao garoto, que começa a se comportar de maneira diferente depois da medição. Nossa observação estraga o efeito que queremos, como abrir o forno para checar se o bolo está bom pode estragar o bolo.

Na mesma época, foram feitas outras experiências com a luz e descobriu-se que ela, muitas vezes, se comporta como partícula, quando desde muito se sabia que ela é uma onda. Aos poucos, os físicos foram chegando à conclusão de que, no mundo do muito pequeno, as coisas não são nem ondas, nem partículas. Não é muito correto dizer que são onda e partícula simultaneamente, tentando criar a ideia de um falso paradoxo e, acidentalmente, de misticismo na ciência. Mais honesto seria, talvez, dizer que os objetos muito pequenos não são ondas ou partículas, mas schrugs, um nome que acabo de inventar, mas que serve para deixar claro o fato de que eles são algo diferente do que estamos acostumados. Em algumas experiências, se comportam como ondas, em outras, como se fossem partículas, e essa é a realidade do mundo do infinitamente pequeno.

E por que haveríamos de achar uma analogia perfeita das partículas com objetos de nosso cotidiano? Que obrigação tem a realidade do nanométrico de se conformar a nossas concepções tão atreladas ao metro e ao segundo? A mecânica quântica diverge muito de nosso senso comum porque o muito pequeno, como o muito grande, não cabe em nossa imaginação; ainda bem que possuímos muitas equações confortáveis para nos guiar nesses pântanos e pradarias tão pouco familiares.

Por fim, noto que não consigo conceber onde nessa história toda há a verificação da espiritualidade de Ayres Britto. Na onda dos místicos de plantão, os que provavelmente inspiraram o ministro em sua crença, eles podem julgar que todos nós temos uma dualidade na existência, que a alma é um estado quântico, ou convolver um termo esotérico qualquer com um quântico para soarem sábios e parecerem ridículos; é fácil se aproveitar do desconhecido, do analfabetismo científico, para, em uma pajelança de termos vagos, vomitar pilantragem em DVD’s e palestras.

A física quântica nada tem de vago, nada tem de esotérico, nada tem de místico, não é bagunça, é coisa séria. É diferente do convencional, é verdade, assim como o estudo do muito grande, a cosmologia e a astrofísica, o são. Mas de nada serve, a eles, uma área da ciência sem frases de efeito, sem termos de significado obscuro que podem tornar um pilantra em um sábio em potencial (como disse em outro post, tarô quântico certamente parece mais interessante que tarô). Essas pseudociências compõem livros que forçam termos científicos a ficarem constrangedoramente justapostos a quem eles jamais conscientemente ficariam, como uma festa de fim de ano em que ninguém se conhece, sendo mais próximos de um sequestro de reféns que de um texto. Qualquer pessoa que usar termos estripados dessa área da física para justificar seu misticismo é, na melhor das hipóteses, ingênua; na pior, uma fraude.

Esperamos, portanto, que essa área da ciência se livre algum dia desse estigma, desse encosto esotérico. E também esperamos, como brasileiros, que o julgamento do ministro nada tenha de quântico, nada tenha de dualidade e nada tenha de relativo.