savoy082

Pt En O problema deste post é muito engraçado porque é muito simples de enunciar e o resultado é um facto engraçado sobre os números inteiros! Problema: Mostra que qualquer número inteiro tem um múltiplo que se escreve apenas com os dígitos $0$ e $1$. Solução: Por comodidade, sejam $c(1) = 1$ e $c(n+1) = 10^{n} + c(n), n > 0$, i.e. $c(k)$ é o número que é escrito por $k$ dígitos $1$ de seguida. Consideramos a lista $c(1), c(2), \cdots, c(|n|-1), c(|n|)$. Ou existe algum $k$ tal que $n\ |\ c(k)$, ou pelo princípio do pombal existem 2 índices $i>j$ com $c(i) \equiv c(j) \mod |n|$. Mas se $c(i)$ e $c(j)$ deixam o mesmo resto na divisão por $n$ então $c(i) - c(j) \equiv 0 \mod{|n|}$ e $c(i) - c(j)$ é escrito apenas com $0$s e $1$s. Por exemplo, para o número $4$ consideramos os números $1, 11, 111, 1111$. É fácil de ver que nenhum desses quatro números é múltiplo de $4$, portanto precisamos de recorrer à segunda parte da demonstração. É fácil de ver que $11,111$ têm o mesmo resto ...

(An english translation of this post can be found after the portuguese version, here ) O objetivo deste post é introduzir o conceito de grupo de uma maneira que seja entendível por um aluno do secundário. Os grupos são objetos matemáticos cuja utilidade advém do nível de abstração que representam, em relação aos objetos matemáticos mais usuais, tais como: os números inteiros, racionais e reais ($\mathbb{Z}, \mathbb{Q}, \mathbb{R}$); as funções (reais de variável real) com a soma usual e composição de funções ($f \circ g$); rotações e simetrias de polígonos regulares. Tentaremos também justificar a importância da noção de grupo através de alguns resultados (simples) que provam a utilidade de considerar objetos abstratos. Supõe-se que o leitor está minimamente familiarizado com os objetos da lista anterior, uma vez que uma das maneiras mais fáceis de introduzir a noção de grupo é ir comparando a teoria abstrata com objetos concretos e comuns. Começamos por apresentar a definição formal...

(english version below ) O problema deste post foi-me colocado na primeira edição das Jornadas de Matemática da Faculdade de Ciências da Universidade do Porto, numa sessão de jogos matemáticos ! O problema é particularmente engraçado porque assenta num jogo que se pode jogar entre duas pessoas. Problema: suponha-se que sobre uma mesa estão dois montes de feijões, um com 19 feijões e outro com 20 feijões. A Ana e o João vão jogar um jogo com esses montes de feijões: cada jogada consiste em retirar $2N$ feijões de um monte e pôr  $N $ feijões no outro monte. Assim, na primeira jogada podemos, por exemplo, tirar 10 feijões do monte com 19, deixando-o com 9, e pôr 5 feijões no monte com 20, deixando-o com 25. A Ana vai ser a primeira a jogar e perde quem não puder fazer nenhuma jogada válida. Será que algum dos jogadores consegue garantir a sua vitória? Este jogo tem regras muito simples e é bastante engraçado, vale a pena jogá-lo com alguém só para entender realmente como funciona a d...

In this post we will talk about three different, all very common, ways of making proofs: contrapositive , contradiction and construction . Construction: (jump to the contrapositive or to the contradiction ) Proofs by construction are probably the proofs that make more sense or are more intuitive in nature. When you prove something by construction, you explicitly build the thing that you described to exist, or give an explicit way of verifying what you described. This is very important because more often than not, mathematics can prove things like "an object X satisfying this and that property exists" , but without providing means to find such object. A good example of a proof by construction is the proof that every function $f: \mathbb{R}\to\mathbb{R}$ can be decomposed into a sum $f(x) = O(x) + E(x)$ where $O(x)$ is an odd function and $E(x)$ is an even function, i.e. $$\begin{cases}O(-x) = -O(x)\\ E(-x) = E(x)\end{cases}\ \forall x \in \mathbb{R}$$ To prove this statemen...

Today's problem has gotten me thinking about it several times for several reasons. In particular, the first time I came across it I was pretty sure I knew the answer but didn't really know how to formalize a proof. It was only a couple of years later, when I remembered the problem for no reason at all, that I was able to answer it completely. Problem statement: imagine you have an infinite table with a checkerboard pattern. In the bottom leftmost corner you put a $0$. For every other cell, you insert the smallest non-negative integer that hasn't been used neither in the same row, to the left of the cell, nor in the same column, below it. So, for example, the first row will have the numbers $0, 1, 2, 3, \cdots $. What is the number that appears in the $1997$th row, $2018$th column? The key is in understanding that the $1997$th row and the $2018$th column have nothing special. Hint 1 Write down a small board and fill it in following the rule of the problem statement. Look for...

Everyone knows what mazes/labyrinths are! And plenty of us find it amusing to try and solve one! Take the image above as an example... Can you find a path from the top left opening to the bottom right opening? There exists at least one! I wrote a program in Python (making use of pygame and Pillow) to solve any maze given. I did this project several years ago, after learning about Dijkstra's algorithm . I read about the algorithm and decided to implement it, to get a feel for it. I realized that I could apply it to a maze in a picture, if I took each pixel of the image to be a vertex in the graph where I'd apply the method. I wanted to make my program fairly general, in terms of the mazes that could be given, and so I dwelled with a problem: how to tell if two adjacent pixels should be connected in the graph or not. I knew I only wanted to connect pixels that referred to the path, and not to the walls, so my idea was simple: I supposed that a picture of a maze would have mainly ...

This post's project was made by me and a colleague of mine, Inês Marques. We programmed a small puzzle game, based solely on colours and not on images, that we called HueHue (please mind that the idea for how the game works is not ours). The way the game works is pretty straightforward: you start with a bunch of coloured tiles all mixed up, like in the left image above, and then you want to organize them to create a degradee like the one in the right! The only thing you can take for granted is that the four corners are already correctly placed (and you can't move them, just to prevent accidents). The instructions are also quite simple: you use left and right clicks to swap tiles. Whenever you left-click a tile, you are telling the game that you will want to swap that tile. Whenever you right-click a tile, that tile gets swapped with the last tile you left-clicked! Simple, right? When you finish the puzzle and rearrange the degradee, the window caption changes and you can't ...