Chủ đề này có 2 trả lời

[L Lawliet]

Bài toán. Tìm số nguyên dương $k$ nhỏ nhất sao cho ta có thể tô màu các số nguyên dương từ $1$ đến $n$ bằng $k$ màu khác nhau để không có hai số nào cùng màu là bội của nhau.

[redfox]

$k=\left\lfloor\log_2n\right\rfloor+1$
Xét $k$ số $1;2;2^2;...;2^{k-1}$. Hiển nhiên ta phải dùng ít nhất $k$ màu.
Giữ nguyên $\left\lfloor\frac{n}{2}\right\rfloor$ số đầu tiên của dãy, tô màu các số còn lại và tiếp tục làm vậy với các số chưa được tô.
Cách tô này dùng đúng $k$ màu. Gọi $m$ và $n$ là hai số cùng tô bởi một màu. Giả sử $m<n$. Từ cách tô dễ thấy $2m>n$. Vậy cách tô trên thỏa mãn.

Bài viết đã được chỉnh sửa nội dung bởi redfox: 18-08-2016 - 15:27

[rfiyms]

Bài toán. Tìm số nguyên dương $k$ nhỏ nhất sao cho ta có thể tô màu các số nguyên dương từ $1$ đến $n$ bằng $k$ màu khác nhau để không có hai số nào cùng màu là bội của nhau.

Để ý rằng $2^{\left \lfloor \log _{2}n \right \rfloor}=\left \lfloor n \right \rfloor\leq n$.

Xét dãy các số $2^{0};2^{1};2^{2};...;2^{\left \lfloor \log _{2}n \right \rfloor}$ thì ta thấy không thể có hai số nào được tô cùng một màu.

Do đó $k\geq \left \lfloor \log _{2}n \right \rfloor+1$.

Bây giờ ta sẽ chứng minh với $k=\left \lfloor \log _{2}n \right \rfloor+1$ thì ta có thể thực hiện được cách tô màu theo yêu cầu bài toán.

Thật vậy với $k=\left \lfloor \log _{2}n \right \rfloor+1$ ta tô màu như sau:

Đặt $A_{i}=\left \{ 2^{i};2^{i}+1;2^{i}+2;...;2^{i+1}-1 \right \} \,\,\,\, \left ( i=\overline{0;\left \lfloor \log _{2}n \right \rfloor-1} \right )$ và $A_{j}=\left \{ 2^{\left \lfloor \log _{2}n \right \rfloor};2^{\left \lfloor \log _{2}n \right \rfloor}+1;2^{\left \lfloor \log _{2}n \right \rfloor}+2;...;n \right \}$.

Tô màu các số thuộc $A_{i}$ bởi màu thứ $i+1$ thì cách tô màu này thỏa mãn yêu cầu bài toán.

Vậy $k_{\min }=\left \lfloor \log _{2}n \right \rfloor+1$.