Nesse problema usaremos algumas peças do jogo de xadrez.
• O cavalo (C) é uma peça que ataca quadrados que estão a um movimento em L da sua casa atual. Esse movimento percorre dois quadrados numa direção e um quadrado na direção perpendicular. Uma propriedade importante é que o cavalo consegue pular peças, ou seja, ele pode atacar uma casa mesmo que existam peças no caminho. Veja a primeira figura abaixo em que temos um cavalo no canto inferior esquerdo que ataca 2 quadradinhos (•).
• A torre (T) é uma peça que ataca todos os quadradinhos que estão na mesma linha ou na mesma coluna. Diferentemente do cavalo, a torre não pode pular peças. Na segunda figura a seguir, temos uma torre atacando 4 quadradinhos (•).
Ao colocar algumas peças de xadrez num tabuleiro 3 × 3, dizemos que essa configuração é completa quando cada um dos 9 quadradinhos está ocupado por exatamente uma peça ou está sendo atacado por pelo menos uma das peças. Não é permitido colocar mais de uma peça em um mesmo quadradinho.
No primeiro exemplo a seguir, temos uma configuração completa com 3 torres. No segundo, uma configuração que não é completa usando 3 torres.
a) Qual é o número mínimo de cavalos necessários para fazer uma configuração completa em um tabuleiro 3 × 3 apenas com cavalos? Lembre-se de mostrar um exemplo com esse número mínimo de cavalos e demonstrar que não existe configuração completa com menos cavalos.
b) Quantas configurações completas diferentes existem em um tabuleiro 3×3 usando apenas uma torre e dois cavalos? Configurações obtidas com rotações ou reflexões devem ser consideradas diferentes. Por exemplo, as quatro configurações a seguir são consideradas todas distintas.