Задача М43‍‍

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

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