Arquivo mensais:outubro 2012

O prédio e as bolas

Imagine-se num prédio de 100 andares com várias bolas. A partir de um determinado andar (desconhecido), quando você joga uma bola pela janela, a bola quebra. Você quer determinar precisamente qual é esse andar e a única coisa que pode fazer é jogar bolas de andares diferentes.

Se você tem muitas bolas e não se importa em quebrar quantas forem necessárias, você pode realizar uma busca binária. Uma busca binária, para começar com um exemplo, é aquilo que você faz naquele diálogo clássico:

— Pense num número de 1 a 100 e eu vou tentar adivinhar. A cada palpite, você precisa me dizer se o número que você pensou é maior ou menor do que meu chute.
— Pensei.
— 50
— Maior.
— 75
— Menor.
— 63
— Menor.
— 57
— Menor.
— 54
— Menor.
— 52
— Menor.
— 51
— Acertou!

A cada passo numa busca binária você divide o intervalo de possibilidades por dois. Você descarta metade dos números que poderiam ser a solução. Por isso, mesmo que você pense num número de 1 a 1.000.000.000 (um bilhão) eu certamente não vou demorar mais de 30 (isso é, logaritmo de um bilhão na base dois) tentativas para acertar exatamente o número que você pensou.

Por que logaritmo de um bilhão na base dois? Como eu comentei anteriormente, a cada número que eu chuto e você diz se é maior ou menor do que o resultado eu corto meu intervalo por dois. Portanto, o número de chutes necessários (no pior caso) é precisamente a quantidade de vezes que preciso dividir um bilhão por dois até chegar a um (até sobrar um único número possível para eu chutar, que necessariamente vai ser o número que você pensou).

1000000000 / 2 / 2 / \cdots / 2 = 1

Nosso problema é encontrar quantos 2 tem aí. Dividir um número por 2 k vezes é o mesmo que dividir por 2^k. Logo, nosso problema é encontrar quanto vale k:

\displaystyle \frac{1000000000}{2^k} = 1

Multiplicando os dois lados da igualdade por 2^k, temos:

\displaystyle 1000000000 = 2^k

Tirando o logaritmo na base 2, concluímos:

\displaystyle \log_2 1000000000 = k

Ou seja, o logaritmo de n na base 2 é o número de vezes que precisamos dividir n por 2 para chegar em 1. Voltando ao problema inicial, como log_2 100 < 7[/latex], precisaremos jogar no máximo 7 bolas para determinar a partir de qual andar a bola quebrar. Quando você jogar uma bola, se ela quebrar é a mesma coisa que o seu amigo que pensou num número dizendo "O número que eu pensei é menor." Se ela não quebrar, é equivalente ao seu amigo dizendo "O número que eu pensei é maior."

Realizando uma busca binária, o pior caso (aquele caso no qual quebraremos mais bolas -- e que jogaremos a maior quantidade de vezes) é quando a bola quebra no primeiro andar. Você joga as bolas dos andares 50 (poft!), 25 (poft!), 13 (poft!), 7 (poft!), 4 (poft!), 2 (poft!), 1, jogando um total de 7 e quebrando um total de 6 bolas.

Nada muito novo para quem já conhecia busca binária. Por isso, vamos modificar o problema: Suponha que você não tenha quantas bolas desejar, mas apenas duas bolas. Quando uma bola cai sem quebrar, você pode descer, pegá-la e jogá-la de novo. Qual a menor quantidade de vezes que você vai ter que jogar a bola para com certeza determinar a partir de qual andar as bolas começam a quebrar?

Fazer uma busca binária não funciona mais. No caso de a bola quebrar a partir do primeiro andar, assim que você joga uma bola do andar 50 (uma bola quebra) e outra do 25 (outra bola quebra), você não tem mais bolas e não tem ideia de qual é o andar a partir do qual as bolas começam a quebrar (tudo o que você sabe é que é algum andar entre 1 e 25).

Como usar as duas bolas para determinar exatamente o andar a partir do qual as bolas começam a quebrar jogando as bolas a menor quantidade possível de vezes? Qual é essa quantidade mínima de vezes que será necessário jogar bolas pela janela?

Obrigado ao David por ter me apresentado o problema. A solução é bem legal!

Editado para ficar mais claro: A quantidade mínima que queremos é a do pior caso, isso é, a menor quantidade de vezes que será necessário jogar a bola independente de qual for o andar. Por exemplo, suponha que eu jogue uma bola do andar 5 e não quebre. Aí eu jogue do andar 10 e não quebre. Do 15 e não quebre. E assim sucessivamente (de 5 em 5) enquanto ela não quebrar. Quando ela quebrar, eu pego a outra bola e jogo no último valor que eu joguei menos 4, menos 3, menos 2 e menos 1. O pior caso para esse algoritmo é quando a bola quebrar a partir do andar 99. Jogarei nos andares 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100 (poft!), 96, 97, 98, 99 (poft!), ou seja, 24 vezes. (Mas é possível usar um algoritmo mais esperto que isso: a resposta do problema é menor que 24.)

Editado para programadores: A generalização deste problema (para n andares em vez de 100 e k bolas em vez de 2) caiu na OBI 2010 (o problema se chama Altas Aventuras) e está no SPOJ para quem quiser resolver: ALTAS2. Quem me contou foi o André.

Escreva um blog e compartilhe suas ideias

O crescimento da internet em todo o planeta expressa a necessidade da nossa geração de experimentar meios de comunicação diferentes dos que a mídia tradicional nos propõem. A sociedade é cada vez mais dependente dessa rede, que conecta as pessoas das mais distantes localidades em tempo real.

A internet não é a mesma de dez anos atrás. Uma conexão hoje é condição necessária para a utilidade de um computador e a rede está cada vez mais presente em diferentes dispositivos, em especial nos celulares. A web é hoje o espaço das aplicações e dos serviços: um espaço virtual aparentemente infinito para onde você faz upload de toda a sua vida. Você usa a internet para ouvir músicas, baixar filmes, editar documentos, conversar com amigos, pagar contas, planejar viagens, organizar calendário, ver mapas, guardar fotos, entre muitos outros usos. Porém, o principal deles continua sendo compartilhar, ou seja, difundir ideias.

Compartilhar sempre foi o cerne da internet. Desde a criação dos primeiros sites pessoais, passando pelos blogs e por ferramentas que auxiliam a sua criação, chegando às mais diferentes ferramentas de redes sociais. Por isso, a disputa da rede é feita através das brigas em torno do compartilhamento: o que pode e não pode compartilhar, o anonimato necessário para compartilhar verdades inconvenientes, a neutralidade dos serviços contra o filtro do que passa e não passa pela rede.

Por um lado, temos aqueles que defendem uma internet mais restrita e com menos liberdade, isso é, com mais cara de TV. A censura do Wikileaks, juntamente com a perseguição a Julian Assange, e os projetos de lei SOPA/PIPA (EUA), Sinde (Espanha), Lerras (Colômbia) e Azeredo (Brasil) foram os casos que mais chamaram atenção nos últimos tempos.

Por outro lado, tecnologias estão sendo construídas e superadas em tempo recorde para tornar o compartilhamento mais fácil. Os levantes recentes no Oriente Médio demonstraram a eficácia da internet em ajudar ativistas políticos e sociais a organizarem protestos, disseminarem informações para o público e enviarem notícias de prisões e repressões ao restante do mundo. Do ponto de vista da tecnologia, o Facebook, pela sua capilaridade, é hoje a maior expressão da internet de curtir e compartilhar.

A rede de Mark Zuckerberg teve papel destacado em importantes acontecimentos sociais e políticos do ano passado. Há vários exemplos. Organização e divulgação dos protestos que culminaram na queda de Hosni Mubarak no Egito. Construção do movimento 15-M da juventude da Espanha e de outros movimentos de indignados por todo o planeta. Surgimento do movimento Occupy Wall Street nos EUA. Aqui no Brasil, difusão de diversos atos contra o aumento da passagem de ônibus, Marcha da Liberdade, Marcha das Vadias, Fora Ricardo Teixeira, entre outros.

A internet de hoje não é a mesma do ano passado. Pelo seu funcionamento democrático e pela sua dimensão global, ela muda muito rápido. Por isso, cabe a nós experimentar o tempo todo novas formas de explorar o ciberespaço para aproveitar todo o seu potencial viralizante e discutir ideias que nos auxiliem na construção de instrumentos de mudança social que organizem mais e mais pessoas ao redor do mundo.

Embora o Facebook seja uma ferramenta de utilidade incontestável, sua hegemonia tem me preocupado. Não pelo motivo que sempre leio por aí (o de estarmos compartilhando toda a nossa vida com uma empresa que não tem uma política de privacidade muito razoável), mas principalmente por outros dois: seu caráter efêmero e seus algoritmos que nos separam em bolhas.

Achar algo que você leu no mês passado no Facebook é um pesadelo. Ainda que você lembre quem foi que compartilhou ou em que grupo, você precisa andar e andar na barra de rolagem até fazer seu cooler começar a gritar de tanto processamento de JavaScript para encontrar o que você queria. No caso de querer encontrar comentários ou uma coisa que você não lembra quem foi que postou, é difícil até imaginar por onde começar. Os posts do Facebook não são indexados por sites de busca e suas mensagens vão ficando sufocadas embaixo de uma pilha que cresce quanto mais você usa a rede social. Por mais que exista a tentativa da linha do tempo para você navegar por anos e meses, é inegável que o Facebook é a rede social do que está acontecendo e não do que aconteceu.

Além disso, sua rede de amigos no Facebook é muito limitada. Primeiramente porque você só pode ter 5000 amigos (mais assinantes, é verdade), mas principalmente porque uma porcentagem muito pequena deles efetivamente vêem o que você posta. Vou dar um exemplo: De julho a outubro publiquei todos os dias atualizações de status sobre as eleições municipais no meu perfil divulgando as propostas dos meus candidatos. Na véspera das eleições, mandei e-mails e mensagens no Facebook para grande parte dos meus contatos pedindo voto neles. Várias pessoas ficaram felizes com a recomendação e disseram que até receberem a mensagem nem sabiam que eu estava envolvido na campanha do PSOL.

Faz sentido. O algoritmo do Facebook provavelmente seleciona postagens de temas que você se interessa (costuma postar, curtir, comentar, compartilhar) para você ler. Os posts sobre banana tendem a ser visualizados por quem gosta de banana. Aí você fica fazendo propaganda de bananas para seus amigos bananeiros. Bom para receber curtidas e melhorar sua auto-estima, ruim se você quer discutir as vantagens da banana com mais pessoas que não são do seu grupo de estudos sobre banana. Além de que tem um monte de gente que gosta de banana, mas nunca vai ver seus posts simplesmente porque não é seu amigo.

Passei os últimos anos escrevendo muito no Facebook. O Facebook certamente é uma ferramenta muito importante, mas estou convencido de que ele tem um potencial infinitamente maior se caminhar junto com a escrita de blogs. Posso citar pelo menos três motivos:

  1. Os blogs divulgam mensagens menos efêmeras e com mais conteúdo. Por isso, são espaços mais adequados à formulação e ao registro de ideias (que certamente não devem deixar de ir para as redes sociais para serem disseminadas nas bolhas).
  2. Os blogs são indexados pelo Google. Com isso, aparecem nos resultados das buscas de quem se interessa pelas coisas que escrevemos e seus links fortalecem os sites que queremos difundir para o mundo através do aumento do seu pagerank.
  3. Os blogs não só enviam mensagens, mas iniciam conversações. Posts em blogs geram não só reflexões, mas comentários, posts em outros blogs e discussões nas redes sociais.

Tenho uma rede de amigos que escreve coisas muito legais nas redes sociais. Debate os temas da atualidade, formula política, faz críticas inteligentes sobre uma porção de assuntos relevantes. Há muitas (bilhões, eu diria) pessoas que não leio no Facebook, que talvez leiam este post e que certamente também têm muito a contribuir para o saudável debate de ideias que precisamos travar o tempo todo para mudarmos as pessoas e mudarmos o mundo. Esses comentários merecem e precisam superar as fronteiras dos algoritmos do Facebook para gerar mais discussão e influenciar outras pessoas. Por isso, escrevo para fazer o convite: escreva um blog e compartilhe suas ideias!

Tem um blog? Compartilhe um link dele nos comentários.

Resgate de anos de história

No início de 2005, logo antes de começar o Ensino Médio, eu escrevi meu próprio sistema de blog (tipo pra concorrer com o WordPress — só que não) e comecei a blogar no endereço tableless.tiagomadeira.net. Estava empolgado com a ideia de construir uma web semântica, com XHTML e com tableless. Foi um pouco antes do “estouro” da blogosfera que veio com o ascenso do WordPress mais pro final do mesmo ano e pelos dois anos seguintes.

Desde lá e durante todo o ensino médio, eu bloguei muito. No final de 2005, o blog se transformou num WordPress e assumiu o endereço tiagomadeira.net. Além disso, no verão de 2005 para 2006 escrevi um blog-curso de algoritmos para estudar para a Olimpíada de Informática.

Um ano depois, comecei a escrever outro blog em parceria (o Mal Vicioso, com a Carol). E em 2007, passei a participar timidamente ainda de outro (o 1001 Gatos de Schrödinger, do Ibrahim).

Em 2008, quando entrei na UFSC, fiquei um ano completamente sem blogar. Foi provavelmente o meu ano mais longe da internet, devido ao estudo sério de matemática e o treinamento intensivo para a Maratona de Programação (foi nesse ano que nossa equipe se classificou para a final mundial na Suécia).

Quando vim para São Paulo, em 2009, resolvi voltar a blogar. Porém, depois de ter ficado um ano sem dar bola pro meu blog, não me senti confortável em continuar usando ele (além de que fui tentar organizá-lo e acabei perdendo conteúdo sem querer). Aí acabei criando outro no endereço blog.tiagomadeira.com.

O conteúdo do tiagomadeira.net acabou ficando jogado às traças num leiaute terrível com mais publicidade do AdSense do que conteúdo. A mesma coisa aconteceu com o blog de algoritmos, que curiosamente continuou sendo bem visitado (valeu, Google!). E os outros dois blogs (Mal Vicioso e 1001 Gatos) simplesmente morreram.

Vinha pensando há algum tempo em fazer alguma coisa para salvar o conteúdo de todos esses blogs. Até que nesse sábado resolvi botar a mão na massa e toquei esse meu projeto egocêntrico: Escrevi um novo design e exportei/importei os posts de todos os outros blogs para este novo, relendo os posts para corrigir formatação, imagens e links quebrados.

Estou inaugurando este blog com textos dos últimos oito anos, ou seja, que registram acontecimentos interessantes de mais de 1/3 do meu tempo de vida. Encontrei uma porção de coisas legais quando resgatava os posts: angústias, ideias, planos, descobertas. Definitivamente valeu a pena não permitir que isso tudo se perdesse no buraco negro da internet.

Acabei motivado a continuar escrevendo aqui para contar o que ando pensando e para que no futuro eu continue me divertindo com meus velhos projetos. Ansioso para ver se a motivação vai vingar.

Não existem potências de 2 que terminem com 02, 22, 42, 62, 82

Esses dias, tomando banho de mar, me vi pensando na forma das potências de dois em base dez.

É fácil ver que não existe potência de 2 que termine em 0, já que qualquer número que termina em 0 é múltiplo de 5.

Na verdade, é fácil ver (com um raciocínio indutivo com módulo 10) que o último algarismo das potências de 2 vai seguindo a sequência (2, 4, 8, 6) infinitamente, de tal forma que o último algarismo de 2^k (k > 0) é:

– 6, se o resto da divisão de k por 4 for 0
– 2, se o resto da divisão de k por 4 for 1
– 4, se o resto da divisão de k por 4 for 2
– 8, se o resto da divisão de k por 4 for 3

Mas aí fiquei pensando em potências de 2 que acabassem com uma porção de doises. Algo como 3103912840123891294805398108310312222 (esse número aí não tem nada de especial, foi só eu batendo no teclado loucamente e terminando com 2222). Como eu faria pra encontrá-las? Será que existem?

Comecei pensando em coisas do tipo 222…222, isto é 2 \times 10^n + 2 \times 10^{n-1} + 2 \times 10^{n-2} + \cdots + 2 \times 10^0

Podemos colocar 20 em evidência, ficando com 20 \times (10^{n-1} + 10^{n-2} + \cdots + 10^0) + 2.

A princípio isso não parece ajudar muito, mas vejam que interessante:

20 \times x + 2 = 2(10x+1) (x é qualquer número inteiro > 0)

Bem… 10x+1 certamente não é uma potência de 2 (porque termina em 1).

Logo, 2(10x+1) também não é uma potência de 2, independente da maluquice que a gente coloque no lugar de x.

Portanto, não existem potências de 2 que terminem em 22! Mais que isso: não existem potências da forma 20x+2, ou seja, não existem potências de 2 que terminem em 02, 22, 42, 62 ou 82! Não é incrível? Não é nada muito revolucionário ou complexo, mas nunca tinha parado pra pensar nisso.

Lá no início tínhamos visto que o último algarismo de 2^k é 2 se e somente se o resto da divisão de k por 4 for 1. Logo, concluímos (e dá pra imaginar várias outras provas simples pra esse fato, pensando bem, por exemplo notando que 12 \times 16 \equiv 12 \mod 20) que para todo k > 0 tal que o resto da divisão de k por 4 seja 1 vale que o resto da divisão de 2^k por 20 é 12.

As primeiras potências de 2 que terminam em 2 são:

2^1 = 2 (que ignorei aí em cima quando falei que x > 0 no 20x+2)
2^5 = 32
2^9 = 512
2^{13} = 8192
2^{17} = 131072
2^{21} = 2097152
2^{25} = 33554432

O que parece nos indicar que, da mesma forma que o último algarismo das potências de 2 seguem a sequência (2, 4, 8, 6), o penúltimo algarismo das potências de 2 que acabam em 2 seguem a sequência (9, 7, 5, 3, 1). Isso é fácil de ver: basta fazer umas multiplicações por 16 dentro do módulo 100.