terça-feira, 27 de dezembro de 2016

Números primos

Gosto dos números primos. São rebeldes, não se deixam arrumar.
Por exemplo, se tivermos um certo número de azulejos e os quisermos arrumar em paineis rectangulares, há casos em que isso é possível e outros em que não!
Com 15 azulejos, temos duas soluções


Se em vez de azulejos, fossem chocolates, podíamos arrumá-los em 3 grupos de 5 ou em 5 grupos de três, o que dá muito jeito na hora de repartir.
Mas se fossem 13, o caso mudaria de figura, pois não há qualquer hipótese de os arrumar num rectângulo, 13 é um número primo!


Um número primo não tem qualquer divisor, para além dele próprio e da unidade.
E afinal quantos divisores tem um número? Temos de procurar os factores primos e todas as combinações entre eles.

Se quisermos saber quantos são os divisores de 48, por exemplo, como 48 = 2x2x2x2x3, o factor  2 surge 4 vezes e o factor 3 surge 1 vez, pelo que o número de divisores de 48 é 10, o número de elementos do produto cartesiano dos conjuntos {1, 2, 4, 8, 16} e {1, 3}, que são as formas como os factores 2 e 3 podem figuram num divisor de 48.
Feitas as contas, os 10 divisores de 48 são {1, 2, 3, 4, 6, 8, 12, 16, 24, 48}.

Um número primo muito falado recentemente é 557, o salário mínimo nacional, pelo que não é possível dividir 557 € em valores de montantes iguais. Seria essa a ideia malévola de quem fixou este número?

A propósito, perguntava há uns dias a alunos meus da área da Comunicação se já tinham visto um programa por dentro. Usando PENCILcode, fiz um programa muito simples, que todos entenderam, e que desenhava uma estrela com um número variável de pontas. Quando lhes perguntei porque seria que o programa funcionava melhor com certos números - primos - um deles logo comentou que deveria ser obra de Deus...

sábado, 29 de outubro de 2016

A fila mal comportada

Estou no último lugar de uma fila de 100 passageiros com lugares marcados, num avião com 100 lugares. O primeiro da fila (onde é que eu já vi...) senta-se num lugar à sorte! Os passageiros seguintes vão-se sentando nos lugares que lhes estão destinados, e sempre que um deles encontra o lugar já ocupado senta-se também num lugar ainda livre, à sorte. Qual é a probabilidade de eu encontrar o meu lugar livre?


A probabilidade é 50%, como se pode notar por exemplo aqui.
Mas precisamos de fazer contas complicadas para chegar a esta conclusão? Eu diria que não...
Pensemos.
O primeiro passageiro escolhe à sorte um lugar, que pode ser o dele mesmo, e então eu vou sentar-me no meu, que pode ser o meu, e então eu vou trocar com ele, ou que pode ser o de um terceiro passageiro.
Neste último caso, todos se vão sentando nos seus lugares, até chegar a vez deste passageiro, que, como encontra o seu lugar ocupado, se vai sentar num lugar à sorte, de entre os livres.
Pode escolher o lugar do primeiro passageiro da fila, que ainda está livre, e então o meu lugar fica garantido, pode escolher o meu lugar, e então vou ficar com o lugar do primeiro passageiro, ou então um dos restantes lugares ainda livres, e a situação repete-se, até acontecer uma das duas situações: ou sai o lugar do primeiro ou sai o meu!
E as probabilidades são exactamente iguais.

segunda-feira, 22 de agosto de 2016

pixeis e ppis (2/2)

[recomendo ao leitor que começe por ler a primeira parte deste artigo]

O ecrã do meu televisor tem uma resolução de 1920x1080 pixeis, e o ecrã do meu tablet também. No entanto, um tem uma diagonal de 44 polegadas e o outro uma diagonal de 7 polegadas. Conclusão, os pixeis no meu tablet serão mais pequenos que os do meu televisor, porque cabem mais numa polegada (2.54 cm), ou seja, o meu tablet tem mais ppi (pixeis por polegada) ou dpi (dots por polegada).
Já agora, quantos?
Os velhos ecrãs com factor de forma 4:3, como eram os primitivos televisores, tinham uma propriedade interessante devida a Pitágoras: a sua diagonal seria proporcional a 5. Com a alta definição, optou-se pelo factor de forma 16:9, sendo a correspondente diagonal proporcional a (é fazer as contas) aproximadamente 18.5.
Um ecrã com diagonal de 44 polegadas terá as dimensões aproximadas de 38x21.5 polegadas, e se tiver a resolução de 1920x1080 pixeis, em cada polegada linear caberão uns 50 pixeis. É de 50 ppi.
Já no que respeita ao meu tablet, as suas 7 polegadas de diagonal correspondem às dimensões aproximadas de 6x3.5 polegadas, ou seja, para a mesma resolução, terá aproximadamente 310 ppi.
Calculando as dimensões de cada pixel, os pixeis do meu televisor serão de aproximadamente 0.5x0.5 mm, enquanto que os do meu tablet serão de aproximadamente 0.08x0.08 mm. Bem mais pequenos.
Entra no entanto aqui um factor, que é a distância a que se observa a imagem, pois o que conta efectivamente é a dimensão da imagem formada na retina, o sensor óptico humano. Como facilmente se percebe, quanto mais longe estiver a imagem, menos visíveis serão os pixeis individuais.
Um ecrã retina será um ecrã com pixeis tão pequenos que a nossa retina não os consegue distinguir individualmente, como os de certos equipamentos iPad e MacBook, por exemplo.
E a tal imagem de 2048x2048 pixeis e 72 ppi do meu Tio Francisco?
Em papel, tudo bem. Como 2048/72 são aproximadamente 28.5 polegadas, ou 70 cm, tal quer dizer que a imagem deve ser mostrada num suporte com 70x70 cm. Não ficaria muito bem, mas vista a uma distância aceitável daria o efeito pretendido. E no nosso tablet ou smartphone? Não cabe! E há duas soluções, ou encolher a imagem (opção do Facebook) ou mostrar por partes (scroll, opção do Flickr).
É por isso que eu digo que não há milagres...
Claro que ainda sobra um aspecto, a gama dinâmica, o número de bits usado para representar cada pixel. Até porque não é possível representar todas as cores do universo visível numa codificação RGB ou outra. A natureza é infinitamente mais rica.
Fica para outro dia...

sábado, 20 de agosto de 2016

pixeis e ppis (1/2)

Dizia há uns dias o meu Tio Francisco que a mesma imagem de 2048x2048 pixeis e 72 ppi (pixeis por polegada) produzia resultados diferentes no Flickr e no Facebook, e interrogava-se porquê? Teria feito algo de errado?
Claro que não fez nada de errado, a não ser pensar que iria ter os mesmos resultados...
Responder a esta questão com profundidade será contudo uma longa história, que nos levará a pensar como podemos registar um instante (instantâneo) da realidade iluminada e depois como podemos reproduzir esse registo.
Portanto, há a realidade, a iluminação, o sensor, a formação da imagem, o tempo de registo, o suporte, a digitalização, os algoritmos de compressão, o dispositivo de reprodução, e finalmente os nossos olhos e cérebro. Toda uma cadeia implicada nesta coisa aparentemente simples que é publicar uma fotografia no Flickr, no 500px ou no Facebook.
Uma imagem de 2048x2048 pixeis em si é todo um mundo... Será uma imagem raw, isto é, tal como foi registada pelo sensor, com o esplendor de 2048x2048x3x2 byte, ou seja, 24 MB de informação (3 cores por pixel e 2 byte (16 bit) por cor)? Se não é, foi comprimida, por um algoritmo que tenta eliminar informação "redundante" para o olho "médio", como por exemplo os algoritmos JPEG (Joint Photographic Experts Group). Estes algoritmos têm perdas, ao contrário dos algoritmos do tipo ZIP ou RAR, usados obrigatoriamente para compressão de ficheiros de programas, que não podem ter perdas de informação, mas que em regra comprimem bastante menos.
Além disso, os algoritmos com perdas, como os JPEG, admitem factores de compressão que permitem conjugar de alguma forma esses dois factores contraditórios - fidelidade e tamanho do ficheiro final. Quem já usou o PhotoShop sabe isto bem.
Eu, por mim, costumo avaliar as perdas pela tamanho do ficheiro, em relação ao ficheiro sem compressão. Uma imagem de 4000x3000 pixeis, 3 cores por pixel e 2 byte por cor tem cerca de 72 MB de informação. No formato JPEG produzido pela máquina fotográfica, terá uns 6 a 8 MB, e se a armazenar no Google Photos no formato de 2048x1536 pixeis e fizer em seguida o seu download obtenho um ficheiro de 400 a 600 kB com boa qualidade Internet, e umas 20 vezes menor que o ficheiro raw inicial. Como não há milagres, houve obviamente perda de informação, a maior parte irrelevante, mas informação, certamente.
A imagem do meu Tio Francisco no Facebook tem um tamanho (peso) de 680 kB, enquanto que a original no Flickr tem 3.2 MB, quase 5 vezes mais informação. Logo, são necessariamente diferentes.
E os ppis (pixeis per inch)? Claro que são importantes. Mas de outro ponto de vista. Voltarei a isso na continuação deste artigo.

segunda-feira, 13 de abril de 2015

Dois dados equitativos

O Público de ontem pergunta-nos se será possível numerar as faces de dois dados de modo que as somas das faces variem entre 1 e 12 e sejam todas igualmente prováveis.
Com dois dados normais, os 6x6 = 36 resultados possíveis não são igualmente prováveis. Basta listá-los todos e contá-los. Podemos utilizar um quadrado 6x6:


e chegaremos facilmente à distribuição de resultados


Facilmente se encontram contudo duas possibilidades de construir os tais dados equitativos:

 

em que é notório que a distribuição de resultados é uniforme. Qualquer resultado tem a probabilidade 1/12 de acontecer.
E até há uma solução em que um dos dados é o convencional. Quantas soluções diferentes haverá?

sexta-feira, 2 de janeiro de 2015

5 x 13 x 31

2015 é o produto de três números primos (2015 = 5 x 13 x 31). Se tivermos uma caixinha em forma de cubo para cada um dos anos, podemos arrumá-las todas num paralelepípedo com uma base de 13 x 31 cubos e altura 5 cubos, e chegar facilmente a cada uma calculando o resto da divisão do ano respectivo por 5, 13 e 31 e usando os restos como coordenadas da posição da caixa (figura simplificada).

Nos anos anteriores, 2014 = 2 x 19 x 53, e a arrumação teve de ser em duas camadas de 19 x 53 caixas, num nível as caixas correspondentes a anos pares e no outro as caixas correspondentes a anos ímpares, e 2013 = 3 x 11 x 61, pelo que as caixas puderam ser arrumadas em 3 camadas de 11 x 61 caixas.
Em 2012, a arrumação foi um pouco mais difícil, pois há dois factores repetidos e um muito grande, 2012 = 2 x 2 x 503, o que dá 4 filas de 503 caixas, e em 2011 só houve uma maneira de arrumar as caixas: numa fila de 2011 (2011 = 1 x 1 x 2011).
2011 é um número primo.
Aparentemente, este ciclo terá uma forte relação com a nossa crise económica e com os factores que a podem controlar, e é de notar que evoluímos de uma longa fila de 2011 caixas (um factor primo) para uma arrumação cada vez mais compacta (3 factores primos, não muito grandes).
E como será daqui para a frente?
Bem, 2016 = 2 x 2 x 2 x 2 x 2 x 3 x 3 x 7, o que dá uma multiplicidade de combinações, como já sabemos, mas o pior é que 2017 é outra vez um número primo, sem arrumação compacta possível.
Lá virá outra vez a longa fila...

domingo, 14 de dezembro de 2014

Contar quadrados...

Uma versão ligeiramente diferente de um problema antigo.
Olhemos para o quadrado da figura abaixo, que tem uma área de 8x8=64 quadrados unitários.
Se o recortarmos em quatro peças, conforme assinalado e rearrumarmos as peças de acordo com a sua posição no rectângulo representado, verifica-se que obtemos uma figura com uma área de 5x13=65 quadrados unitários! Apareceu um quadrado!
Qual é a explicação? Deixo aqui o desafio...