Problem #07 - binary multiples

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 quando dividimos por $4$ e portanto procurávamos $111 - 11 = 100 = 4 \times 25$.

Comentem o que acham disto!

This post's problem has a really simple statement and provides a really interesting piece of trivia about the integers!

Problem: Show that any integer has a multiple that can be written using only $0$s and $1$s.

Solution: Let us define $c(1) = 1$ and $c(n+1) = 10^{n} + c(n), n > 0$, meaning $c(k)$ is the number that is written with $k$ digits $1$ in a row. Pick an integer $n$ and consider the list $c(1), c(2), \cdots, c(|n|-1), c(|n|)$. If one of the numbers is a multiple of $n$, we are done. If none was, by the pigeonhole principle there are $i > j$ with $c(i) \equiv c(j) \mod{|n|}$. Having found those values, we notice that $c(i) - c(j) \equiv 0 \mod{|n|}$ and $c(i) - c(j)$ is written only with $0$s and $1$s.
For example, for $n = 4$ we consider $1, 11, 111, 1111$. It is easy to see that none of those is a multiple of $4$ and so we need to make use of the second part of the solution. We notice that $11$ and $111$ have a remainder of $3$ when divided by $4$ and thus we were looking for $111 - 11 = 100 = 4 \times 25$.

Let me know what you think!

- RGS