Wie viele Schlangen können Sie im Spiel "Schlangen und Leitern" geben?

Question

Wie berechnet man die maximal zulässige Anzahl von Schlangen im Spiel von "Schlangen und Leitern" Von mathematischer / algorithmischer Sicht vorausgesetzt, dass es eine NXN-Board gibt?

up: Meine Gedanken sind einfach, aber sie könnten falsch sein: Ich vermute, sobald zwei Felder auf dem Board nicht zweimal involviert werden können, um eine Schlange zu bilden, bedeutet dies, dass in der NXN-Karte NXN / 2 Schlangen sein kann

Answer 1

Wenn wir annehmen, dass ein bestimmtes Quadrat der Kopf oder der Schwanz sein kann (aber nicht jedoch nicht beide) von höchstens eine Schlange, dann eindeutig eine obere Grenze für die Anzahl der Schlangen auf einem $ n \mal n $ board ist $ \ frac {n ^ 2} 2 $ .Für einen $ m \ times n $ Board können wir diese auf $ \ frac {mn} 2 $ verallgemeinern.Und wir können diese Obergrenze erreichen, wenn entweder $ M $ oder $ n $ sogar ist.Was passiert, wenn $ M $ und $ N $ beide seltsam sind?