OliForum Matematico

In una nazione ci sono $2016$ città. Possiamo stilare $4$ graduatorie $A_1$, $A_2$, $A_3$, $A_4$, ciascuna delle quali ordina totalmente tutte le città di questa nazione. Ciascun turista che arriverà sceglierà una graduatoria $A_i$ e una città $c$ e visiterà tutte le città che, secondo $A_i$, sono migliori di $c$, decidendo eventualmente se andare anche in $c$. Alla fine desideremmo che, comunque vengano prese due città $c$ e $c′$, l’insieme dei turisti che avranno visitato $c$ sia diverso dall’insieme di quelli che avranno visitato $c′$. Qual è il minimo numero $k$ di turisti per cui esistono graduatorie e scelte dei turisti che realizzano tale situazione?