Posts

Verifying tautologies with Haskell

join the mathspp mailing list
PtEn< change language A tautology is a formula that is true regardless of the logical value we attribute to the variables it contains. For example, the propositional formula $P \vee \neg P$ is always true, regardless of $P$ being true or false. But not every tautology is as simple as the one I just showed. For example, showing that $$(P \implies Q) \implies [(Q \implies R) \implies (P \implies R)]$$ is a tautology requires a bit more thought. But thinking is too tiring, so let us write a Haskell program that takes a formula and decides if the formula is a tautology or not! (By the way, said program is available in my GitHub...) First we need to be able to represent a proposition and we will create a data type just for that. We will call our type "Prop", from proposition, from propositional logic. where we provided data constructors for all sorts of propositional formulas. The idea is that now the formula $P \vee \neg P$ is represented as Or…

Problem #17 - shuffle me around

join the mathspp mailing list
PtEn< change language This post contains a problem that haunted me for a couple of years. I had it lingering in my brain for a long time and it felt quite challenging... then I presented it to a friend of mine one night, and the morning after I had a text from him saying he had cracked it! So kudos to him! I only got to the answer after he gave me a hint...

Problem statement: you and a friend are outside a room guarded by a sphinx. The sphinx tells you that inside the room there are 100 drawers, numbered from $1$ to $100$, where each drawer contains one of a hundred balls, also numbered from $1$ to $100$. The balls are randomly shuffled inside the drawers but each drawer contains exactly only one unique ball. You, your friend and the sphinx are to play a game. First of all, your friend is going to the room where he will be able check the contents of each drawer for as long as he wants; he will also be given the opportunity to swap the balls of two draw…

Problem #16 - the hamburger dilemma

Image
PtEn< change language This post's problem is brought to you by my struggles while cooking. I bought 4 raw chicken hamburgers; two of them were plain chicken burgers, the other two were already seasoned, "american-style" (whatever that meant). In practice, I could tell them apart because the american-style burgers were orange and the plain chicken burgers were light-pinkish.

I had never had one of those "american-style" (AS) burgers and I was slightly afraid I wouldn't enjoy them, so I decided I would have half of a regular burger and half of the AS burger for dinner.

I started cooking the burgers, and at some point I couldn't tell them apart by colour, as you can see in the first picture of this post: they all looked the same colour! So I panicked a little bit: how can I be sure that for my dinner I will only have half of a regular burger and half of an AS burger? Of course in my mind I couldn't just take a bite of each, because that is not math…

The formula that plots itself

Image
PtEn< change language By the end of this blog post I hope that you know how to make mathematical drawings and why the number $$N \approx 4.85845063618971342358209596 \times 10^{543}$$ is so special.

Given a function $f(x, y)$, how can you use it to make a drawing? Well, we just imagine the whole plane as a white, clean grid, and then we fill with black the squares at the positions $(x,y)$ such that $f(x,y) > \frac12$. In a way, it is as if the function $f$ is telling us whether to use white or black, i.e. to leave the square empty ($0$) or filled in ($1$).

(more rigorously, we divide the plane in unit squares, and we give each square the coordinates of its lower-left corner)

If we take, for example, $f(x, y) = x + y$, then square $(0,0)$ would be white because $f(0, 0) = 0 < \frac12$ but the squares $(0, 1)$ and $(1, 0)$ would be black because $f(0, 1) = f(1, 0) = 1 > \frac12$.

As another example, take $f$ to be this function: $$f(x, y) = \left\lfloor mod\left(\left\…

Pocket maths: mathy broccoli

Image
PtEn< change language This post is about showing you how mathematics is beautiful and how it occurs naturally in the world that is around us. In two previous posts (here and here) I talked about fractals. Today I am going to do the same thing, except now I will use broccoli as the example, instead of some weird set on the complex numbers!

Here's two pictures of broccoli: which one is bigger? There's only two possible answers:
Exhibit A is biggerExhibit B is smaller right? WRONG! Don't be fooled like Joey! Options 1 and 2 are the same...
Going back to the matter at hand, which one is bigger? The right answer is exhibit A, but I don't really expect you to get that. The actual question is, how much bigger is A, when compared to B?

In fact, B was "removed" from inside A! But they both look like perfectly fine broccoli, right? This is one of the properties of fractals: self-similarity. Fractals usually exhibit this very interesting behaviour: you keep zoomi…

Problem #15 - cover me not

PtEn< change language This problem that I am posting here today was inspired by an awesome video by 3blue1brown.

Problem statement: for a given $\epsilon > 0$, is there a way for you to cover all the rational numbers in the interval $[0, 1]$ with small intervals $I_k$, such that the sum of the lengths of the intervals $I_k$ is less than or equal to $\epsilon$? In other words (with almost no words), for what values of $\epsilon > 0$ is there a collection $\{I_k\}$ of intervals such that $$\left(\mathbb{Q}\cap [0,1]\right) \subseteq \left(\cup_k I_k \right) \wedge \sum_k |I_k| < \epsilon$$
Solution: such a family of intervals always exists, for any value of $\epsilon > 0$. We start by noticing that the rational numbers in the interval $[0, 1]$ are countably many, which means I can order them as $q_1, q_2, q_3, \cdots$. If you haven't solved the problem yet, take the hint I just gave you and try to solve it.

After enumerating the rationals inside $[0, 1]$, we define $…