Problem #15 - cover me not


< 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 $I_k$ to be $[q_k - \epsilon2^{-k-1}, q_k + \epsilon2^{-k-1}]$. By defining $I_k$ this way, we get that $$|I_k| = (q_k + \epsilon2^{-k-1}) - (q_k - \epsilon2^{-k-1}) = \frac{\epsilon}{2^k}$$ We now are left with showing that with the intervals defined this way, we have the two desired properties. In fact, we have that $\left(\mathbb{Q}\cap [0,1]\right) \subseteq \left(\cup_k I_k \right)$. If $q$ is some rational number in $[0, 1]$, then because they are countably many and I listed all of them, $q$ is equal to some $q_k$, but then $q = q_k \in I_k \subset \cup_k I_k$. As to whether the sum of the lengths is smaller than or equal to $\epsilon$, we just have to compute the series $$\sum_{k=1}^\infty |I_k| = \sum_{k=1}^\infty \frac{\epsilon}{2^k} = \epsilon \sum_{k=1}^\infty \frac1{2^k} = \epsilon$$ And that was it! Pretty simple proof, but then I feel like the result is absolutely amazing if we consider $\epsilon < 1$. Don't forget that the rationals are dense in $[0, 1]$, which in a not-so-rigorous way, means that there are rationals everywhere in the interval $[0, 1]$... but we can cover them up with smaller intervals that clearly don't cover the whole interval, because the whole interval has size $1$ and the sizes of our intervals only add up to $\epsilon$... and we didn't even take into account that some of the smaller $I_k$ intervals overlap with each other!

In case you are wondering, the video from which I got this problem is this one.

If you liked this problem, consider subscribing to the newsletter of the blog and like it on Facebook.
O problema de hoje foi inspirado por um vídeo espetacular do canal 3blue1brown.

Enunciado: dado um certo $\epsilon > 0$, há alguma maneira de cobrir todos os racionais do intervalo $[0, 1]$ com pequenos intervalos $I_k$, de tal forma que a soma dos comprimentos desses intervalos seja menor ou igual a $\epsilon$? Escrito de outra maneira, para que valores de $\epsilon > 0$ é que existe uma coleção $\{I_k\}$ de intervalos tal que $$\left(\mathbb{Q}\cap [0,1]\right) \subseteq \left(\cup_k I_k \right) \wedge \sum_k |I_k| < \epsilon$$
Solução: a família de intervalos descrita existe sempre, independentemente do valor de $\epsilon > 0$. Começamos por notar que os racionais no intervalo $[0, 1]$ são contáveis, o que quer dizer que os posso listar como $q_1, q_2, q_3, \cdots$. Para quem ainda não resolveu o problema, agora é uma boa altura para pegar no que eu já escrevi e tentar resolvê-lo.

Depois de enumerarmos os racionais que estão dentro de $[0, 1]$, basta definir $I_k$ como $[q_k - \epsilon2^{-k-1}, q_k + \epsilon2^{-k-1}]$. Definindo $I_k$ desta maneira, obtemos $$|I_k| = (q_k + \epsilon2^{-k-1}) - (q_k - \epsilon2^{-k-1}) = \frac{\epsilon}{2^k}$$ Agora só nos falta mostrar que esta família de intervalos tem as duas propriedades pedidas pelo enunciado. De facto, temos que $\left(\mathbb{Q}\cap [0,1]\right) \subseteq \left(\cup_k I_k \right)$. Se $q$ é um número racional em $[0, 1]$, então porque os racionais são contáveis e eu os enumerei, existe algum $q_k$ tal que $q = q_k$. Mas se esse é o caso, então $q = q_k \in I_k \subset \cup_k I_k$. Para vermos o valor da soma de todos os comprimentos dos pequenos intervalos $I_k$, basta ver que $$\sum_{k=1}^\infty |I_k| = \sum_{k=1}^\infty \frac{\epsilon}{2^k} = \epsilon \sum_{k=1}^\infty \frac1{2^k} = \epsilon$$ E ta-dan! A prova é bastante simples, mas o que este resultado nos diz é absolutamente fascinante se pensarmos em $\epsilon < 1$. Não nos podemos esquecer que os racionais são densos em $[0, 1]$, que de uma forma nada rigorosa quer dizer que há racionais em todo o lado no intervalo $[0, 1]$... mas no entanto, conseguimos tapá-los a todos com intervalinhos (intervalos pequenos) de forma a que esses intervalinhos não cubram o intervalo $[0, 1]$ todo! Ou seja, há partes do intervalo que não estão debaixo de nenhum dos intervalinhos! Afinal de contas, os pequenos intervalos têm $\epsilon < 1$ como soma do comprimento, e o intervalo $[0, 1]$ tem comprimento $1$... e ainda nem tivémos em consideração que alguns dos intervalos $I_k$ se sobrepõem!

Para os mais curiosos, este é o vídeo onde fui buscar este problema.

Se gostaram deste problema, considerem subscrever a newsletter do blog e "ponham" um like no Facebook.

  - RGS

Comments

Popular posts from this blog

Markov Decision Processes 02: how the discount factor works

Problem #16 - the hamburger dilemma

Markov Decision Processes 01: the basics