Math Labs

Bài 6

Cho số nguyên n>1n>1 và tập SS gồm nn điểm trong mặt phẳng sao cho khoảng cách giữa hai điểm phân biệt bất kỳ của SS ít nhất bằng 11. Chứng minh rằng có một đường thẳng ℓ\ell phân tách SS sao cho khoảng cách từ mọi điểm của SS đến ℓ\ell ít nhất bằng cn−1/3c n^{-1/3} với một hằng số tuyệt đối c>0c>0. (Đường thẳng ℓ\ell phân tách một tập điểm SS nếu có một đoạn thẳng nối hai điểm của SS cắt ℓ\ell.)
Bước 1 trên 8: Chọn khoảng trống hình chiếu lớn nhất
Bước trướcBước tiếp
Hiểu nôm na

Khoảng trống hình chiếu lập tức cho một đường phân tách.

d(P,Q)≥1(PeQ),δ=max⁡mmax⁡{extgapofconsecutiveprojectionsontom}d(P,Q)\ge1\quad(P e Q),\qquad \delta=\max_{m}\max\{ ext{gap of consecutive projections onto }m\}
Phân tích chi tiết

Gọi δ\delta là khoảng trống lớn nhất giữa các hình chiếu liên tiếp khi chiếu lên một đường thẳng bất kỳ mm. Khoảng trống dài δ\delta cho đường thẳng vuông góc với mm qua trung điểm của nó; đường này phân tách SS và mọi điểm cách nó ít nhất δ/2\delta/2.