Veraces y mentirosos

Este problema apareció el 16/6/14 en el envío semanal 15 de Olimpíada Matemática Argentina:

Hay 2000 personas paradas en una fila. Cada una de ellas es un mentiroso, que siempre miente, o un veraz, que siempre dice la verdad. Cada una de las personas dice la misma frase: “Hay más mentirosos a mi izquierda que veraces a mi derecha.” Determinar, si es posible, cuántas personas de cada clase hay en la fila. 

Al igual que el problema de los alumnos y los paseos, este me dejó desconcertado. Lo primero que vino a mi cabeza fue como todos dirigían la mirada hacia mi y exclamaban en tono neutro pero sistemático “Hay más mentirosos a mi izquierda que veraces a mi derecha”, al estilo de los "muertos vivos" que aparecen en el videoclip “Thriller” de Michael Jackson (1982).
Cuando se me pasó el miedo, aparecieron las ideas. 

Si me están mirando, ellos tienen su derecha a mi izquierda y su izquierda a mi derecha. Un diagrama puede aclarar la situación:

En primer lugar, supongamos que una persona miente. En consecuencia, es verdad lo contrario de lo que afirma la frase: los mentirosos a su izquierda son tantos o menos que los veraces a su derecha. Aclarémoslo más. Si la frase dice “los mentirosos a la izquierda son más que los veraces a la derecha”, entonces lo contrario es la negación de esto, es decir, no ocurre que los mentirosos a la izquierda son más que los veraces a la derecha, lo que entonces equivale a decir que los mentirosos a la izquierda son una cantidad igual o menor que los veraces a la derecha.

Resumiendo, si llamamos Mi al número de mentirosos a la izquierda y Vd al número de veraces a la derecha, tenemos:

Si hay 2000 personas, comencemos evaluando a la primera. Si miente, es verdad que Mi menor o igual que Vd. Pero no tiene veraces a la derecha, es decir, Vd = 0, y los Mi no pueden ser menos que 0!!!! Por lo tanto, esta contradicción nos conduce a que la persona 1 dice la verdad.

Esta conclusión nos lleva de inmediato a evaluar a la última persona. Si miente, entonces Mi es menor o igual que Vd. Como Mi = 0, entonces Vd puede ser cualquier número entre 0 y 1999, lo cual es perfectamente posible. ¿Qué pasa si suponemos que dice la verdad? En este caso, entonces Mi > Vd, pero no tiene mentirosos a la izquierda, o sea, Mi = 0 y los Vd no pueden ser menor que 0!!!! Otra vez arribamos a una contradicción. Por lo tanto, la persona 2000 miente. 
Entonces hasta aquí, la cuestión puede representarse así: 

A continuación evaluamos la persona 2. 
(1) Si miente significa que Mi menor o igual que Vd. Como Vd = 1, Mi = 0 o Mi = 1. Descartamos la primera posibilidad porque la última persona es M, en consecuencia, Mi = 1. Pero esto conduce necesariamente a que todos a la izquierda de 2 son V, excepto la persona 2000:

(2) Si 2 dice la verdad, Mi > Vd y como Vd = 1 entonces Mi puede ser cualquier valor entre 2 y 1998:

No hay nada que contradiga ninguna de las dos alternativas para la persona 2. Sin embargo, la posibilidad (1) es difícil que se verifique.

Sigamos indagando dando por sentado (1). Pero, ¿por dónde seguir? Si seguimos con 3, para no contradecir lo anterior debe ser V, lo que conduce a que Mi > 1. Entonces tenemos:

Entonces como mínimo una de las 1996 personas desde 4 hasta 1999 es M, pero esto se contradice con (1) que supone que 2 es M, porque si 2 es M desde la persona 3 hasta la 1999 son V!!!!. O sea que si 2 es M, 3 no puede ser ni M ni V, porque ambas llevan a contradicción!!!! Entonces 2 no es M o es lo mismo decir que 2 es V.
Luego, hasta aquí la cuestión es así:

Adelante, no desesperes.