Bài 2

Cho

n

và

k

là các số nguyên dương nguyên tố cùng nhau với

k < n

. Tập

M = \{1, 2, \ldots, n-1\}

được tô bởi hai màu, mỗi số một màu xanh hoặc trắng, sao cho: (i) với mỗi

i \in M

, hai số

i

và

n-i

cùng màu; và (ii) với mỗi

i \in M

mà

i \ne k

, hai số

i

và

|i-k|

cùng màu. Chứng minh rằng mọi số trong

M

đều cùng một màu.

Bước 2 trên 5: Hai cách hai thặng dư liên tiếp có thể khác nhau

Bước trước Bước tiếp

Hiểu nôm na

Đi từ điểm được đánh số này sang điểm kế tiếp trên vòng tròn thặng dư, mỗi bước là một bước nhảy độ dài $k$ — trừ khi vượt qua đỉnh vòng tròn (giá trị $n$ ), lúc đó điểm đến thấp hơn tổng thông thường đúng $n$ đơn vị.

r_{i+1} = r_i + k \quad\text{or}\quad r_{i+1} = r_i + k - n

Phân tích chi tiết

Theo định nghĩa, $r_{i+1}-r_i \equiv k \pmod n$ , và vì $r_i,r_{i+1}\in\{1,\dots,n-1\}$ , hiệu thực sự (không theo modulo) chỉ có thể đúng bằng $k$ , hoặc bằng $k-n$ (khi cộng $k$ vượt quá $n$ và phải "quấn vòng").