Vrijeme: 01:12

Invarijante: Neprijateljski ambasadori - RJEŠENJE

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: