savoy082

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

This post's problem is a follow-up from this earlier post in which I talk a little bit about the problem of the water buckets and describe how I wrote a program to solve it. If you spot any mistakes here (or there) please let me know! Problem statement : Given $n$ buckets of capacities $c_1, \cdots, c_n$, prove that if the target value $t$ is not a multiple of $d = \gcd{(c_1,\cdots,c_n)}$ then the problem is unsolvable. Show that if all quantities in all buckets are multiples of $d$, then after one single move, that still holds. Hint 1 Solution : We will show that, regardless of the sequence of moves, all values in all buckets are - at all times - multiples of $d$. Let $w_i$ denote the value of bucket $i$. It is easy to see that in the beginning we have that each bucket has $w_k = 0 = \sum_{i=1}^n 0\cdot c_i$ and thus our property holds for the initial configuration. Now consider that for each bucket $k, w_k = \sum_{i=1}^n a_{k,i}c_i$ (i.e., all values are multiples of $d$). Reme...

[ Link to code, you can try it in the end of the post] Suppose you have an infinite source of water and two buckets of capacities $5$L and $3$L. Through juggling around the water in the buckets, can you find a way to have one of the buckets hold exactly $1$L of water? A possible way of doing it would be: Fill the bucket of $3$L and then pour its water into the $5$L one; Fill the bucket of $3$L. At this point you have $3$L in each bucket; Pour the bucket of $3$L into the $5$L one. Since the bigger one already had $3$L in it, only $2$ will fit, meaning there will be a remaining litre in the $3$L bucket. I find this problem a very interesting one, and it is not hard to generalize it: given $N$ buckets of capacities $c_1, c_2, \cdots, c_N$, as well as a target value $T$ and an infinite source of water, is there a sequence of moves that puts exactly $T$ litres in one of the buckets? There are some cases for which one can immediately say that there is no such sequence. On one hand, if $T ...

[Code/código: regexPrinter ] A regular expression , without much rigor, is a very compact way of representing several different strings. One common use of regular expressions is to look for strings that have a certain structure in a bigger string (say a text). As an example, the regular expression abc(d|e) can be used to look for the strings "abcd" and "abce", where the character | denotes we have to make a choice. Thus cat|dog would match the strings "cat" and "dog". There are other special symbols that have meanings and purposes. One very interesting question that arises is: given a regular expression, what are the strings matched by it? To answer that question I wrote a small Python program, that I called regexPrinter , that prints all strings matched by a given regular expression! In order to manage that task, I chose a subset of the regex syntax that I wanted to be able to print and also decided that whenever a piece of a pattern was inf...