28/10/2023, 15:34
01/11/2023, 21:52
03/11/2023, 22:23
09/11/2023, 16:05
09/11/2023, 18:26
axpgn ha scritto:Testo nascosto, fai click qui per vederloInizialmente gli ambasciatori si siedono a caso e quindi avremo in generale $N$ coppie "nemiche".
09/11/2023, 18:56
10/11/2023, 14:16
axpgn ha scritto:Testo nascosto, fai click qui per vederloEra solo un'introduzione per dire che, in generale, c'è ALMENO una coppia di nemici seduti vicini; se non ce ne fosse nessuna avremmo già finito la dimostrazione, non ti pare?
10/11/2023, 14:18
axpgn ha scritto:Una soluzione più a portata di manoTesto nascosto, fai click qui per vederloInizialmente gli ambasciatori si siedono a caso e quindi avremo in generale $N$ coppie "nemiche".
Se esiste un algoritmo che ad ogni opportuno scambio di posto di due ambasciatori riduce $N$ siamo a cavallo.
L'algoritmo esiste ed è questo:
Sia $(A,B)$ una coppia "nemica" con $B$ alla destra di $A$.
Supponiamo che esista una coppia $(A'B')$ tale che se scambiamo $B$ con $A'$, le nuove coppie $(A,A')$ e $(B,B')$ siano entrambe amiche; se una coppia simile esiste sempre allora possiamo sempre ridurre $N$.
Si può dimostrare che tale coppia esiste sempre.
Dimostrazione:
Partiamo da $A$ e percorriamo il tavolo in senso antiorario.
Incontreremo almeno $n$ amici di $A$.
Alla loro destra ci sono $n$ sedie, le quali NON possono essere occupate tutte da nemici di $B$ in quanto al massimo possono essere $n-1$ quindi ci sarà sicuramente un amico $A'$ di $A$ con alla sua destra un amico $B'$ di $B$.
Cordialmente, Alex
10/11/2023, 15:55
11/11/2023, 17:59
axpgn ha scritto:Certo che regge ...Testo nascosto, fai click qui per vederloforse ti è sfuggito il fatto che in questo modo si riducono le coppie nemiche UNA ALLA VOLTA, l'altra la risolvi DOPO (la coppia "a sinistra" non è altro che un'altra coppia "a destra" )
n = 100
1-25
57-99
33-34
....
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.