Un país llamado Máxico tiene dos islas, la isla Mayor y la isla Menor. La isla Mayor está compuesta por $k>3$ estados con exactamente $n>3$ ciudades cada uno, de manera que tiene $kn$ ciudades en total. La isla Menor tiene sólo un estado que tiene 31 ciudades en total. Dos aerolíneas de alto renombre, Aeropapantla y Aerocenzontle, ofrecen vuelos alrededor de Máxico. Aeropapantla ofrece vuelos directos desde cualquier ciudad hasta cualquier otra ciudad de Máxico. Aerocenzontle solo ofrece vuelos directos desde cualquier ciudad de la isla Mayor a cualquier otra ciudad de la isla Mayor.
Cada aerolínea calcula qué porcentaje de sus vuelos directos conectan dos ciudades que se encuentran dentro del mismo estado. Así, se calcularon dos porcentajes en total, uno por cada aerolínea. Si sabemos que ambas aerolíneas obtuvieron el mismo porcentaje, ¿cuál es el menor número de ciudades que puede haber en la isla Mayor?