A figura ilustra um tabuleiro do jogo RESTA UM. Começa-se o jogo com peças em todas as casas, exceto em uma, que está inicialmente vazia (Figura 1). Nesse jogo, todas as peças podem ser movimentadas. No entanto, cada casa comporta, no máximo, uma peça.

Nesse jogo, a única jogada possível consiste em: dadas três casas consecutivas em linha, na horizontal ou na vertical, se uma das casas, que não a central, estiver vazia e as outras duas, ocupadas, uma das peças salta a outra, adjacente, retirando-se do jogo a que foi pulada. Se não for possível realizar a jogada, o jogo acaba.

Na Figura 2, vê-se a casa A vazia e as casas B e C ocupadas. A peça que está em C pula a que está em B e passa a ocupar a casa A. A peça da casa B, que foi pulada, é retirada do jogo (Figura 3).

Abaixo, está representada uma situação de jogo no Resta Um.

Na situação apresentada, o jogo acaba com, no mínimo, um número de peças igual a

No rio Heródoto, há duas ilhas: Alfa e Beta. A ilha Alfa é ligada à margem direita pela ponte 1 e à margem esquerda pela ponte 2. A ilha Beta é ligada à margem direita pelas pontes 3 e 4, mas não é ligada à margem esquerda. Há ainda a ponte 5, que liga uma ilha à outra.

Percursos diferentes passando pelas pontes são caracterizados por seqüências diferentes formadas com os números do conjunto {1,2,3,4,5}. Por exemplo, (1,2) é um percurso que começa na margem direita, passa pela ponte 1, atravessa a ilha Alfa e, passando pela ponte 2, termina na margem esquerda. Note ainda que (1,5,3), (1,5,4) e (3,5,1) são diferentes percursos que saem da margem direita e chegam a essa mesma margem, passando pelas duas ilhas. Quantos percursos diferentes podem ser feitos, que começam em uma margem e terminam na outra, visitando necessariamente as duas ilhas sem que se passe por uma mesma ponte duas vezes?