Combien de serpents il peut y avoir dans le jeu "Snakes and Ladders"?

Question

Comment calculer le nombre maximum de serpents autorisés dans le jeu de "Snakes and Ladders" Du point de vue mathématique / algorithmique en supposant qu'il existe une carte NXN?

updément: mes pensées sont simples, mais elles pourraient être incorrectes: Je suppose qu'une fois deux champs de la planche ne pouvant être impliqués deux fois former un serpent, cela signifie que dans le tableau NXN, il peut y avoir des serpents NXN / 2

Answer 1

Si nous supposons que tout cas carré peut être la tête ou la queue (mais pas à la fois) d'au plus un serpent, alors clairement une limite supérieure du nombre de serpents sur un $ n \TIMES N $ Le tableau est $ \ frac {n ^ 2} 2 $ .Pour un $ M \ TIMES N $ Conseil Nous pouvons généraliser ceci à $ \ frac {mn} 2 $ .Et nous pouvons atteindre cette limite supérieure si $ M $ ou $ n $ est même.Que se passe-t-il si $ m $ et $ n $ est bizarre?