Ambientazione gentilmente offerta da Cip999

[bern-1-16-4-13]

Abbiamo $4n$ città disposte su una bellissima circonferenza. A ogni città assegniamo un numero, che corrisponde al numero di persone di quella città che vogliono morire. Il caso ha voluto che l'insieme di tutti i numeri assegnati alle città sia proprio $\{1,...,4n\}$.
Tuttavia nessuna persona ha la forza di volontà di uccidersi da sola, nè tanto meno di uccidere un concittadino, per cui il governo elabora il seguente metodo per soddisfare tutte le richieste, e allo stesso tempo creare un evento di grande attrazione turistica mondiale: organizza le $4n$ città in $2n$ coppie disgiunte, dopodiché per ogni città crea un esercito (composto dalle persone di quella città che si vogliono suicidare) e lo manda contro l'esercito della città interna alla stessa coppia (gli eserciti di tutte le città partiranno tutti nello stesso istante alle parole del governatore trasmesse in diretta televisiva mondiale: "Che la fortuna sia con voi!"). Per ragioni statistiche (ma noi lo prenderemo come dato certo) in ogni scontro tra eserciti verrà ucciso lo stesso numero di persone, e la battaglia non terminerà fino a che uno dei due eserciti non sarà stato annientato. Il governo affinchè il suo sistema sia efficiente vuole evitare che da ogni scontro sopravvivano più di $3n-1$ persone (queste persone, che si saranno trovate così vicino alla morte, ritroveranno la gioia di vivere). Vuole inoltre evitare che gli eserciti di due città che non sono nella stessa coppia non rischino di incontrarsi (poichè si rischierebbe che stringano alleanze, o si scontrino), in modo che il tutto vada secondo lo schema fatto.

a) In funzione di $n$ riuscirà sempre (i.e. qualsiasi sia la configurazione dei numeri assegnati alle città) il nel suo intento?
b) Se il governo volesse invece far sopravvivere non più di $3n-2$ persone da ogni scontro, in funzione di $n$ riuscirà sempre (i.e. qualsiasi sia la configurazione dei numeri assegnati alle città) nel suo intento?

[karlosson_sul_tetto]

Possiamo dividere le città in 2 fazioni, guelfi e ghibellini entrambe con $2n$ città, nel seguente modo: parto da una città guelfa e inizio a girare lungo la circonferenza; la successiva è ghibellina, la successiva guelfa e via dicendo. Noto che due città $A,B$ della stessa fazione non possono combattere, perché tra di loro c'è un numero pari di "passaggi di città", quindi un numero dispari di città. Queste non potranno accoppiarsi completamente, perché ne rimarrà una spaiata; non potrà combattere con nessun altra città perché la congiungente attraverserebbe il segmento AB. Chiamo due città vicine se sono collocate consecutivamente lungo la circonferenza.

Prese due città collegate $A,B$ con $a,b$ suicidi, il numero dei sopravvissuti al combattimento è $|a-b|$. Se WLOG la città più numerosa è $A$, affinché la condizione sia soddisfatta serve $a-b\leq 3n-1\rightarrow b\geq a-3n+1$. Visto che $b\geq 1$, se $a\leq 3n$, allora nello scontro tra $A$ e $B$ ci saranno meno di $3n-1$ sopravvissuti. Traendo le somme, chiamo guyanesi le città con un numero di aspiranti suicidi $\geq 3n+1$, bulgare quelle con un numero compreso tra $3n$ e $n+1$, maltesi quelle con una quantità $\leq n$. Una città bulgara può combattere contro qualsiasi altra città senza problemi: se è quella più popolosa per quanto detto sopra ci saranno pochi sopravvissuti, se si scontra con una più popolosa (quindi con una città guyanese) il numero di sopravvissuti è $\leq 4n-(n+1)=3n-1$. Una città maltese può scontrarsi con una maltese o bulgara, cosi come una città guyanese può scontrarsi con un'altra guyanese o bulgara.
Gli unici problemi sono gli scontri tra città guyanesi e maltesi; dimostrerò ora per induzione che è possibile pianificare gli scontri tra le città in modo che non si scontrino mai una città guyanese e maltese; in questo modo, avrò la tesi.

Passo base:


$n=1$, ci sono quattro città di cui una guyanese, una maltese e due bulgare; quindi la città guyanese avrà una vicina bulgara, mi basta collegare loro due e poi l'altra bulgara con la maltese.

Passo induttivo: si hanno $n$ città maltesi, $2n$ bulgare e $n$ guyanesi. Se ho due città guyanesi vicine, le faccio combattere (e la loro congiungente non intersecherà nessun altra linea di combattimento); poi prendo una città maltese vicina ad un'altra maltese o bulgara ($n$ città maltesi non posso avere come vicine solo $n(-2)$ città guyanesi) . A seconda della nazionalità di quest'ultima, posso essere rimasto con:

• $n-2$ guyanesi, $2n-1$ bulgare, $n-1$ maltesi
• $n-2$ guyanesi, $2n$ bulgare, $n-2$ maltesi

Posso togliere per un attimo le 4 città dalla circonferenza; l'ipotesi induttiva ci consente di collegare $4n-4$ città di cui $n-1$ guyanesi, $2n-2$ bulgare e $n-1$ maltesi. In qualunque dei tre casi, l'ipotesi induttiva è più forte (perché ha un numero maggiore di città guyanesi). Posso prendere una città bulgara e metterci la bandiera guyanese (e nel secondo caso far passare un'altra bulgara per maltese). In questo modo si hanno le esatte condizioni dell'ipotesi induttiva e non ho problemi perché le città bulgare possono essere collegate a tutto (paese di spie!).

Ora presuppongo che non ci siano due città guyanesi vicine. Allora non posso avere tutte solo vicine maltesi, quindi ci sarà una città bulgara e una città guyanese vicine, le faccio combattere. Per lo stesso discorso di sopra, ci sarà anche una coppia maltese-maltese o maltese-bulgara; facendo scontrare anche loro, posso avere:

• $n-1$ guyanesi, $2n-2$ bulgare, $n-1$ maltesi
• $n-1$ guyanesi, $2n-1$ bulgare, $n-2$ maltesi

Nel primo caso posso concludere per l'ipotesi induttiva; nel secondo, faccio arrendere una città bulgara ai cavalieri dell'ordine di malta in modo da poter nuovamente applicare l'ipotesi induttiva.



Per fare il punto b), cambio leggermente i confini territoriali dei tre stati: ora per avere la tesi serve che le differenze di abitanti siano $leq 3n-2$. Quindi la guyana si prende la città bulgara con $3n$ abitanti e malta quella con $n+1$; la bulgaria ha ora solo $2n-2$ città.
Parto da una città guyanese ghibellina con $4n$ suicidi e scelgo un verso da seguire; la successiva è una maltese guelfa con $n+1$ suicidi;dopo c'è una guyanese ghibellina con $4n-1$ suicidi e una maltese guelfa con $n$ suicidi e cosi via fino alla conquista guyanese con $3n$ e quella maltese con $1$. Le altre $2n-2$ città sono bulgare in un ordine che non importa. Noto che è impossibile che tutte le città non-bulgare siano collegate a città bulgare, perché le bulgare sono $2n-2$ e le non-bulgare $2n+2$; quindi ci sono due città dell'alleanza guyano-maltese che si combattono (e allora forse non è davvero un'alleanza). Non sono due città della stessa nazione, perché tutte le guyane sono ghibelline e tutte le maltesi sono guelfe, quindi il segmento è tra una città guyanese $A$ con $3n+a$ suicidi e una città maltese $B$ con $1+b$ suicidi. Noto che $a\leq b$ perché il numero di sopravvissuti $3n-1+a-b\geq 3n-1$ cosa inammissibile.Considero il semipiano formato dalla retta $AB$ in cui sono presenti solo città maltesi e guyanesi. Tutti i combattimenti avvengono tra una città guyanese e una maltese (per via degli schieramenti politici). Siccome le guyanesi hanno più soldati, se conto il numero di sopravvissuti è uguale alla differenza tra tutti i solfati guyanesi e tutti quelli maltesi (perché nella somma $|x_1-y_1|+|x_1-y_1|+\ldots +|x_k-y_k|$ tutti gli argomenti dei moduli sono positivi). Raggruppando in un altro modo, ovvero ogni città maltese $1+x$ con la successiva guyanese $3n+x$, la differenza per ciascuna coppia è $3n-1$. Ci sono $b-a$ coppie di città, quindi il numero di sopravvissuti è $(3n-1)(b-a)$. Però avvengono anche $b-a$ scontri e il numero di sopravvissuti in ciascuno scontro è per ipotesi $\leq 3n-2$, quindi il numero totale di sopravvissuti è $\leq (3n-2)(b-a)$. Ma questo contrasta con l'affermazione di prima, assurdo.

[bern-1-16-4-13]

Ok, tutto bene tranne che devi aggiustare il punto b: l'idea è esattamente quella, ma se guardi qualche caso piccolo ti rendi conto cosa non va nel tuo ragionamento, perchè infatti con la tua disposizione è possibile tracciare le corde rispettando le ipotesi (prova ad esempio $n=2$)

[karlosson_sul_tetto]

Apporto la leggera modifica alla soluzione della parte b) (scusa per il ritardo bern <3)

Perché non funzionava la soluzione di prima? Perché la distanza tra due vicine prima era alternato tra $3n-1$ e $3n-2$; quindi il segmento poteva congiungere due vicine distanti $3n-2$ e far funzionare tutto.
Modifico la disposizione spostando le città maltesi in modo che abbiano un abitante in meno: in senso orario una guyanese con $4n$, poi una maltese con $n$, poi una guyanese con $4n-1$ e maltese con $n-1$ fino a guyanese con $3n+1$, maltese con $1$, guyanese con $3n$. In questo blocco la distanza tra due città vicine è o $3n$ o $3n-1$. Inoltre siccome ho preso $2n+1$ città, ci dev'essere una coppia di queste che combatte. Questa coppia è tra una città guyanese e una maltese (ricordo che le maltesi sono guelfe e le guyanesi ghibelline, e due città della stessa fazione non possono combattere perché lascerebbero un numero di città dispari da una parte); e da qua finisco come sopra, la somma delle distanze da una delle due metà è $\leq (3n-2)\cdot$ coppie di città, ma dall'altro canto ogni distanza guyanese-maltese consecutive è $\geq 3n-1$, assurdo.

[bern-1-16-4-13]

ok, ora va bene