Quanti serpenti ci possono essere nel gioco "serpenti e scale"?

Question

Come calcolare il numero massimo consentito di serpenti nel gioco di "Snakes and Ladders" Dal punto di vista matematico / algoritmico assumendo che ci sia una scheda NXN?

UPD: I miei pensieri sono semplici, ma potrebbero essere errati: Suppongo che una volta che alcuni campi sulla scheda non possano essere coinvolti due volte formando un serpente, significa che nella scheda NXN può esserci NXN / 2 serpenti

Answer 1

Se assumiamo qualsiasi quadrato può essere la testa o la coda (ma non entrambi) del maggior numero di serpenti allora chiaramente un limite superiore sul numero di serpenti su una classe $ n \Times n $ scheda è $ \ frac {n ^ 2} 2 $ .Per una classe $ m \ volte n $ scheda possiamo generalizzare questo a $ \ frac {mn} 2 $ .E possiamo raggiungere questo limite superiore se sia $ M $ o $ N $ è pari.Cosa succede se $ m $ e $ N $ sono entrambi dispari?