Câu hỏi 82
Có $n$ danh sách ứng cử viên tham gia một cuộc bầu cử. Gọi $h_i$ là tổng số phiếu bầu cho các ứng cử viên trong danh sách thứ $i$. Có $M$ ghế trong cơ quan đại diện.
Anna đề xuất cách phân bổ ghế như sau. Với mỗi danh sách, tính số tham chiếu $v_i=\frac{h_i}{a_i+1}$, trong đó $a_i$ là số ghế đã được phân cho danh sách thứ $i$; ban đầu $a_i=0$, tức là số tham chiếu của mỗi danh sách bằng số phiếu của nó. Ở mỗi bước, tổng cộng có $M$ bước, chọn danh sách có số tham chiếu lớn nhất; nếu có nhiều danh sách cùng lớn nhất thì chọn ngẫu nhiên một trong số đó. Phân thêm một ghế cho danh sách được chọn rồi tính lại số tham chiếu của nó.
Ý tưởng của Bert là nhân số phiếu của mỗi danh sách với $M/K$, trong đó $K=h_1+\cdots+h_n$, rồi làm tròn xuống nếu kết quả không nguyên. Vì việc làm tròn có thể khiến một số ghế chưa được phân bổ, Bert đề nghị nhân số phiếu của tất cả các danh sách với một hệ số $\beta$ thích hợp sao cho số ghế của danh sách thứ $i$ là
$$
m_i=\left\lfloor\frac{\beta h_iM}{K}\right\rfloor,
$$
và $m_1+\cdots+m_n=M$.
Chứng minh rằng nếu tồn tại hệ số $\beta$ như vậy thì hai phương pháp của Anna và Bert cho cùng một cách phân bổ ghế.
Anna đề xuất cách phân bổ ghế như sau. Với mỗi danh sách, tính số tham chiếu $v_i=\frac{h_i}{a_i+1}$, trong đó $a_i$ là số ghế đã được phân cho danh sách thứ $i$; ban đầu $a_i=0$, tức là số tham chiếu của mỗi danh sách bằng số phiếu của nó. Ở mỗi bước, tổng cộng có $M$ bước, chọn danh sách có số tham chiếu lớn nhất; nếu có nhiều danh sách cùng lớn nhất thì chọn ngẫu nhiên một trong số đó. Phân thêm một ghế cho danh sách được chọn rồi tính lại số tham chiếu của nó.
Ý tưởng của Bert là nhân số phiếu của mỗi danh sách với $M/K$, trong đó $K=h_1+\cdots+h_n$, rồi làm tròn xuống nếu kết quả không nguyên. Vì việc làm tròn có thể khiến một số ghế chưa được phân bổ, Bert đề nghị nhân số phiếu của tất cả các danh sách với một hệ số $\beta$ thích hợp sao cho số ghế của danh sách thứ $i$ là
$$
m_i=\left\lfloor\frac{\beta h_iM}{K}\right\rfloor,
$$
và $m_1+\cdots+m_n=M$.
Chứng minh rằng nếu tồn tại hệ số $\beta$ như vậy thì hai phương pháp của Anna và Bert cho cùng một cách phân bổ ghế.