Bài 5

Cho một số nguyên

N \ge 2

. Có

N(N+1)

cầu thủ bóng đá, không ai có cùng chiều cao với ai khác, đứng thành một hàng. Ngài Alex muốn loại bỏ

N(N-1)

cầu thủ khỏi hàng này để còn lại một hàng mới gồm

2N

cầu thủ sao cho

N

điều kiện sau đây được thỏa mãn: không ai đứng giữa hai cầu thủ cao nhất, không ai đứng giữa cầu thủ cao thứ ba và cầu thủ cao thứ tư,

\ldots

, không ai đứng giữa hai cầu thủ thấp nhất. Chứng minh rằng điều này luôn luôn thực hiện được.

Bước 2 trên 7: Chia hàng thành các khối chiều cao

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

G_1<G_2<\cdots<G_N,\qquad |G_j|=N+1

Phân tích chi tiết

Liệt kê các cầu thủ theo thứ tự vị trí là $x_1,\ldots,x_{N(N+1)}$ và gán cho mỗi người thứ hạng chiều cao tổng thể của họ. Chỉ dựa vào chiều cao, chia họ thành $N$ khối liên tiếp $G_1,\ldots,G_N$ , mỗi khối có kích thước $N+1$ , sao cho mọi thành viên của $G_j$ đều thấp hơn mọi thành viên của $G_{j+1}$ . Nếu $2N$ người sống sót cuối cùng chứa đúng $2$ thành viên của mỗi khối, các cặp đó sẽ tự động rơi vào đúng các thứ hạng chiều cao liên tiếp $(2j-1,2j)$ theo thứ tự khối.