Math Labs

Bài 2

Cho n≥3n\ge3 và tập EE gồm 2n−12n-1 điểm phân biệt trên một đường tròn. Tô đen đúng kk điểm. Gọi cách tô là tốt nếu có một cặp điểm đen mà cung giữa chúng có phần trong chứa đúng nn điểm của EE. Tìm kk nhỏ nhất để mọi cách tô kk điểm đều tốt.
Bước 1 trên 4: Mã hóa điều kiện bằng đồ thị
Bước trướcBước tiếp
m=2n−1,i∼j⟺j−i≡±(n−2)(modm)m=2n-1,\qquad i\sim j\Longleftrightarrow j-i\equiv\pm(n-2)\pmod m
Phân tích chi tiết

Đánh số các điểm theo chu kỳ modulo m=2n−1m=2n-1. Hai điểm có một cung chứa đúng n điểm bên trong khi và chỉ khi nhãn của chúng sai khác ±(n−2)(modm)\pm(n-2)\pmod m (hai hướng cho sai khác n-2 và n+1). Nối đúng các cặp này. Khi đó cách tô tốt chính là cách tô có một cạnh với cả hai đầu đen.