Perché la mucca ha attraversato la strada (Platino)

Il fattore John alleva $n$ razze di mucche, e ogni suo campo è destinato al pascolo di mucche di una sola razza specifica. Per esempio, un campo destinato alla razza $12$ può essere utilizzato solo da mucche della razza $12$, ma non da mucche di qualsiasi altra razza.

Attraverso la fattoria del Fattore John passa una lunga strada. Su un lato della strada si trova una sequenza di $n$ campi — uno per ogni razza, e sull'altro lato si trova un'altra sequenza di $n$ campi, anch'essa con uno per ogni razza. Quando una mucca attraversa la strada, si sposta tra i due campi destinati alla sua razza.

Se il Fattore John avesse pianificato tutto attentamente in anticipo, avrebbe disposto i campi nello stesso ordine su entrambi i lati della strada, in modo che i due campi per ogni razza si trovassero esattamente uno di fronte all'altro. In questo caso, le mucche potrebbero attraversare la strada senza incrociarsi con mucche di altre razze. Sfortunatamente, l'ordine dei campi sui due lati della strada può differire, quindi alcune coppie di razze potrebbero avere percorsi che si incrociano. Una coppia di razze distinte $(a,b)$ è chiamata «coppia incrociata» se qualsiasi possibile percorso attraverso la strada per la razza $a$ incrocia necessariamente qualsiasi possibile percorso attraverso la strada per la razza $b$.

Il Fattore John vuole minimizzare il numero di coppie di razze incrociate. Per motivi organizzativi, può riordinare i campi su un lato della strada tramite uno «spostamento ciclico». Ovvero, per qualche 0 \le k < n, ogni campo viene spostato in avanti di $k$ posizioni, mentre i campi che si trovavano nelle ultime $k$ posizioni vengono spostati nelle prime $k$ posizioni.

Per esempio, se i campi su un lato della strada sono inizialmente disposti per razza nell'ordine 3, 7, 1, 2, 5, 4, 6 e si esegue uno spostamento ciclico con k = 2, il nuovo ordine sarà 4, 6, 3, 7, 1, 2, 5.

Determinare il numero minimo possibile di coppie di razze incrociate dopo aver eseguito uno spostamento ciclico opportuno dei campi su uno dei due lati della strada.