A Torre de Hanói é uma interessante atividade lúdica que consiste em uma placa de madeira na qual são dispostos três pinos de mesmo comprimento e um conjunto de discos concêntricos conforme ilustra a figura abaixo:

O desafio é transferir a “Torre” de um “pino” para outro obedecendo apenas duas regras:

I. Só se pode transferir um disco de cada vez.

II. Durante o processo de transferência, nunca um disco maior pode ficar sobre um disco menor.

http://www.google.com/search?num=10&hl=en&site=imghp&tbm=isch& source=hp&q=a+torre+de+hanoi&oq=a+torre+de+hanoi&gs_l=img.3... 1042.6128.0.7188.16.10.0.5.5.0.745.1627.3j1j2j6- 1.7.0...0.0.DT3lMCOD7jM&biw=1280&bih=683&sei=JLj8T6T1E6Pv0gGPv 4mFBw. Acesso em 10/07/2012.

. Obedecendo as regras é possível estabelecer uma função que associa o número de discos “d” utilizados na Torre e o número mínimo de movimentos “m” que se pode efetuar para transferi-la de um pino para outro. Essa função é dada pela expressão m(d) = !$ 2^d !$ – 1 que pode ser definida, por exemplo, como uma aplicação de {1, 2, 3, 4...} em {1, 3, 7, 15...}. Em outros termos, com 1 disco tem-se 1 movimento, com 2 discos tem-se 3 movimentos, com 3 discos tem-se 7 movimentos e assim por diante. Nestas condições, todos os elementos do domínio de m(d) podem ser expressos por: