Guardatemi!

Iniziate a posizionare il sergente alla sinistra estrema della fila. Il numero s di persone alla sua sinistra che lo guardano sarà ovviamente 0, mentre a destra lo guarderanno in d. Abbiamo che d−s≥ 0. Se d=0 siamo a posto; altrimenti il sergente comincia a spostarsi a destra di un posto per volta.
Quando si sposta a destra di una posizione, ci sono tre possibilità: la recluta oltrepassata sta guardando a sinistra (e allora d si riduce di 1 mentre s rimane lo stesso); sta guardando a destra (e allora s cresce di 1 mentre d rimane lo stesso); sta guardando dall'altra parte, e allora i numeri non cambiano. Come vedete, la differenza d−s rimane costante o si riduce di 1 a ogni passo. Ma alla fine dev'essere per forza minore o uguale a 0; quindi da qualche parte deve essere stata zero.

Un'ultima parola

In giochi come questo, la prima idea che viene in mente è vedere se la risposta ha a che fare con la parità: per esempio "sì, si può fare se il numero di reclute è dispari". Sapere che ci sono alcune reclute che hanno fatto dietrofront, e che quindi per quanto riguarda la domanda sono neutrali, ci permette di capire subito che stavolta la parità non c'entra. La seconda idea che può venire in mente è quella di trovare un monovariante... e stavolta ci siamo.