Math Labs

Bài 3

Cho nn là một số nguyên dương. Liu Bang và Xiang Yu có một thanh gỗ dài 11 và muốn chia nó cho nhau. Liu đánh dấu nhiều nhất nn điểm trên thanh gỗ, rồi Xiang đánh dấu nhiều nhất nn điểm trên thanh gỗ. Các điểm được đánh dấu đôi một phân biệt. Sau đó, thanh gỗ được cắt tại tất cả các điểm đã đánh dấu, tạo thành một số mảnh. Tiếp theo, họ lần lượt lấy một mảnh chưa ai lấy, với Liu đi trước. Mục tiêu của mỗi người là làm cực đại tổng độ dài các mảnh của mình. Với mỗi nn, hãy xác định giá trị lớn nhất cc sao cho Liu có thể đảm bảo tổng độ dài ít nhất cc, bất kể cách chơi của Xiang.
Bước 1 trên 5: Quy pha lấy mảnh về độ lệch đan dấu G
Bước trướcBước tiếp
x1≥x2≥⋯≥x2n+1≥0,G:=x1−x2+x3−x4+⋯+x2n+1,Liu’s total=1+G2x_1\ge x_2\ge\cdots\ge x_{2n+1}\ge0,\qquad G:=x_1-x_2+x_3-x_4+\cdots+x_{2n+1},\qquad \text{Liu's total}=\frac{1+G}{2}
Phân tích chi tiết

Cho phép các nhát cắt trùng nhau (tạo ra mảnh độ dài 00) để mỗi người thực hiện đúng nn nhát cắt và có 2n+12n+1 mảnh với độ dài x1≥x2≥⋯≥x2n+1≥0x_1\ge x_2\ge\cdots\ge x_{2n+1}\ge0 thỏa ∑i=12n+1xi=1\sum_{i=1}^{2n+1}x_i=1. Trong pha lấy mảnh, mỗi người tối ưu sẽ lấy mảnh lớn nhất còn lại ở lượt của mình, nên Liu thu được x1+x3+⋯+x2n+1x_1+x_3+\cdots+x_{2n+1} và Xiang thu được x2+x4+⋯+x2nx_2+x_4+\cdots+x_{2n}. Theo độ lệch G:=x1−x2+x3−x4+⋯+x2n+1G:=x_1-x_2+x_3-x_4+\cdots+x_{2n+1}, tổng của Liu là 1+G2\tfrac{1+G}{2} và của Xiang là 1−G2\tfrac{1-G}{2}, nên cực đại hóa tổng của Liu tương đương với cực đại hóa GG.