Для доказательства, что часто бывает на олимпиадах, достаточно сделать один неожиданный шаг: раскрасить треугольнички в шахматном порядке, как это сделано на рисунке. Остальное совсем просто. Во всем треугольнике красных треугольничков на n больше, чем желтых (в каждом горизонтальном ряду красных на один больше), а в цепочке цвета должны чередоваться, поэтому красных может быть только на один больше, чем желтых.

Одна из цепочек максимально возможной длины показана на рисунке. (Из сказанного выше ясно, что для того, чтобы цепочка имела длину n²-n+1, необходимо и достаточно, чтобы она начиналась и кончалась в красных треугольничках и проходила через все без исключения желтые.)

<style type="text/css"> div.p { margin-top: 7pt;}</style><style type="text/css"></style><title>Ответ</title>n²-n+1.