Bài 5

Tìm số nguyên dương nhỏ nhất

k

sao cho tồn tại hàm

f:\mathbb Z\to\{1,2,\dots,k\}

thỏa mãn

f(x)\ne f(y)

mỗi khi

|x-y|\in\{5,7,12\}

Bước 3 trên 5: Hoàn tất phép tô bốn màu

Bước trước Bước tiếp

f(x)\ne f(y)\quad\text{whenever }|x-y|\in\{5,7,12\}

Phân tích chi tiết

Ở mỗi bước chọn màu nhỏ nhất còn dùng được. Chặn ở bước trước bảo đảm tập màu còn dùng được không rỗng. Mọi cặp bị cấm đều được xét khi đầu mút đến sau được tô, nên hàm thu được thỏa $f(x)\ne f(y)$ khi $|x-y|\in\{5,7,12\}$ . Do đó $k\le4$ .