¿Cuántas serpientes puede haber en el juego "Serpientes y escaleras"?

Question

Cómo calcular el número máximo permitido de serpientes en el juego de "Serpientes y escaleras" Del punto de vista matemático / algorítmico asumiendo que hay un tablero de NXN?

UPP: Mis pensamientos son simples, pero pueden ser incorrectos: Supongo que una vez que dos campos en la placa no puedan participar dos veces, formando una serpiente, significa que en la placa NXN puede haber nxn / 2 serpientes

Answer 1

Si asumimos que cualquier cuadrado dado puede ser la cabeza o la cola (pero no ambos) de la mayoría de una serpiente, entonces claramente un límite superior en el número de serpientes en un $ n \veces n $ la placa es $ \ frac {n ^ 2} 2 $ .Para un $ m \ veces n $ board podemos generalizar esto a $ \ frac {mn} 2 $ .Y podemos alcanzar este límite superior si $ m $ o $ n $ es incluso.¿Qué sucede si $ m $ y $ n $ son extraños?