Tavola rotonda

[axpgn]

Intorno ad un tavolo rotondo, siedono $n$ persone.
Ogni coppia di persone vicine può scambiarsi di posto.

Qual è il minor numero di scambi necessario affinché ogni persona abbia gli stessi vicini ma scambiati di posto?

[utente__medio11]

\( f(\lfloor \frac{n}{2} \rfloor) + f(\lceil \frac{n}{2} \rceil) \)

con \( f(m)=(m-1) \cdot \frac{m}{2} \) se $m$ è pari e \( f(m) = m \cdot \lfloor \frac{m}{2} \rfloor \) se $m$ è dispari.

Si può fare di meglio?

[axpgn]

È una formula complicata ma sembra funzionare.

Dimostrazione?

[utente__medio11]

"axpgn":È una formula complicata ma sembra funzionare.

Forse sono riuscito a compattarla un po':

[size=120]\( \frac{(n-1) \cdot (n-2)}{2} - ( \lfloor \frac{n}{2} \rfloor - 1) \cdot ( \lceil \frac{n}{2} \rceil - 1) \)[/size]

"axpgn":Dimostrazione?

Poi con calma la posto, ma si può fare di meglio?

[Quinzio]

Per ottenere la disposizione desiderata bisogna in pratica specchiare la disposizione delle persone.
Dividiamo la tavola in 4 quadranti.
Quelli del quadrante I avranno convenienza a scambiarsi di posto con quelli del quadrante IV.
Quelli del quadrante II con quelli del quadrante III.
A questo punto il problema equivale a fare un ordinamento usando l'algoritmo "bubble sort", partendo dal caso peggiore, cioe' quando gli elementi sono invertiti rispetto alla posizione finale.
Nel caso peggiore questo algoritmo chiede $1/2 k(k-1)$ scambi.
Quindi l'ordinamento va fatto per ognuno dei 2 "emicicli", e ogni emiciclo ha $n/2$ persone.

In tutto $2 1/2 (n/2)(n/2-1) = (n/2)(n/2-1) \approx n^2/4$ per $n$ grande.

Ache la soluzione di utente medio verte a questo risultato.
Direi che non e' possibile fare di meglio.

[axpgn]

No, non è possibile fare meglio.

Si divide il tavolo a metà in due gruppi equivalenti (o uno in più se dispari), in ogni gruppo quello ad una estremità si scambia con tutti fino all'altra estremità e poi il secondo e così via ...
Se $n=2k$ è pari allora gli scambi sono $k(k-1)$ mentre se $n=2k+1$ dispari allora gli scambi sono $k^2$