Resposta do Subway Problem

Pois bem, a chave para responder o subway problem é o intervalo de tempo de um trem para o outro. 

A solução é alcançada assim: 

Ele visitou a mãe 1/10 das vezes. Então, em um intervalo de duas horas (de 3 a 5), ou seja, 120 minutos, em  apenas em 12 minutos ele teve a chance de pegar um trem para ir visitar a mãe. A solução do livro é que no intervalo de 3 às 5 saem 12 trens para o centro e 12 trens para o subúrbio. Só que o trem do subúrbio vem um minuto após ter passado o trem para o centro, sobrando pro Marvin apenas 12 chances de um minuto para pegar um trem na justa janela de tempo entre eles. 

O que a resposta do livro não detalha é que qualquer divisor de 12 é possível para o número de trens. Eu resolvi o problema com 4 trens para o centro e intervalos de 3 minutos entre o metrô que vai para o centro e o que vai para o subúrbio (Marvin não consegue pegar o que sai exatamente às 3h), mas poderiam ser apenas dois trens: o que partiria às 3:12 para o subúrbio e o que partiria às 5h para o centro.

The Frederick Mosteller's Subway Problem

Caros, pequeno post para informar que atualizei o algoritmo de Gale-Shapley que foi mencionado no post "problemas matemáticos interessantes", agora está funcionando perfeitamente para men proposing and women proposing (antes funcionava só até matrizes 6x6), testei até uma matriz 100x100. Está lá no R-Nabble. Também para não perder a oportunidade, segue um outro problema de metrô (uma vez considerei um problema de outra natureza aqui no blog) do livro "Fifty Challenging Problems in Probability" do Frederick Mosteller:

"Marvin sai do serviço em horários aleatórios entre 3 e 5 da tarde. Sua mãe mora no subúrbio e sua namorada no centro. Ele pega o primeiro metrô que aparece em qualquer direção e janta na companhia da pessoa que está na primeira direção do metrô que lhe aparece. Sua mãe reclama que ele nunca vai jantar com ela, mas ele diz que ela tem chance de 50-50. Ele jantou com sua mãe apenas duas vezes durante os últimos 20 dias de trabalho. Explique."

Quem estiver disposto a considerá-lo pensem aí, em breve posto a resposta. Como não podia deixar de ser esse problema lembra Titãs.

Alguns Problemas Matemáticos Interessantes

Pessoal, algumas novidades do mundo econômico têm aparecido aí no fim de ano, algumas animadoras, outras nem tanto. Todos devem ter acompanhado a ascenção do Brasil para 6ª Economia mundial e visto os destaques da inflação, superávit primário e outros tópicos. Bom, como microeconomista que sou, não vou me concentrar nesses assuntos por hoje. Sobre a questão do 6º lugar, digo que é uma notícia boa e interessante, mas há bem pouco tempo, ainda no "Brasil-novo" pós 2003, estavamos em 11º. Enfim, se colocação de tamanho de PIB fosse indicativo de qualidade de vida para seus concidadãos a China já estava bem a muito tempo. A notícia é interessante para reforçar o tamanho de nossa economia.

Mas me concentro aqui em temas mais microeconômicos e matemáticos e alguns assuntos que aguardam um pouco para entrarem aqui no Blog. Um deles é um comparativo usando densidade relativa para saber qual é o melhor disco dos Beatles. Qual é o seu preferido?! Outro assunto nesse tema, e por vir aqui, é uma aplicação estatística ao problema de detecção de comportamentos diferentes: "o problema do chefe". Outro é um joguinho de Sodoku que fiz para o R, ainda não está pronto, pois meu algoritmo tenta achar um jogo válido entre os zilhões de jogos possíveis! A idéia do meu algoritimo é achar primeiro uma solução e depois cobrir os números de acordo com a facilidade que o jogador desejar. O fácil deve cobrir poucos números, o médio um pouco mais e assim por diante. Li em algum lugar que o Sudoku super profissional conta com apenas 16 números no grid inicial.  Os interessados já podem encontrar o jogo em um pacote "Sudoku" já disponível no R. Pelo menos a janelinha do meu sudoku (a da foto acima) é mais bacana. Quem não tem costume de usar o R e mesmo assim quer jogar um Sudoku e gerar jogos veja aqui nesse site.

Mas o propósito desse post no momento é convidá-los a conhecer o Problema do Casamento Estável (um joguinho muito interessante e didático), também conhecido como problema da dança de salão, desenvolvido pelo professor David Gale (1922-2008), da foto aí do lado, mais particularmente o algoritmo Gale-Shapley proposto em artigo de 1962. O problema consiste em alocar as pessoas de acordo com suas preferências da melhor maneira possível para os proponentes e que não dê empate. Imagine um salão de dança com o mesmo número de homens e mulheres. Esse problema envolve a escolha de um parceiro para a dança de acordo com as preferências. Suponhamos que os homens convidem primeiro as mulheres para dançar, então os homens propõem primeiro à mulher preferida. Mas e se mais de um homem convidar a mesma mulher para dançar? Então a mulher terá opção de escolha de acordo com as suas preferências. O problema pode ser invertido, com as mulheres propondo primeiro. O interessante é que nem sempre as soluções serão idênticas, o grupo que propõe primeiro tem maior chance de estar melhor, no mínimo estará igual a situação em que o outro grupo propõe. Um dos principais nomes nessa área é a profa. Marilda Sotomayor da faculdade de economia da USP que desenvolveu essa área, um dos seus artigos mais importantes é com o prof. Gale. Além disso é co-autora com Alvin Roth, outro nome importante da área, do livro "Two-Sided Matching: A Study in Game Theoretic Modeling and Analysis".

Há poucos dias meu orientador, o prof. Eduardo Rios-Neto, me propôs lidar com esse problema para vermos uma questão de como são alocados os alunos de escolas públicas, uma aplicação importante que procura responder: "Será que podemos melhorar nosso ensino alocando melhor os estudantes?". E me debrucei a tentar o algoritmo na linguagem R, que tenho mais familiaridade. Hoje postei o resultado disso no R-Nabble, comunidade para usuários e desenvolvedores do R-project. Convido a todos que tiverem interesse, e lidam com o R, a me ajudarem e melhorar o algoritmo. É importante testá-lo para novos desenvolvimentos da aplicação de alocação de alunos entre escolas.

Um exemplo interessante de aplicação é a dissertação de Felipe Bardella mestrado da USP. Em que ele estudou a relação de preferências que os alunos candidatos da ANPEC faziam para o exame e os resultados da seleção. Suas conclusões levam que o mercado da ANPEC passou por um tempo de aprendizado e que se trata de um mercado descentralizado com solução próxima a do algoritimo NRMP. Os centros mais bem rankeados tem maior facilidade em fazer valer sua ordenação de preferências sobre os candidatos, os demais centros tem mais dificuldades o que insere maior instabilidade do processo para eles. Uma sugestão da dissertação de Bardella não foi ainda adotada pela ANPEC. Adoção de uma listagem maior do que 6 centros que é atualmente feita. 

The Subway Problem

O metrô de Brasília é o novo xodó do transporte público da população Brasiliense. Estações, limpas, vagões novinhos em folha, muito asseio, conforto e rapidez. Ao preço de R$3,00 cada viagem (sendo que no fim de semana o preço abaixa para R$ 2,00, similar ao preço de várias linhas de ônibus que cobrem o plano piloto e satélites mais próximas). Os cidadãos da capital do país estão bastante zelosos com uso desta mais nova jóia do transporte público e desejosos da manutenção do nível dos serviços. O metrô da capital federal possui 42 Km de extensão.

Em particular, nesse último mês, esse economista observador que vos fala, que já é fã de trens urbanos tem utilizado bastante o trem. Fui até Aguas Claras, e tenho usado principalmente para ir ao "centro" da capital. Notei que o afluxo de pessoas está aumentando, usei o metrô também ano passado e pude comparar. Ainda assim, poucos brasilienses usam o serviço, o que significa que o metrô raramente está lotado (não como nas outras capitais). Também não pude deixar de observar estações vazias, em particular, me chamaram a atenção as estações inacabadas da 104, 106 e 110 Sul (vejam aqui um pequeno video que fiz no passeio de metro brasiliense). As estações já estão lá prontinhas para serem usadas, o mais difícil já foi feito, cavaram o buraco no chão, fizeram os pilares e toda a estrutura, falta o acabamento.

Essas estações são uma coisa bem típica do Brasil que gosta de jogar dinheiro fora... Fiquei pensando: "Será que algum dia vão ativar essas estações inacabadas?", "Compensa ativá-las?", "Se algum dia vierem a ativá-las o trabalho estará justificado, pois maior parte do serviço está pronta". Mas temo mesmo é que as estações da 104, 106 e 110 nunca serão ativadas. Taí mais um exemplo de desperdício do dinheiro público tão comum em nossas terras".

Acrecenta-se que seria totalmente lógico não ativá-las. O morador de Brasília sabe muito bem que as distâncias da 102 para a 104 não é tão grande. O mesmo ocorre da 108 para a 106 ou para a 110. Além disso, tenho observado que as estações das quadras do plano piloto são as menos densas no afluxo de passageiros (muitos críticos anteriormente defendiam que a w3 era o eixo mais apropriado no plano piloto), isso não quer dizer que não deva ter estações nas quadras, mas que ali os passageiros tem mais renda e mais opções de substituição do que nas periferias. O que ocorre? E por que acho que tais estações nunca serão ativadas?

Ativá-las atranvancaria o tempo de viagem do metrô que pararia em três quadras a mais para subirem e descerem apenas alguns gatos-pingados.

Chegamos então à grande questão lógica:

O Sr. Economista Questionador pergunta:

- "Para quê foram construídas as estações da 104, 106 e 110 que não estão sendo usadas?"

Sr. Projetista Estatal de plantão:

- "Para adiantar o trabalho caso o afluxo de pessoas aumente e precisemos ativá-las"

Sr. Economista:

- "Mas as quadras não são áreas pouco densas no transporte de passageiros do metrô?"

Sr. Projetista:

- "Sim, mas..."

Sr. Economista:

_ "E dado o atual afluxo de pessoas nas estações já instaladas da 102, 108, 112, 114 e Asa Sul, você acredita que o afluxo nas estações faltantes possa ser tão maior assim?"

Sr. Projetista:

- "As pessoas substituirão o carro pelo metrô e o movimento nas quadras pode aumentar."

Sr. Economista:

- "Concordo que isso possa ocorrer, mas será que aumentará o bastante?! Afinal a viagem durará mais tempo não é verdade?"

Sr. Projetista:

- "Sim o tempo de viagem, irá aumentar..."

Sr. Economista:

- "As pessoas não gostam de um transporte público que anda-e-pára, anda-e-pára, para isso já existem os ônibus. Se o metrô ficar muito lento algumas pessoas deixarão de usá-lo. Vale a pena aumentar o tempo de viagem para que umas poucas pessoas da região menos densa do plano piloto andem mais de metrô e menos de uma estação para outra?"

Sr. Projetista:

- "Sob essa perspectiva, não."

O Economista arremata dizendo:

- "Todo sistema de metrô enfrenta o mesmo problema básico: 'alcançar o maior número de passageiros oferecendo o maior conforto e o menor tempo de viagem possível'".

Simplificando, podemos colocar duas simples funções matemáticas para descrever esse problema:

1) O número de passageiros aumenta se aumentarmos o número de paradas, mas se colocamos muitas paradas próximas umas das outras o número de passageiros não incrementará tanto assim. Digamos que depois das duas paradas principais, cada parada a mais não consegue mais do que mil passageiros a cada viagem. Vamos descrever com a seguinte equação:

pax = 1000.p^(½)

Pax (número de Passageiros por viagem) e p é o número de paradas.

2) Se aumentamos o número de paradas aumentamos o tempo médio de viagem. E a cada parada acrescentam-se 5 minutos de tempo de viagem. E a cada parada e tempo de viagem que se acrescenta, mais pessoas desistem de viajar no metrô. Digamos que essa equação seja:

pax = 5.p²

Esse é um simples problema de maximização de 1) sujeito à 2) onde a solução para o exemplo é:

p = 13,5 (Ou aproximando para cima: 14 paradas).

Que podemos também representar no gráfico abaixo:

O mais importante desse exemplo não é um número particular de paradas, mas sim mostrar que existe uma solução ótima para o total de paradas a construir. É possível saber onde e em quais locais. É claro, que para se adequar melhor à realidade seria necessário que as equações fossem muito mais complexas e completas. A cidade tem regiões de densidade bastante diferentes, uma parada a mais na 110 sul, não é a mesma coisa em número de passageiros do que uma parada em Taguatinga. As regiões com densidade de passageiros diferentes complicariam o modelo. Assim como minha equação que descreve os passageiros desistindo com o acréscimo de tempo precisa de muito mais elementos, não considera o preço e o comparativo do tempo de viagem dos transportes alternativos.

No entanto, o que mais me admira nessa história toda é de como no Brasil temos vários exemplos ocultos de desperdício de dinheiro. Dinheiro público principalmente, um planejamento bem-feito resolveria várias dessas questões, mas continuamos com a preferência de esbanjadores a construir paradas-fantasma para ninguém usar e literalmente enterrar o dinheiro público.