Cho đa giác lồi n đỉnh \({A_0}{A_1}...{A_{n - 1}}\,\,\left( {n \ge 2} \right).\) Mỗi cạnh và đường chéo của đa giác được tô bởi một trong k màu sao cho không có hai đoạn thẳng nào cùng xuất phát từ một đỉnh cùng màu. Tìm giá trị nhỏ nhất của k.

Dễ thấy \({k_{\min }} \ge n - 1\), bởi vì k < n -1 thì hiển nhiên có hai đoạn thẳng xuất phát từ một đỉnh được tô cùng một màu.

TH1. Nếu n là số chẵn thì gọi các màu cần tô là \(0,1,...,n - 2\). Ta tô màu như sau:

\({A_i}{A_j}\) tô màu \(i + j\left( {\bmod (n - 1)} \right)\,\,\,\,\,\left( {0 \le i,j \le n - 2} \right)\) và \({A_i}{A_{n - 1}}\) tô màu 

\(2i\left( {\bmod (n - 1)} \right)\,\,\,\left( {0 \le i \le n - 2} \right)\)

Cách tô màu này thỏa mãn đề bài. Thật vậy

+ Nếu \({A_i}{A_j},{A_i}{A_k}\left( {0 \le i,j,k \le n - 2} \right)\) tô cùng màu thì \(j \equiv k\left( {\bmod (n - 1)} \right).\) Vô lí !

+ Nếu \({A_i}{A_{n - 1}},{A_i}{A_j}\left( {0 \le i,j \le n - 2} \right)\) tô cùng màu thì \(i \equiv j\left( {\bmod (n - 1)} \right).\) Vô lí !

+ Nếu \({A_i}{A_{n - 1}},{A_j}{A_{n - 1}}\left( {0 \le i,j \le n - 2} \right)\) cùng màu thì \(2i \equiv 2j\left( {\bmod (n - 1)} \right) \Leftrightarrow i \equiv j\left( {\bmod (n - 1)} \right).\) Vô lí !

Vậy cách như trên thỏa mãn yêu cầu bài toán.

Như vậy \({k_{\min }} = n - 1\). (1)

TH2:  Nếu n là số lẻ thì giả sử tô với n – 1 màu là \(0,1,...,n - 2\). Khi đó, tất cả các đoạn thẳng có màu \(1,...,n - 2\) xóa hết chỉ còn lại các đoạn thẳng đều có màu 0. Suy ra \(\deg {A_i} = 1\) do đó \(\sum\limits_{i = 0}^{n - 1} {\deg {A_i}}  = n \vdots 2\) (Vì tổng số bậc bằng 2 lần số cạnh). Điều này vô lí. Do đó \(k \ge n.\)

Với k = n ta chỉ tô màu như sau: Gọi n màu cần tô là \(0,1,...,n - 1\) thì \({A_i}{A_j}\) tô màu \(i + j\left( {\bmod n} \right)\). Cách tô này thỏa mãn yêu cầu bài toán . Thật vậy \({A_i}{A_j},{A_i}{A_k}\) tô cùng màu thì \(i \equiv j\left( {\bmod n} \right)\) vô lí.

 Như vậy \({k_{\min }} = n.\)  (2)

Từ (1) và (2) suy ra \({k_{\min }} = 2\left[ {\frac{{n - 1}}{2}} \right] + 1.\)