"뱀과 사다리"게임에 몇 개의 뱀이있을 수 있습니까?

Question

뱀과 사다리 "의 최대 허용 뱀 수를 계산하는 방법 NXN 보드가 있다고 가정하는 수학적 / 알고리즘 시점에서?

UPD : 내 생각은 간단하지만 부정확 할 수도 있습니다. 나는 이사회의 두 필드가 뱀을 형성하는 두 개의 필드가 두 번 관련 될 수 없다고 생각합니다. 이는 NXN 보드에서 NXN / 2 뱀이있을 수 있음을 의미합니다.

Answer 1

주어진 사각형이 가장 많은 뱀의 머리 또는 꼬리 (그러나 둘 다)가 될 수 있다고 가정하면 $ n \시간 n $ 보드는 $ \ frac {n ^ 2} 2 $ 입니다. $ m \ times n $ 보드 우리는 이것을 $ \ frac {mn} 2 $ 에 일반화 할 수 있습니다...에 $ M $ 또는 $ n $ 이라면이 상한에 도달 할 수 있습니다. $ m $ 및 $ n $ 은 모두 이상