Mathspp: mathematics and programming

Pt En In this post we prove what the minimum number of moves to solve the problem of the Tower of Hanoi is! Claim: let $T(n)$ denote the number of moves it takes to solve the Tower of Hanoi with $n$ disks; then $T(n) = 2^{n}-1$. Twitter proof: note that to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move the top $n-1$ disks to the top of the bigger disk. Each time we move the top $n-1$ disks to another pole we must take, at least, $T(n-1)$ moves (by definition of $T$) hence we clearly have $T(n) = 2T(n-1) + 1$. Just notice that $B(n) = 2^n - 1$ satisfies the recurrence relation and that $T(0) = B(0) = 0$. If you are having trouble understanding what I mean by to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move t...

Pt En Num post anterior mostrei como podemos aproximar a raíz quadrada de um número através de um processo iterativo que começa com um palpite, seguido de vários ajustes. Neste post vou mostrar qual é o algoritmo mencionado pela Mathgurl no vídeo que ela fez em "parceria" comigo. O método que vou descrever pode ser usado com qualquer número real, seja quadrado perfeito ou não, seja inteiro ou não, racional ou não. Vou começar por apresentar um raciocínio que mostra como o algoritmo surge. Para quem não estiver interessado, pode saltar diretamente para a explicação final de como funciona . Para a exposição que se segue, se $a,b$ forem dígitos, então a notação $ab$ representa o número $10a + b$ em vez do número $a\times b$. Começamos por notar que, se quisermos descobrir $\sqrt{N}$ à mão e $\sqrt{N}$ for irracional, então vamos ter de nos contentar com uma aproximação com um número finito de casas decimais. Por outro lado, se $\sqrt{N} = a_0a_1\cdots a_n.b_0\c...

Pt En Muita gente sabe o que é um sudoku: um puzzle com números que se joga numa tabela com $9$ linhas e $9$ colunas. O objetivo é simples: preencher a tabela com os números entre $1$ e $9$, seguindo umas quantas regras. As regras que devem ser seguidas não são complicadas, mas quem já experimentou resolver sudokus sabe que às vezes pode ser bastante difícil completar o puzzle! Para além de resolver problemas, os matemáticos também gostam muito de generalizar . Suponhamos que temos uma série de características e que olhamos para todos os objetos que satisfazem essas restrições; uma generalização desses objetos pode ser dada ao ignorarmos uma das características consideradas. A título de exemplo, suponha-se que estamos à procura de todos os polígonos que satisfazem as seguintes restrições: Tem quatro lados; Todos os lados são iguais; Todos os lados fazem ângulos de $90^\circ$ entre si. É fácil de ver que o quadrado é o único polígono que satisfaz estas duas retr...