Раскраска квадрата в наибольшее возможное число цветов

[Ktina]

В какое наибольшее число цветов можно раскрасить клетки квадрата $3\times 3$ так, чтобы для любой пары цветов нашлись две соседние по стороне клетки, окрашенные в эти цвета?

У меня чисто семантическая загвоздка. Что именно следует понимать под парой цветов?
Обязательно ли цвета в паре должны быть различными? Ведь от этого зависит ответ на задачу.

Если подразумеваются только пары различных цветов, то ответ, я полагаю, будет 5. Ведь при 6 и более цветах уже найдутся 15 пар различных цветов, а у нас только 12 «доминошек». Вот пример для пяти цветов:
425
513
342

Если же речь идёт о любых парах цветов, не обязательно различных, то ответ, я полагаю, будет 4. Ведь при 5 и более цветах уже найдутся 15 пар различных цветов, а у нас только 12 «доминошек». Вот пример для четырёх цветов:
212
412
433

Пожалуйста, помогите решить.
Заранее спасибо!

(Оффтоп)

И как такие квадраты сделать в латексе, чтобы красиво было?

[vpb]

Вы, собственно, уже решили задачу. А что авторы подразумевали, "любой пары различных цветов" или "любой пары цветов, не обязательно различных", сказать точно нельзя. Наверняка все-таки первое. С наступающим!

[Ktina]

vpb

(Оффтоп)

И Вас так же! А заодно и всех форумчан!