Xin chào mọi người. Đây là lần đầu tiên mình tham gia diễn đàn. Mình đang gặp 1 bài toán khó, xin nhờ mọi người cho ý kiến. Nếu bài toán không đúng box thì xin admin chuyển box hộ mình.
Cho 1 hình vuông 2x2, gọi là $R$. Trong hình vuông $R$ có $N$ điểm, phân bố rải rác. Mỗi điểm có 1 trọng số dương. Gọi $r_{max}$ là hình vuông 1x1 (các cạnh song song với R) mà tổng trọng số các điểm nằm trong nó là lớn nhất. Ta dễ dàng chứng minh được là tỷ số $|r_{max}|/|R| \ge 1/4$.
Bây giờ, ngoài điểm ra chúng ta có thêm cạnh nối 2 điểm bất kỳ. Một điểm có thể có nhiều cạnh, và mỗi cạnh luôn tìm được ít nhất 1 hình vuông 1x1 bao nó (tức là 2 điểm của cạnh nằm trong hình vuông đó). Và cạnh cũng có trọng số. Bây giờ, trọng số của hình vuông 1x1 được định nghĩa là tổng trọng số của điểm và cạnh nằm trong nó.
Giống như trên, gọi $r_{max}$ là hình vuông 1x1 có tổng trọng số lớn nhất. Mình đã chứng minh được rằng nếu trọng số cạnh không bị giới hạn (tức là có thể lớn tuỳ ý), thì tỷ số $|r_{max}|/|R|$ không có cận dưới (tức là có thể nhỏ tuỳ ý). Vì thế mình thêm điều kiện là trọng số của 1 cạnh không thể lớn hơn tổng trọng số của 2 điểm của nó. Tức là $e_{ij} \le w_i + w_j$, với $e_{ij}$, $w_i$, $w_j$ là trọng số của cạnh nối 2 điểm $i$ và $j$, và trọng số của 2 điểm $i$, $j$. Vậy trong trường hợp này, tỷ số $|r_{max}|/|R|$ có cận dưới không? Nếu có, thì bằng bao nhiêu?
Rất mong ý kiến của mọi người.
Solved
