BÀI TOÁN "ĐẤU TRƯỜNG 100"

Tối thứ 6 hàng tuần, trên kênh VTV3 – Đài Truyền hình Việt Nam – có một chương trình giải trí rất hấp dẫn, đó là chương trình “Đấu trường 100”. Luật chơi của chương trình này như sau:

• Đầu tiên, có 1000 điểm được chia đều cho 100 khán giả trong trường quay.
• Người chơi chính và các khán giả cùng trường quay sẽ phải trả lời các câu hỏi mà chương trình đưa ra.
• Sau câu hỏi đầu tiên, sẽ có một số khán giả trả lời sai và người chơi chính sẽ nhận được tổng số điểm mà những người trả lời sai đang giữ.
• Tiếp đó, 1000 điểm lại được chia đều cho những người chơi còn lại (trước khi chia thì số điểm của mỗi người lập tức quay về 0), rồi tất cả tiếp tục trả lời câu hỏi số 2.
• Sau câu hỏi số 2, người chơi chính lại nhận thêm số điểm của những ai trả lời sai. Cứ như vậy, trò chơi kéo dài đến khi người chơi chính trả lời sai hoặc xin dừng cuộc chơi, hoặc loại hết 100 khán giả trong trường quay.

Trong quá trình chơi, người chơi chính sẽ có ba lần sử dụng quyền giải thoát, nghĩa là người dẫn chương trình sẽ đọc ra đáp án của câu hỏi, nhưng người chơi sẽ mất một số điểm lần lượt bằng 25%, 50%, 75% số điểm mà anh ta hiện có, đồng thời anh ta cũng sẽ không nhận được điểm từ những khá giả trả lời sai câu hỏi đó đó Ngoài quyền giải thoát, người chơi chính còn có quyền nhân đôi, nghĩa là nếu dùng quyền này tại một câu hỏi nào đó thì anh ta sẽ nhận được số điểm gấp đôi tổng số điểm của những khán giả trả lời sai.

Tổng số điểm mà người chơi chính tích lũy được sẽ được nhân với 10000, và đó sẽ là mức tiền thưởng người đó nhận được; đồng thời, theo quy định, khi loại được 80 người thì người chơi chính chắc chắn nhận 2 triệu đồng.

Bài viết quan tâm đến số điểm lớn nhất mà người chơi chính có thể nhận được, tức là tìm giá trị cực đại về điểm của người chơi chính theo luật chơi nêu trên. Ta có thể thấy ngay rằng, để đạt được số điểm tối đa, người chơi chính không nên sử dụng bất kỳ “quyền giải thoát” nào cả và người đó sẽ dúng quyền nhân đôi đúng lúc ở câu hỏi cuối cùng (vì khi đó anh ta có thể nhận đến 2000 điểm ở câu này, và tất nhiên lúc này anh ta đã loại hết 100 người).

Giả sử người chơi chính đạt số điểm lớn nhất sau n câu hỏi. Tại câu hỏi thứ i, anh ta loại được $k_i$ người (tức có $k_i$ người trả lời sai). Khi đó:

Những câu không có ai trả lời sai thì không làm tăng điểm cho người chơi chính, nên ta có thể giả sử mọi $k_i \ge 1$ (mỗi câu loại ít nhất 1 người).

Theo luật, sau mỗi câu hỏi, người chơi chính nhận số điểm đúng bằng tổng điểm của những người vừa trả lời sai. Nhưng trước mỗi câu hỏi mới, 1000 điểm lại chia đều cho các khán giả còn lại (trả lời đúng ở câu trước đó). Khi còn m khán giả, thì mỗi người giữ $\frac{1000}{m}$ điểm. Do đó, nếu trong câu hỏi đó có $k_i$ người sai, người chơi chính lấy được: $ k_i \times \frac{1000}{m}.$, trong đó m là số người chưa bị loại trước câu hỏi đó.

Cụ thể, chi tiết theo thứ tự các câu như sau:

• Sau câu hỏi thứ 1, với 100 khán giả ban đầu. Nếu $k_1$ người sai, người chơi chính nhận: $10 \, k_1$ (vì $\frac{1000}{100} = 10$).
• Sau câu hỏi thứ 2, số khán giả còn lại là $100 - k_1$. Nếu $k_2$ người sai, anh ta nhận: $k_2 \times \frac{1000}{100 - k_1}.$
• Sau câu hỏi thứ 3, còn $100 - (k_1 + k_2)$ người. Nếu $k_3$ người sai, anh ta nhận: $k_3 \times \frac{1000}{100 - (k_1 + k_2)}.$
• ...
• Sau câu hỏi thứ n, khi còn $100 - \sum_{m=1}^{n-1} k_m$ người, nếu $k_n$ người sai, anh ta nhận: $k_n \times \frac{1000}{100 - \sum_{m=1}^{n-1} k_m}.$

Trong chương trình còn có quyền “nhân đôi” một lần trong cuộc chơi. Nếu dùng ở câu hỏi thứ n, anh ta sẽ nhận số điểm gấp đôi, tức:

Ngoài ra, nếu anh ta đã loại được 80 người, thì chắc chắn có thêm 2 triệu đồng tiền thưởng.

Bây giờ, chúng ta gọi $P(k_1, k_2, \ldots, k_n)$ là tổng số điểm mà người chơi chính nhận được sau khi loại hết $k_1, k_2, \ldots, k_n$ người chơi (trong đó $\sum k_i = 100$), và dùng quyền nhân đôi ở câu hỏi cuối. Khi đó:

Mục tiêu là tìm giá trị lớn nhất của: $$P(k_1, k_2, \ldots, k_n)$$ dưới các ràng buộc $$k_1 + k_2 + \dots + k_n = 100,\; k_i \ge 1,\; n \ge 1.$$

Cách tối đa hóa $P(k_1,k_2,\ldots,k_n)$, có thể làm gọn gàng từ nhận xét sau:

Nếu $k_n > 1$, dễ thấy \[ P\bigl(k_1, \ldots, k_{n-1},\,k_n - 1,\,1\bigr) \;-\; P\bigl(k_1, \ldots, k_{n-1},\,k_n,\,1\bigr) \;=\; \frac{1000\,\bigl(k_n - 1\bigr)} {\,100 \;-\;\displaystyle\sum_{m=1}^n k_m\,} \;>\;0. \] Vậy để $P\bigl(k_1, \ldots, k_n\bigr)$ đạt giá trị lớn nhất thì \[ k_n = 1. \] Tương tự, với cách làm trên, ta cũng có thể chứng minh \[ k_i = 1 \quad \text{với mọi } i = 2,\,3,\,\ldots,\,n. \] Thật vậy, giả sử ta đã có $k_n = 1$ và với mọi $i$ từ $m+1$ đến $n$ đều có $k_i = 1$. Ta sẽ chứng minh $k_m = 1$. Nếu $k_m > 1$ thì: \[ P\bigl(k_1,\,k_2,\,\dots,\,k_{m-2},\;\;k_{m - 1}+k_m-1,\underbrace{\;1,\;1,\dots,1}_{\text{n-m+1 số 1}}\bigr) \;-\; P\bigl(k_1,\,k_2,\,\dots,\,k_{m-1},\;k_m,\underbrace{\;1,\;1,\dots,1}_{\text{n-m số 1}}\bigr) \;=\; \frac{1000\,(k_m - 1)}{100 \;-\;\displaystyle\sum_{i=1}^{m-2} k_i} \;>\;0. \] Do đó, để $P(k_1,\,\dots,\,k_n)$ đạt giá trị lớn nhất thì $k_m = 1$. Theo giả thuyết quy nạp, để $P\bigl(k_1,\dots,k_n\bigr)$ đạt giá trị lớn nhất thì \[ k_i = 1 \quad \text{với mọi } i = 2,\,3,\,\ldots,\,n. \] Khi đó $k_1 = 101 - n$. Theo công thức xác định $P$, ta có: \[ P\bigl(101-n,\;1,\;1,\;\dots,\;1\bigr) \;=\; 10\bigl(101 - n\bigr) \;+\; \sum_{i=2}^{\,n-1}\,\frac{1000}{\,n - i + 1\,} \;+\; 2000. \] Thay $n$ bởi $n+1$, ta xét hiệu: \[ P\bigl(101 - (n+1),\underbrace{\,1,\,1,\dots,1}_{\text{n số 1}}\bigr) \;-\; P\bigl(101 - n,\underbrace{\,1,\,1,\dots,1}_{\text{n-1 số 1}}\bigr) \] \[ =\; \Bigl[\, 10\bigl(101-(n+1)\bigr) +\sum_{r=2}^{\,n}\,\frac{1000}{\,n-r+2\,} +2000 \Bigr] \\ -\; \Bigl[\, 10\bigl(101-n\bigr) +\sum_{i=2}^{\,n-1}\,\frac{1000}{\,n-i+1\,} +2000 \Bigr] \] \[ = \frac{1000}{\,n\,} \;-\; 10 \;\ge\; 0 \quad(\text{vì } n \le 100). \]

Như vậy, $P(k_1,\dots,k_n)$ đạt giá trị lớn nhất nếu $n=100$ và $k_i=1$ với $i=1,2,\dots,100$. Nói cách khác, người chơi chính sẽ đạt số tiền thưởng lớn nhất khi ở mỗi câu hỏi anh ta loại đúng 1 người cùng chơi, và không sử dụng quyền giải thoát, ở câu 100 loại luôn khán giả cuối cùng và áp dụng nhân đôi ở câu này, sẽ đem lại tổng điểm lớn nhất.

Với $n = 100$ và $k_i = 1$ cho mọi $i$, người chơi chính có thể nhận được (sau khi quy đổi thành tiền): \[ 10{,}000 \Bigl( 10 \;+\; \sum_{i=2}^{99} \frac{\,1000\,}{\,100 - i + 1\,} \;+\; 2000 \Bigr) \;+\; 2{,}000{,}000 \] nghĩa là xấp xỉ 63.874.000 (đồng). Thật là một con số ấn tượng phải không các bạn. Hi vọng rằng sẽ có các bạn trẻ yêu toán tham gia và thành công trong chương trình Đấu trường 100 với chiến thuật hợp lí để giành được số tiền thưởng lớn nhất của chương trình.

Chú ý: Số liệu và luật chơi của chương trình này được tác giả lấy trong năm 2009.