Quantas cobras podem estar no jogo "cobras e escadas"?

Question

Como calcular o número máximo permitido de cobras no jogo de "cobras e escadas" Do ponto de vista matemático / algorítmico assumindo que existe uma placa NXN?

Upd: Meus pensamentos são simples, mas podem estar incorretos: Suponho que uma vez que qualquer dois campos no conselho não puder ser envolvido duas vezes formando uma cobra significa que no quadro NXN pode ser NXN / 2 cobras

Answer 1

Se assumirmos que qualquer quadrado dado pode ser a cabeça ou a cauda (mas não ambos) de no máximo uma cobra, então claramente um limite superior no número de cobras em uma $ n \Times n $ Board é $ \ frac {n ^ 2} 2 $ .Para uma $ m \ vezes n $ placa podemos generalizar isso para $ \ frac {mn} 2 $ .E podemos alcançar este limite superior se ou $ m $ ou $ n $ é mesmo.O que acontece se $ m $ e $ n $ ambos são estranhos?