Câu hỏi 141
$n$ thí sinh của một kỳ EGMO được đặt tên là $C_{1}, \ldots, C_{n}$. Sau cuộc thi, họ xếp hàng trước nhà hàng theo các quy tắc sau.
- Ban giám khảo chọn thứ tự ban đầu của các thí sinh trong hàng.
- Mỗi phút, Ban giám khảo chọn một số nguyên $i$ với $1 \leq i \leq n$.
- Nếu thí sinh $C_{i}$ có ít nhất $i$ thí sinh khác đứng trước mình, cô ấy trả một euro cho Ban giám khảo và tiến lên phía trước trong hàng đúng $i$ vị trí.
- Nếu thí sinh $C_{i}$ có ít hơn $i$ thí sinh khác đứng trước mình, nhà hàng mở cửa và quá trình kết thúc.
a. Chứng minh rằng quá trình không thể kéo dài vô hạn, bất kể Ban giám khảo lựa chọn thế nào.
b. Với mỗi $n$, xác định số euro lớn nhất mà Ban giám khảo có thể thu được bằng cách khéo léo chọn thứ tự ban đầu và dãy các nước đi.
(Hungary)
- Ban giám khảo chọn thứ tự ban đầu của các thí sinh trong hàng.
- Mỗi phút, Ban giám khảo chọn một số nguyên $i$ với $1 \leq i \leq n$.
- Nếu thí sinh $C_{i}$ có ít nhất $i$ thí sinh khác đứng trước mình, cô ấy trả một euro cho Ban giám khảo và tiến lên phía trước trong hàng đúng $i$ vị trí.
- Nếu thí sinh $C_{i}$ có ít hơn $i$ thí sinh khác đứng trước mình, nhà hàng mở cửa và quá trình kết thúc.
a. Chứng minh rằng quá trình không thể kéo dài vô hạn, bất kể Ban giám khảo lựa chọn thế nào.
b. Với mỗi $n$, xác định số euro lớn nhất mà Ban giám khảo có thể thu được bằng cách khéo léo chọn thứ tự ban đầu và dãy các nước đi.
(Hungary)