dimkadimon, попробуйте подумать в таком направлении:
1) Предположим, что у нас есть идеальное решение для

(в котором нет монохроматических треугольников). Это возможно только при

, но это не важно.
2) Что нам надо сделать, чтобы получить из него идеальное решение для

? (Это элементарно!)
3)Далее подумайте как из какого-нибудь текущего наилучшего решения для

(с минимально возможным числом треугольников, но уже не нулевым) сделать минимально возможное число ошибок для

...
Эти рассуждения должны натолкнуть вас на ключ к решению.
Удачи!