MathLabs

Bài 3

Xét nn hình tròn C1,C2,…,CnC_1,C_2,\ldots,C_n trong mặt phẳng sao cho với mọi 1≤i<n1\le i<n, tâm của CiC_i nằm trên đường tròn của Ci+1C_{i+1}, và tâm của CnC_n nằm trên đường tròn của C1C_1. Định nghĩa điểm là số cặp (i,j)(i,j) sao cho CiC_i chứa thực sự CjC_j. Tìm điểm lớn nhất có thể.
Bước 1 trên 6: Mã hóa quan hệ chứa bằng cặp có thứ tự
Bước trướcBước tiếp
score⁡(C)=∣SC∣,SC={(i,j):Ci properly contains Cj}\operatorname{score}(C)=|S_C|,\qquad S_C=\{(i,j):C_i\text{ properly contains }C_j\}
Phân tích chi tiết

Gọi SCS_C là tập các cặp có thứ tự (i,j)(i,j) sao cho CiC_i chứa thực sự CjC_j. Quan hệ chứa thực sự phản xạ không và bắc cầu; hai hình tròn không thể chứa thực sự nhau theo cả hai hướng.