MetaMath '22 - demo

Posjednimo na početku ambasadore na proizvoljan način. Neka je $H$ broj susjednih parova neprijateljskih ambasadora. Pokažimo da u slučaju $H>0$ možemo napraviti razmještaj nekih ambasadora kojim smanjujemo $H$. Neka su $A$ i $B$ susjedni neprijateljski ambasadori pri čemu $B$ sjedi desno od $A$. Ambasador $A$ ima barem $n$ prijatelja među preostalih $2n-1$ ambasadora. Odaberimo nekih $n$ među njima i promotrimo mjesta koja se nalaze njima zdesna. Na tih $n$ mjesta mora postojati barem $1$ prijatelj ambasadora $B$ budući da on ima maksimalno $n-1$ neprijatelja. Nazovimo tog ambasadora $B'$, a njegovog lijevog susjeda $A'$ - on je ujedno i prijatelja ambasadora $A$. Promotrimo sada luk od ambasadora $B$ u smjeru suprotnom od kazaljke na satu, sve do ambasadora $A'$. Neka se on sastoji od ambasadora $B, C_1, C_2, ..., \, C_m, A'$. Napravimo sada inverziju tog luka, odnosno zamijenimo mjesta ambasadorima $B$ i $A'$ te ambasadorima $C_k$ i $C_{m+1-k}$, za svaki $1 \leq k \leq m$ (ako je $m$ neparan onda ambasador $C_{\frac{m+1}{2}}$ ostaje na svom mjestu). Primjetimo da su ovom transofrmacijom jedini ambasadori kojima se promijenio jedan od susjeda upravo ambasadori $A,B,A',B'$. Zbog odabira ambasadora $A'$ i $B'$, znamo da su $B$ i $B'$ prijatelji, kao i $A$ i $A'$, pa se $H$ sigurno smanjio barem za $1$ jer su $A$ i $B$ bili neprijateljski susjedi (a možda su takvi bili i $A'$ i $B'$ pa se $H$ smanjio za $2$). U svakom slučaju, našli smo transformaciju kojom se $H$ strogo smanjuje za barem $1$, a on je na početku konačan pa će konačnim nizom ovakvih poteza postati $0$: