Spioni

Iniziamo col definire "neutrali" due agenti A e B tali che A non spia B e B non spia A. Se chiamiamo gli agenti A1, A2, ..., A16 possiamo definire i seguenti numeri per ogni agente Ai:
ai è il numero di agenti che spiano Ai;
bi è il numero di agenti che Ai spia;
ci è il numero di agenti neutrali rispetto ad Ai.
È immediato che per ogni i abbiamo che ai + bi + ci = 15, perché abbiamo considerato tutti i possibili agenti. Un po' meno immediato è notare che ai + ci ≤ 8 e bi + ci ≤ 8, sempre per ogni i. Se non fosse così, infatti, potremmo prendere i nove elementi e Ai, e sarebbe impossibile formare la catena. Combinando queste relazioni otteniamo che ci ≤ 1; pertanto ciascun agente ha al più un collega neutrale. Inoltre, poiché l'essere neutrali è una proprietà riflessiva (se A è neutrale rispetto B allora B è neutrale rispetto ad A), eventuali spie neutrali possono essere accoppiate sapendo che nessuna di esse può avere altre spie neutrali.
Immaginiamo ora che esista un gruppo di 11 spie per cui non si possa creare una catena. Poiché 11 è dispari, ci deve essere necessariamente almeno un agente S che non è neutrale rispetto a nessuno degli altri dieci. Togliamo momentaneamente S, e formiamo la catena con i rimanenti agenti C1, C2, C3, ..., C10 dove ciascuno spia l'agente col numero seguente e C10 spia C1. Per le disuguaglianze iniziali sappiamo che S deve spiare almeno uno dei Ci ed essere spiato da almeno un altro Ci. Se facciamo il giro dei Ci arriveremo dunque a un punto in cui l'agente precedente spia S e quello seguente è spiato da S; basta pertanto inserire S tra questi due agenti e ottenere la catena richiesta.

Un'ultima parola

Non è un problema così semplice, però è istruttivo vedere come da semplici disuguaglianze si ottengano grandi risultati.


 
[continua]     [indice]