Клетчатая плоскость раскрашена десятью красками так, что соседние (т. е. имеющие общую сторону) клетки покрашены в разные цвета, причём все десять красок использованы. Две краски называются соседними, если ими покрашены какие-то две соседние клетки. Каково минимально возможное число пар соседних красок?

4?
Вроде для 3х красок или не решили, или не доказали невозможности, не помню

(1) надо не число красок искать (их точно 10), а число "соседних" пар красок (см. определение в (0))

9 не?

9?

(9)(4) осталось привести пример и доказать, что меньше нельзя

меньше 9 не может быть, ибо красок десять. и любая ячейка соседствует с другой

Каждая новая краска добавляет к палитре по крайней мере одну пару. Т.е. 9 - это минимум.

И он реализуем, н., так:

12345678909876543210
23456789098765432101
34567890987654321012

сделаем граф, у которого каждая из 10 вершин - множество точек одного цвета. ребрами будут связи - есть пара соседних по цветам клеток- есть ребро, нет-нет ребра.
Минимальность числа 9 вытекает из связности графа. вопрос очевидна ли связность, то есть то, что из любого цвета можно добраться до любого. наверное это легко доказать, под конец дня не думается.
а пример: шахматная раскраска, вместо белых клеток кидаем любые кроме черного цвета

4 на 4

(7) так у вас на рисунке 10 пар
1. 1-2
2. 2-3
3. 3-4
4. 4-5
5. 5-6
6. 6-7
7. 7-8
8. 8-9
9. 9-0
10. 0-1

1  2 3 4
4  5 6 5
7  8 9 10
10 1 2 3

(11) что это?

(12) Я думал, шахматная доска используется как плоскость.

(10) Точно, с хвостиком ошибся, после 1 не 0, а снова 2:
3212
2123
1234

(8) >вопрос очевидна ли связность, то есть то, что из любого цвета можно добраться до любого. наверное это легко доказать
И правда, граф получается связным, т.к. иначе получилось бы, что плоскость покрашена не полностью.
Либо, из цвета А точки (x1, y1) можно добраться до любой точки (x2, y2) по соседним краскам, например, так:
(x1, y1) -> (x2, y1) -> (x2, y2)

Но решение из (7) выглядит попроще :)