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 A₁, A₂, ..., A₁₆ possiamo definire i seguenti numeri per ogni agente A_i:
a_i è il numero di agenti che spiano A_i;
b_i è il numero di agenti che A_i spia;
c_i è il numero di agenti neutrali rispetto ad A_i.
È immediato che per ogni i abbiamo che a_i + b_i + c_i = 15, perché abbiamo considerato tutti i possibili agenti. Un po' meno immediato è notare che a_i + c_i ≤ 8 e b_i + c_i ≤ 8, sempre per ogni i. Se non fosse così, infatti, potremmo prendere i nove elementi e A_i, e sarebbe impossibile formare la catena. Combinando queste relazioni otteniamo che c_i ≤ 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 C₁, C₂, C₃, ..., C₁₀ dove ciascuno spia l'agente col numero seguente e C₁₀ spia C₁. Per le disuguaglianze iniziali sappiamo che S deve spiare almeno uno dei C_i ed essere spiato da almeno un altro C_i. Se facciamo il giro dei C_i 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.