Arquivo da tag: 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.

Triângulo de Pascal mod m

ATENÇÃO: Este conteúdo foi publicado há 6 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.

Este post possui intencionalmente apenas imagens e códigos.

Uso do programa que gera triângulo de Pascal mod m

mod 2

Pascal's Triangle mod 2

mod 3

Pascal's Triangle mod 3

mod 5

Pascal's Triangle mod 5

mod 7

Pascal's Triangle mod 7

mod 12

Pascal's Triangle mod 12

mod 23

Pascal's Triangle mod 23

Código-fonte (com alguns bugs inofensivos — procure XXX)

/* pascal -- generate colored Pascal's triangles in XPM format
 
   Copyright (C) 2011 Tiago Madeira <madeira@ime.usp.br>
 
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3, or (at your option)
   any later version.
 
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
 
   You can read a copy of the GNU General Public License at
   http://www.gnu.org/licenses/gpl-3.0.txt */
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <getopt.h>
#include <math.h>
 
#define DEFMOD 2
#define DEFSIZE 300
#define DEFPADDING 8
 
int mod = DEFMOD;
int size = DEFSIZE;
int padding = DEFPADDING;
 
char makecolors[6][4] = {
	"001", "010", "100", "110", "101", "001"
};
 
struct option longopts[] = {
	{"help", 0, 0, 'h'},
	{"padding", 1, 0, 'p'},
	{"size", 1, 0, 's'},
	{"mod", 1, 0, 'm'},
	{0, 0, 0, 0}
};
 
char *program_name;
 
void try_help() {
	fprintf(stderr, "Try `%s --help' for more information.\n", program_name);
}
 
void help() {
	printf("Usage: %s [OPTION]... [FILE]\n", program_name);
	printf("Generate colored Pascal's triangles (XPM format).\n\n");
	printf("Mandatory arguments to long options are mandatory for short options too.\n\n");
	printf("  -h, --help        print this help\n");
	printf("  -m, --mod=M       paint with different colors numbers mod M\n");
	printf("  -p, --padding=SZ  image padding (margin) in pixels\n\n");
	printf("  -s, --size=SZ     generate SZ lines of Pascal's triangle\n\n");
	printf("With no FILE, or when FILE is -, write to standard output.\n\n");
	printf("Report bugs to <madeira@ime.usp.br>.\n");
}
 
int baselog(int n, int base) {
	return ceil(log(n) / log(base));
}
 
void *xmalloc(size_t size) {
	void *x = malloc(size);
	if (x == NULL) {
		fprintf(stderr, "There is no enough memory to allocate.\n");
		exit(3);
	}
	return x;
}
 
int main(int argc, char **argv) {
	int optc, tofile;
	int i, j;
	int width, height, chars;
	char **color, rgb[7];
	int one, pos;
	int *pascal;
	char *line;
 
	program_name = argv[0];
	while ((optc = getopt_long(argc, argv, "hm:p:s:", longopts, (int *)0)) != -1) {
		switch (optc) {
		case 'h':
			help();
			return 0;
		case 'm':
			mod = atoi(optarg);
			if (mod > 48) { /* XXX */
				fprintf(stderr, "At the moment, this program supports only mod <= 48 (color generation limit).\n");
				return 4;
			}
			if (mod > 26) { /* XXX */
				fprintf(stderr, "At the moment, this program supports only mod <= 26 (bad implementation limit).\n");
				return 5;
			}
			break;
		case 'p':
			padding = atoi(optarg);
			break;
		case 's':
			size = atoi(optarg);
			break;
		default:
			try_help();
			return 1;
		}
	}
	if (optind < argc && strcmp("-", argv[optind])) {
		if (freopen(argv[optind], "w", stdout) == NULL) {
			fprintf(stderr, "Can't open `%s' for writing.\n", argv[optind]);
			return 2;
		}
		tofile = 1;
	} else {
		tofile = 0;
	}
 
	printf("static char *a_xpm[] = {\n");
	width = size * 2 + padding * 2;
	height = size * 2 + padding * 2;
	chars = baselog(mod, 26);
	printf(""%d %d %d %d",\n", width, height, mod + 1, chars);
	color = xmalloc(sizeof(color[0]) * (mod+1));
	rgb[6] = '�';
 
	printf("\"");
	color[mod] = xmalloc(sizeof(color[mod][0]) * (chars + 1));
	for (j = 0; j < chars; j++) {
		color[mod][j] = ' ';
	}
	color[mod][chars] = '�';
	printf("%s c #000000\",\n", color[mod]);
 
	for (i = 0; i < mod; i++) {
		color[i] = xmalloc(sizeof(color[i][0]) * (chars + 1));
		if (i == 0) {
			for (j = 0; j < chars; j++) {
				color[i][j] = 'a';
			}
			color[i][chars] = '�';
		} else {
			strcpy(color[i], color[i-1]);
			for (j = chars-1; j >= 0; j--) {
				if (color[i][j] == 'z') {
					color[i][j] = 'a';
				} else {
					color[i][j]++;
					break;
				}
			}
		}
		one = 255 / pow(2, i / 6);
		sprintf(rgb, "%02x%02x%02x", makecolors[i%6][0] == '1' ? one : 0,
				makecolors[i%6][1] == '1' ? one : 0, makecolors[i%6][2] == '1' ? one : 0);
		printf("\"%s c #%s\",\n", color[i], rgb);
	}
 
	line = xmalloc(sizeof(line[0]) * (width+1));
	pascal = xmalloc(sizeof(pascal[0]) * size);
 
	line[width] = '�';
	for (j = 0; j < width; j++) {
		line[j] = ' ';
	}
	for (i = 0; i < padding; i++) {
		printf("\"%s\",\n", line);
	}
 
	memset(pascal, 0, sizeof(pascal[0]) * size);
	pascal[0] = 1;
 
	for (i = 0; i < size; i++) {
		for (j = i; j >= 0; j--) {
			if (j != 0) {
				pascal[j] = (pascal[j-1] + pascal[j]) % mod;
			}
			pos = padding + 2*j + (size - 1 - i);
			/* XXX a implementacao de line ficou toda errada e so estou pegando
			 * o primeiro caractere de color aqui. precisa ser reescrito. */
			line[pos] = line[pos+1] = *color[pascal[j]];
		}
		printf("\"%s\",\n\"%s\"%s\n", line, line, i == size-1 && !padding ? "" : ",");
	}
 
	line[width] = '�';
	for (j = 0; j < width; j++) {
		line[j] = ' ';
	}
	for (i = 0; i < padding; i++) {
		printf("\"%s\"%s\n", line, i == padding-1 ? "" : ",");
	}
	printf("};\n");
 
	if (tofile) {
		fclose(stdout);
	}
	return 0;
}

(Download — 5kb)

Coordenadas homogêneas

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.

Conheci as coordenadas homogêneas por acaso. Era 2004, ganhei a modalidade iniciação da Olimpíada Brasileira de Informática e passei o inverno estudando C, acho que por dois motivos: interesse pelos problemas da modalidade programação e desejo de aproveitar bem o curso que os medalhistas fazem na UNICAMP; ou talvez fosse apenas falta do que fazer ou curiosidade mesmo. Não importa.

Confundo os cursos de 2004, 2005 e 2006, mas lembro que no primeiro aprendi com um monitor sobre recursão, representação de grafos e busca em profundidade. Lembro também que foi em 2004 que conheci o CLRS (livro que comprei alguns meses depois e tenho na cabeceira até hoje). Esse post, porém, é sobre um acontecimento mais aleatório relacionado a esse curso e, ouso afirmar, digno de figurar n’O Andar do Bêbado do Mlodinow.

O pessoal da modalidade programação ia tirar cópias de um livro do Stolfi e do Rezende, chamado “Fundamentos de Geometria Computacional” (dá pra baixar aqui). Nem sabia do que estavam tirando xerox, mas vi que era barato e que todos os mais velhos estavam querendo, então também pedi.

Folheei o livro, não entendi nada, deixei num canto e voltei a abrir alguns anos depois, não lembro exatamente quando. E foi aí que fez-se a luz. A primeira parte é sobre coordenadas homogêneas.

Coordenadas homogêneas? A ideia parece simples (até demais) pra ser poderosa. Basicamente você representa uma coordenada em (X, Y) \in \mathbb{R}^2 com uma tripla ordenada [w, x, y] tal que x = \frac{X}{w} e y = \frac{Y}{w}. A reta tem a mesma representação.

1
2
3
4
5
struct ponto {
	int w, x, y;
};
 
typedef ponto reta;

E o que isso tem demais? Você deixa de precisar de pontos flutuantes pra maioria das operações geométricas; ganha pontos no infinito (eles são a interseção entre retas paralelas!) que permitem fazer fórmulas sem preocupação com casos especiais, usar a mesma fórmula pra determinar uma reta gerada por dois pontos ou por um ponto e um vetor etc.; tem representações iguais (e dualidade) entre pontos e retas (e.g. interseção entre retas p e q = reta determinada por pontos p e q); e mais um monte de outras coisas.

Uau! Como eu não ouvi falar disso antes? Eu não sei a razão, mas, embora tenham várias vantagens, as coordenadas homogêneas não são muito populares na universidade, nem entre os maratonistas. No entanto, são usadas em projetos grandes que usam muita geometria (e.g. OpenGL).

Quero código! Vou mostrar como resolvi o problema Symmetry (2002 TopCoder Inv Round 4 – Division I, Level Three).

O enunciado é simples: Dados n (2 \leq n \leq 200) pontos inteiros (com coordenadas de -10000 a 10000) determinar quantas linhas de simetria existem entre eles.

Dá pra fazer em O(n^3) com a seguinte ideia:

  1. Crie uma árvore binária balanceada indexada por retas. (em C++, map <reta,int>)
  2. Para cada par de pontos, determine a reta de simetria entre eles e adicione 2 a essa reta na árvore binária. (O(n^2 log n))
  3. Para cada reta na árvore binária, adicione 1 para cada ponto que pertence a essa reta. (O(n^3))
  4. É fácil ver que a reta é uma reta de simetria do conjunto de pontos se e somente se seu valor na árvore binária for n.

O problema geométrico está no segundo passo: determinar a reta de simetria entre dois pontos. Sejam esses pontos p e q. É preciso:

  1. Determinar o ponto médio entre p e q.
  2. Determinar a reta que passa por p e q (o enunciado garante que p != q).
  3. Determinar uma reta (ou um vetor) perpendicular à reta do passo acima.
  4. Determinar a reta que passa pelo ponto médio e tem a direção do vetor perpendicular do passo 3.

Determinar o ponto médio sem usar ponto flutuante seria trivial de qualquer forma (basta multiplicar todas as coordenadas por dois), mas com coordenadas homogêneas isso é desnecessário. É fácil ver que o ponto médio m entre p = [w_0, x_0, y_0] e q = [w_1, x_1, y_1] é:

m = [ 2 w_0 w_1 , w_1 x_0 + w_0 x_1 , w_1 y_0 + w_0 q_1 ]

1
2
3
ponto ponto_medio(ponto p, ponto q) {
	return (ponto) { 2*p.w*q.w, q.w*p.x+q.x*p.w, q.w*p.y+q.y*p.w };
}

Três pontos [w_0, x_0, y_0], [w_1, x_1, y_1], [w_2, x_2, y_2] são colineares se

 \left| \begin{array}{ccc} w_0 & x_0 & y_0 \\ w_1 & x_1 & y_1 \\ w_2 & x_2 & y_2 \end{array} \right| = 0 ,

o que nos permite concluir que a reta r = \langle W, X, Y \rangle que passa por p = [ w_0, x_0, y_0 ] e q = [ w_1, x_1, y_1 ] é:

r = \langle +x_0 y_1 - y_0 x_1, -w_0 y_1 + w_1 y_0, w_0 x_1 - w_1 x_0\rangle.

1
2
3
ponto reta_determinada_por(ponto p, ponto q) {
	return (reta) { +p.x*q.y-q.x*p.y, -p.w*q.y+q.w*p.y, +p.w*q.x-q.w*p.x };
}

(um ponto [w, x, y] pertence a r se Ww + Xx + Yy = 0)

1
2
3
int ponto_na_reta(ponto p, reta r) {
	return p.w*r.w + p.x*r.x + p.y*r.y == 0;
}

Agora a parte mais legal: a fórmula para determinar uma reta que passa por dois pontos funciona com pontos no infinito (pensemos em pontos no infinito como vetores, porque eles tem direção mas tem w = 0): o resultado é a reta determinada por um ponto e uma direção. O vetor perpendicular à reta \langle W, X, Y \rangle é [ 0, X, Y ].

1
2
3
ponto ponto_infinito_na_reta_perpendicular(reta r) {
	return (reta) { 0, r.x, r.y };
}

E isso é tudo. Agora basta criar uma representação única da reta pra guardar na árvore binária.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
reta reformata_reta(reta r) {
	if (r.w < 0) {
		r.w = -r.w;
		r.x = -r.x;
		r.y = -r.y;
	} else if (r.w == 0) {
		if (r.x < 0) {
			r.x = -r.x;
			r.y = -r.y;
		} else if (r.x == 0 && r.y < 0) {
			r.y = -r.y;
		}
	}
	int d = gcd(r.w, gcd(abs(r.x), abs(r.y)));
	return (reta) { r.w/d, r.x/d, r.y/d };
}

Usando essas funções, primeiro e segundo passos da solução são:

map <reta,int> M;
for (int i = 0; i < n; i++) {
	for (int j = i+1; j < n; j++) {
		reta s = reformata_reta(reta_determinada_por(P[i], P[j]));
		ponto pm = ponto_medio(P[i], P[j]);
		ponto dir = ponto_infinito_na_reta_perpendicular(s);
		reta r = reformata_reta(reta_determinada_por(pm, dir));
		if (M.find(s) == M.end())
			M[s] = 0;
		if (M.find(r) == M.end())
			M[r] = 0;
		M[r]+= 2;
	}
}

Terceiro e o quarto são:

1
2
3
4
5
6
7
8
int output = 0;
for (map <reta,int>::iterator i = M.begin(); i != M.end(); i++) {
	for (int j = 0; j < n; j++)
		if (ponto_na_reta(P[j], i->first))
			i->second++;
	if (i->second == n)
		output++;
}

O código completo ficou com umas 90 linhas com comentários e linhas em branco e foi aceito na primeira submissão (ok, na verdade na segunda, mas não foi devido à geometria muito menos à precisão): symmetry.cpp. Não é lindo?

Paradoxo do medo de errar

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.

Meu primo tuitou há alguns minutos que “o maior erro na vida é ter medo de errar” e a frase me deixou pensativo.

Suponha que você leia essa frase e resolva “Então, para não errar, não vou ter medo de errar”. Nesse caso você está tendo medo de um erro (o erro seria o medo de errar); absurdo!

Suponha, por outro lado, que você leia essa frase e resolva “Então vou continuar com medo de errar.” Neste caso, você está cometendo o maior erro (sem medo dele), então você perdeu o medo de errar. Absurdo novamente!

Portanto, conclui-se que o maior erro na vida não deve ser o medo de errar. qed.

PS: Perdoem-me por possíveis falhas, tive que escrever correndo para não me atrasar para o tango.

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

Diálogos politécnicos #1

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.

— A notação que os físicos e matemáticos usam para a derivada é muito ruim, não faz sentido nenhum.

— É verdade, não dá nem pra usar regra da cadeia!

048
Creative Commons License photo credit: austins_irish_pirate

Algoritmo da Divisão

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.

Warning! Isto não é ficção.

Acabara de provar o Algoritmo da Divisão. Olhou pro quadro maravilhado. Contemplou o seu resultado por quase um minuto. Então, virou para os seus alunos. E disse:

Naquela época as pessoas não usavam roupas. Roupas eram caras, era privilégio da nobreza. Sempre que eu provo este resultado eu imagino Euclides provando-o e correndo aos seus amigos contar: “Descobri o Algoritmo da Divisão! Descobri o Algoritmo da Divisão!” e todos ficando excitados com a descoberta.

A turma do Bacharelado em Matemática Pura, assustada, fingiu que não ouviu. E de repente percebeu pela primeira vez que é compreensível o povo achar que matemática é coisa de gente maluca…

2/22/08
Creative Commons License photo credit: bourgeoisbee