Arquivo da categoria: Matemática

Imprima mais, pague menos

Tabelas de preços de impressão são interessantes. É muito comum que quanto mais você imprima mais baratas as impressões fiquem, fazendo com que o gráfico de preço por impressões não seja monótono (isso é, você não necessariamente pague mais por um número maior de impressões).

Isso torna as gráficas boas candidatas de lugares para pensar em gráficos de funções de primeiro grau, assim como a busca binária é uma boa candidata de aplicação para pensar sobre logaritmos.

Hoje fui imprimir uma partitura e me deparei com a seguinte tabela:

De 01 a 03 unidades R$ 0,70 cada
De 04 a 10 unidades R$ 0,50 cada
De 11 a 20 unidades R$ 0,40 cada
De 21 a 50 unidades R$ 0,30 cada
De 51 a 100 unidades R$ 0,25 cada
Acima de 100 unidades R$ 0,20 cada

(registrada em uma foto de um bilhão de dólares)

Se desenharmos um gráfico de preço (eixo y — vertical) por número de impressões (eixo x — horizontal), temos:

gráfico original

Observando esse gráfico (feio), percebemos que há alguns números de impressões que economicamente não faz sentido fazer. Por exemplo, 3 impressões custam R$ 2,10 enquanto 4 impressões custam R$ 2,00. 20 impressões custam R$ 8,00 enquanto 21 impressões custam R$ 6,30. 100 impressões custam R$ 25,00 enquanto 101 impressões custam R$ 20,20.

Mas não só esses. Os valores que não faz sentido imprimir no gráfico são todos aqueles cujo existe algum ponto a direita na mesma altura ou mais baixo, ou seja, todos os que pintei de amarelo:

gráfico com pontos inúteis destacados

Um problema econômico interessante para quando se está numa gráfica imprimindo é, portanto, descobrir quando estamos nos pontos amarelos. É interessante porque, se estivermos nos pontos amarelos, podemos aproveitar para imprimir mais cópias ou pedir ao dono da gráfica um desconto. Afinal, é razoável esperar que o preço que a gente pague seja limitado por este gráfico:

gráfico esperto

Descobrir se estamos numa região amarela é simples. Basta calcular o preço que pagaríamos a princípio (multiplicar o número de cópias pelo preço por cópias da região em que estamos) e comparar com o preço que pagaríamos se pedíssemos o menor número de cópias da região imediatamente mais barata. Por exemplo, faz sentido imprimir 15 cópias porque 15 \times 0.40=6.00 é menor do que 21 \times 0.30 = 6.30, mas não faz sentido imprimir 85 cópias porque 85 \times 0.25 = 21.25 é maior do que 101 \times 0.20 = 20.20.


Agora vamos inverter o problema. Vamos supôr que você é a gráfica e quer evitar esse tipo de cliente insuportável, fazendo o preço ir ficando mais barato proporcionalmente com o número de impressões, mas mantendo a função monótona (crescendo).

Poderíamos pensar em funções que crescem cada vez mais devagar…

log x

… mas parece complicado achar uma função que não nos dê prejuízo quando o cliente quiser muitas cópias e parece especialmente complicado explicar para o cliente que o preço de x cópias é um monte de constantes multiplicadas pelo logaritmo de x.

Então talvez seja melhor pensar em funções de primeiro grau mesmo.

Se você separar todas as funções que encontramos na tabela de preços do problema anterior e colocá-las num gráfico, você vai ver que a interseção delas só acontece num ponto: o ponto x = 0.

várias funções

(esse gráfico foi um oferecimento Wolfram Alpha)

Uma forma de resolver o problema é fazer com que as interseções sejam nos pontos onde o preço das impressões muda. Isso se faz movendo cada uma das funções um pouquinho pra cima, isso é, adicionando constantes às funções de primeiro grau.

Por exemplo: 3 cópias custam R$ 2,10. Se a partir de 4 cópias quisermos que as cópias custem R$ 0,50 em vez de R$ 0,70, podemos forçar que 4 cópias custem R$ 2,10 + R$ 0,50 = R$ 2,60. R$ 2,60 é R$ 2,00 + R$ 0,60. Logo, em vez de usarmos a função de preço f(x) = 0.5x para x entre 4 e 10, podemos usar a função f(x) = 0.5x + 0.6.

Se repetirmos o mesmo raciocínio para as outras interseções, a tabela de preços final fica assim:

De 01 a 03 unidades R$ 0,70 cada
De 04 a 10 unidades R$ 0,60 fixo + R$ 0,50 cada
De 11 a 20 unidades R$ 1,60 fixo + R$ 0,40 cada
De 21 a 50 unidades R$ 3,60 fixo + R$ 0,30 cada
De 51 a 100 unidades R$ 6,10 fixo + R$ 0,25 cada
Acima de 100 unidades R$ 11,10 fixo + R$ 0,20 cada

(Isso aqui é só um exercício. Por favor, não façam isso, donos de gráficas!)

Agora note que as coisas passam a fazer mais sentido (embora muito mais caras):

– 3 cópias custam R$ 2,10 e 4 cópias custam R$ 2,60;
– 10 cópias custam R$ 5,60 e 11 cópias custam R$ 6,00;
– 20 cópias custam R$ 9,60 e 21 cópias custam R$ 9,90;
– 50 cópias custam R$ 18,60 e 51 cópias custam R$ 18,85;
– 100 cópias custam R$ 31,10 e 101 cópias custam R$ 31,30.

O gráfico monótono (e bonito) comprova:

gráfico da tabela da minha futura gráfica

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é.

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.

Spivak sobre definições e teoremas

ATENÇÃO: Este conteúdo foi publicado há 7 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

“The reader probably suspects that the modern Stokes’ Theorem is at least as difficult as the classical theorems derived from it. On the contrary, it is a very simple consequence of yet another version of Stokes’ Theorem; this very abstract version is the final and main result of Chapter 4. It is entirely reasonable to suppose that the difficulties so far avoided must be hidden here. Yet the proof of this theorem is, in the mathematician’s sense, an utter triviality — a straight-forward computation. On the other hand, even the statement of this triviality cannot be understood without a horde of difficult definitions from Chapter 4. There are good reasons why the theorems should all be easy and the definitions hard. As the evolution of Stokes’ Theorem revealed, a single simple principle can masquerade as several difficult results; the proofs of many theorems involve merely stripping away the disguise. The definitions, on the other hand, serve a twofold purpose: they are rigorous replacements for vague notions, and machinery for elegant proofs.”

Michael Spivak, prefácio de “Calculus on Manifolds”.

Ano novo

ATENÇÃO: Este conteúdo foi publicado há 7 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Aprendo muito na Universidade. Não tanto nas aulas do currículo obrigatório, mas sem dúvidas naquelas que frequento porque realmente quero aprender, principalmente quando essas me desafiam. A falta de desafio nos torna medíocres e foi a falta de desafio que me tirou a vontade de ir para as aulas no semestre passado.

Mais do que na sala de aula, porém, aprendo nas bibliotecas, corredores e gramados. Os espaços de vivência e debates são os locais mais importantes da universidade (e usuários do DaD — diploma a distância — infelizmente talvez nunca experimentem isso). Nestes espaços aprendemos e reproduzimos discursos e ideias que nos fazem pensar e criticar a realidade.

Estes espaços não tem nada de especial e não são exclusivos das universidades, mas acredito que nas universidades é mais fácil criar essas rodas porque há muitas pessoas com interesses em comum. Além disso, eles não se limitam a debates políticos e filosóficos; deles pode surgir um problema puramente matemático.

Sem mais enrolação, vou narrar o fato: Acabou ontem a primeira semana de aulas da USP. Houve recepção aos calouros em todos os cantos do campus e eu passei pelo menos 14 horas todos os dias lá caminhando principalmente entre IME, FAU e FFLCH.

Definitivamente foi uma das semanas mais interessantes que já vivi nesta universidade até o presente momento. Li ótimos livros, participei de ótimas conversas e aulas-debate e conheci várias pessoas muito interessantes. Não vou entrar em detalhes sobre tudo isso, porém, visto que isto foge do assunto que planejei pra esse texto. Pra ser sincero, agora é que percebi: toda essa introdução foi exagerada e criou falsas expectativas para os leitores. Desculpem pelo meu pensamento caótico. Com efeito, sem mais enrolação (agora eu prometo), o ponto que quero chegar é o seguinte:

Sejam a, b e c números naturais. Sejam A e B subconjuntos dos naturais. Seja f : A → B uma função natural bijetora definida por f(x) = a * ⌊x / c⌋ + ⌊(x mod c) / b⌋. Qual pode ser o conjunto A para termos B = ℕ? Qual a função inversa f⁻¹?

Não é um bom problema? Tente resolver antes de continuar a leitura.

Certo. Para manter o texto divertido (e possivelmente confuso, confesso) prosseguirei de trás pra frente.

Tuitei esse problema às 15h de quinta-feira. Antes eu havia passado algumas horas caído por causa do cansaço. Antes eu tuitei que nunca tinha pensado em inversas de funções com módulo. Isso porque eu determinei a inversa dessa estranha função que atribui uma quantidade inteira de dinheiro (em reais) a uma quantidade de cervejas. Cheguei a essa estranha função porque algumas horas antes estava vendendo fichas de cervejas na festa da Calourada Unificada do DCE da USP. Uma cerveja custava R$ 2,00 e três cervejas custavam R$ 5,00.

Simplificando o caminho, agora de frente pra trás: Trabalhar de caixa correndo pra contar dinheiro (havia muita fila) inseriu na minha mente uma estranha função que me permitiu, mesmo com extremo cansaço, criar um problema muito divertido de matemática. (Eu passei o ano passado inteiro no IME e não inventei nenhum problema que eu tenha gostado.)

Agora vem a melhor parte: o problema em linguagem matemática parece assustador para a maioria, mas sua solução é absolutamente trivial se você sabe de onde ele veio e ficar restrito ao caso em que b ≤ c. De fato, concentre-se na venda de cervejas. A pergunta “Qual pode ser o conjunto A para termos B = ℕ?” é equivalente a “Qual os valores que não necessitam troco?” e a pergunta “Qual a função inversa?” é equivalente a “Qual a função que atribui número de cervejas ao seu preço?”

Bem… Não vou me alongar porque escrever recordou-me que preciso resolver o problema pro caso geral. Aproveitem o ano & bons estudos!

Probabilidade

ATENÇÃO: Este conteúdo foi publicado há 8 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Curiosamente as melhores aulas (em conteúdo e rigor matemático) que estou tendo no IMEUSP neste semestre são as de Introdução à Probabilidade e Estatística I (MAE 121). Digo “curiosamente” porque

0. Nunca gostei de estatística (e acreditava que este seria o foco da disciplina);

1. Álgebra e Cálculo tem um conteúdo que acredito ser bem mais matemático;

2. Sinceramente, não esperava nada desta disciplina.

Surpreendi-me porque, de fato, desde que entramos na matéria de Probabilidade tudo até agora foi definido ou provado formalmente. Por exemplo, espaço de probabilidade é a tripla (\Omega, F, P), onde \Omega é o espaço amostral, F é uma \sigma-álgebra que representa o conjunto dos eventos e P: F \rightarrow [0, 1] é a função probabilidade. Com três axiomas em cima dessa definição provamos uma porção de coisas.

Muito interessante. A probabilidade é uma área que eu desconhecia completamente (e discriminava em pensamento por andar sempre junto com Estatística), mas que é muito mais legal (em nível matemático) do que eu pensava.

Probability and Measure
Creative Commons License photo credit: John-Morgan

Economize tempo assistindo os vídeos do IMPA

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Poucos sabem que o Instituto de Matemática Pura e Aplicada possui em seu site diversas vídeo-aulas que fazem parte dos semestrais Cursos do Programa de Aperfeiçoamento de Professores de Matemática do Ensino Médio. Minha dica é simples e limita-se

  1. aos que querem aprender a matemática do Ensino Médio aprofundada e demonstrada bem rápido,
  2. aos que querem relembrar estes conteúdos, ou
  3. aos que, como eu, estão no terceiro ano, querem estudar pro vestibular e não perder tempo nas aulas de matemática convencionais.

Ao invés de gastar seu tempo ou seu dinheiro, gaste banda: baixe e assista os vídeos do CAPEM do IMPA.

Observação: Por mais que possa parecer, não estou ganhando nada pra fazer propaganda dos vídeos deles e nem eles com vocês assistindo-os. :)