“蛇和梯子”游戏中有多少只蛇？

Question

如何计算“蛇和梯子”中的最大速度蛇数的最大蛇数。从数学/算法的角度来看，假设有一个NXN板？

upd：我的想法很简单，但它们可能不正确： 我想考虑电路板上的任何两个字段都不能两次形成蛇，这意味着在NXN板中可以有NXN / 2蛇

Answer 1

如果我们假设任何给定的正方形可以是最多一个蛇的头部或尾部（但不是两个），那么显然是 $ n \上的蛇数的上限时代N $ 板是 $ \ frac {n ^ 2} 2 $ 。对于 $ m \ times n $ 电路板我们可以将其概括为 $ \ frac {mn} 2 $ 。我们可以达到这个上限，如果 $ m $ 或 $ n $ 甚至是偶数。如果 $ m $ 和 $ n $ 都是奇数？