Bài 3

Cho

n

và

k

là các số nguyên dương, và

S

là tập gồm

n

điểm trên mặt phẳng sao cho không có ba điểm nào của

S

thẳng hàng. Giả sử với mỗi điểm

P\in S

có ít nhất

k

điểm của

S

cách đều

P

. Chứng minh rằng

k<\frac12+\sqrt{2n}

Bước 1 trên 5: Đếm liên thuộc từ mỗi tâm

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

Hiểu nôm na

Mỗi cặp điểm cách đều cung cấp một chứng nhân trên đường trung trực.

N\ge n\binom{k}{2}=\frac{nk(k-1)}2

Phân tích chi tiết

Với mỗi $P\in S$ , chọn $k$ điểm ở cùng khoảng cách tới $P$ . Hai điểm được chọn bất kỳ $A,B$ thỏa $PA=PB$ , nên $P$ nằm trên đường trung trực của $AB$ . Do đó mỗi $P$ đóng góp ít nhất $\binom{k}{2}$ liên thuộc $(P,\{A,B\})$ , và tổng cộng trên $n$ điểm ta được $N\ge n\binom{k}{2}=\frac{nk(k-1)}2$ .