(4,0 điểm) Bạn Hải tô màu $n$ số nguyên dương đầu tiên bởi đúng $k$ màu, mỗi số chỉ tô đúng một màu $(k\le n)$. Tìm giá trị nhỏ nhất của $n$ sao cho với mọi cách tô luôn tồn tại hai số được tô cùng màu mà hiệu của chúng là số chính phương trong mỗi trường hợp sau:

a) $k=2$.

b) $k=3$.

a) Với $n=4$, ta phân hoạch tập $\{1;2;3;4\}$ thành hai nhóm, mỗi nhóm gồm các số được tô cùng màu.

Xét phân hoạch $\{1;3\},\{2;4\}$, ta nhận thấy phân hoạch này không có hai số nào được tô cùng màu mà hiệu giữa số lớn và số nhỏ là số chính phương.

Vậy $n\ge 5$. Với $n=5$, ta chứng minh mọi cách tô màu đều thỏa mãn bài toán.

Thật vậy, giả sử tồn tại cách tô màu không thỏa mãn bài toán với $n=5$. Khi đó, hai số tự nhiên liên tiếp không được tô cùng màu. Do đó, các số $1,3,5$ được tô cùng màu. Tuy nhiên $5-1=4$ là số chính phương nên điều này vô lý.

Vậy giá trị nhỏ nhất của $n$ là 5 với $k=2$.

b) Nhận xét: với số tự nhiên $r$ bất kì, bộ số $(r,r+9,r+25)$ và $(r,r+16,r+25)$ có ba số được tô bởi ba màu khác nhau. Do đó, với $r=1,2,3,4$. Các bộ $(10,17);(11,18);(12,19);(13,20)$ có hai số được tô cùng màu.

Theo nguyên lý Dirichlet, trong 4 bộ vừa liệt kê, tồn tại hai bộ có 4 số được tô cùng màu. Tuy nhiên, bằng cách kiểm tra lại từng cặp bộ số, ta nhận thấy rằng luôn tồn tại hai số được tô cùng màu và hiệu giữa số lớn và số nhỏ là số chính phương.

Khi đó, giá trị $n$ nhỏ nhất thỏa mãn 4 bộ số trên xuất hiện và có hai bộ gồm 4 số tô cùng màu là $4+25=29$. Vậy với $n=29$, luôn tìm được hai số cùng màu và hiệu giữa số lớn và số nhỏ là số chính phương.

Với $n=28$, ta xét phân hoạch sau:

- $1,4,6,9,12,14,19,24,27$.
- $2,5,7,10,15,17,20,22,25,28$.
- $3,8,11,13,16,18,21,23,26$.

Với mỗi số trong cùng một nhóm, ta tô cùng một màu và mỗi nhóm khác nhau được tô bởi mỗi màu khác nhau. Cách tô này thỏa mãn không có hai số được tô cùng màu có hiệu là một số chính phương. Vậy giá trị nhỏ nhất của $n$ là 29 với $k=3$.