Re: [obm-l] Cavalos de xadrez

[Helder Suzuki <heldersuzuki@xxxxxxxxxxxx>]

 --- Fábio Dias Moreira
<fabio.dias.moreira@terra.com.br> escreveu: >
-----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> On Sunday 27 April 2003 09:45, Helder Suzuki wrote:
> > Olá!
> >
> > (1) Quantos cavalos de xadrez podemos colocar em
> um
> > tabuleiro NxM tal que nenhum seja ameaçado por
> outro?
> > [...]
> 
> Pinte o tablueiro de preto e branco e coloque um
> cavalo em uma casa branca. 
> Qual a cor das casas que ele ameaça?
> 
> Isso acha uma cota inferior para o resultado. Por
> outro lado, em uma 
> configuração maximal, quadrados vazios são atacados
> pelo maior número 
> possível de cavalos (isso é óbvio?). Logo, como a
> configuração gerada pela 
> idéia acima atende a isso, também é cota superior.
> 
> []s,

Ai teriamos sempre N*M/2 cavalos, certo?

E em um tabuleiro 2x3 como ficaria?
Se eu fizer pintando de preto e branco e colocando
cavalos nas casas brancas, por exemplo, eu colocaria
apenas 3 cavalos, mas na verdade cabem 4.

Já em um tabuleiro 1xM, cabem M cavalos!
talvez exista um grupo de casos especiais, vou pensar
aqui

[]'s,
Helder Toshiro Suzuki

_______________________________________________________________________
Yahoo! Mail
O melhor e-mail gratuito da internet: 6MB de espaço, antivírus, acesso POP3, filtro contra spam. 
http://br.mail.yahoo.com/
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================