1 reply to this topic

[namcpnh]

Tìm số nguyên dương $k$ nhỏ nhất sao cho tồn tại cách tô $k$ màu vào tập số nguyên dương và tồn tại một hàm số $f:\mathbb{Z}^+\rightarrow\mathbb{Z}^+$ thỏa mãn 2 điều kiện sau:

(i) Với mọi số $m$, $n$ được tô cùng màu thì $f(m+n)=f(m)+f(n)$

(ii) Tồn tại vài số $m$, $n$ sao cho $f(m+n)\neq f(m)+f(n)$

Lưu ý: mỗi số nguyên dương được tô đúng 1 trong $k$ màu, hai số $m$, $n$ ở 2 điều kiện không nhất thiết phải trùng nhau.

[namcpnh]

Dễ thấy nếu $k=3$ thì ta xét hàm số :

$f(n)=\frac{n}{3}, khi\;n\equiv 0$(mod3) và

$f(n)=r, khi\; n\equiv r(mod3)$

Ta chứng minh $k$ không thể bằng 2. Giả sử $k=2$:

Đặt $f(1)=c$, khi đó ta chứng minh mệnh đề sau: $f(n)=nc\,\forall 1\leq n\leq m\,(1)$

Với $m=2$ thì (1) đúng, giả sử (1) đúng với $m=k$, ta chứng minh $f(k+1)=(k+1)c$, thật vậy:

Nếu $k$ lẻ, khi đó $f(k+1)=2f(\frac{k+1}{2})=2.\frac{k+1}{2}c=(k+1)c$

Nếu $k$ chẵn, giả sử $f(k+1)\neq (k+1)c=f(x)+f(y)\, \forall x,y$ sao cho $x+y=k+1$, khi đó $k+1$ sẽ là số nhỏ nhất thỏa mãn điều kiện trên và $x,y$ được tô khác màu.

Do $k$ chẵn nên Cmtt, ta được $f(k+2)=(k+2)c$, khi đó 1 và $k+1$ không được tô cùng màu. Giả sử 1 tô màu xanh còn $k+1$ tô màu đỏ, khi đó ta cũng có $k$ màu đỏ. Ta có $f(2k)=2f(k)=2kc$ và $f(2k+1)=f(k+1)+f(k)\neq (2k+1)c=f(2k)+f(1)$ nên $2k$ cũng có màu đỏ.

Lại có $f(2k+2)=2f(2k+1)\neq f(2k)+f(2)$ nên $2k$ và $2$ được tô khác màu hay 2 tô màu đỏ$\Rightarrow$ $k-1$ tô màu xanh.

Khi đó ta có:$f(2k+1)=f(k-1)+f(k+2)=(k-1)c+(k+2)c=(2k+1)c$, vô lý.

Vậy ta có $k_{min}$=3.

Edited by namcpnh, 02-01-2018 - 21:19.