Câu hỏi 148
Cho $n$ là một số nguyên dương. Kí hiệu $S_n$ là tập các điểm $(x, y)$ có tọa độ nguyên sao cho
$$
|x| + \left|y + \frac{1}{2}\right| \lt n.
$$
Một đường đi là một dãy các điểm phân biệt $(x_1, y_1), (x_2, y_2), \dots, (x_\ell, y_\ell)$ trong $S_n$ sao cho, với $i = 2, \dots, \ell$, khoảng cách giữa $(x_i, y_i)$ và $(x_{i-1}, y_{i-1})$ bằng 1 (nói cách khác, các điểm $(x_i, y_i)$ và $(x_{i-1}, y_{i-1})$ là hai điểm kề nhau trong lưới các điểm có tọa độ nguyên).
Chứng minh rằng các điểm của $S_n$ không thể được chia thành ít hơn $n$ đường đi (một phép chia $S_n$ thành $m$ đường đi là một tập $\mathcal{P}$ gồm $m$ đường đi khác rỗng sao cho mỗi điểm của $S_n$ xuất hiện trong đúng một trong $m$ đường đi của $\mathcal{P}$).
$$
|x| + \left|y + \frac{1}{2}\right| \lt n.
$$
Một đường đi là một dãy các điểm phân biệt $(x_1, y_1), (x_2, y_2), \dots, (x_\ell, y_\ell)$ trong $S_n$ sao cho, với $i = 2, \dots, \ell$, khoảng cách giữa $(x_i, y_i)$ và $(x_{i-1}, y_{i-1})$ bằng 1 (nói cách khác, các điểm $(x_i, y_i)$ và $(x_{i-1}, y_{i-1})$ là hai điểm kề nhau trong lưới các điểm có tọa độ nguyên).
Chứng minh rằng các điểm của $S_n$ không thể được chia thành ít hơn $n$ đường đi (một phép chia $S_n$ thành $m$ đường đi là một tập $\mathcal{P}$ gồm $m$ đường đi khác rỗng sao cho mỗi điểm của $S_n$ xuất hiện trong đúng một trong $m$ đường đi của $\mathcal{P}$).