Dựa trên Concrete Mathematics, 3.2

1. Đếm số giá trị nguyên trong một tập liên tục

Ở trong đề thi Đại học, ta thường gặp các câu hỏi tính số giá trị nguyên của ~m~ sao cho một phương trình nào đó có nghiệm. Khi giải các câu hỏi dạng này, ta thường ra được kết quả là ~m~ thuộc một tập liên tục (đoạn, khoảng, nửa đoạn) đó với các đầu mút là số nguyên hay số thực. Vậy, ta làm thế nào để đếm được số giá trị nguyên với rủi ro bị sai sót là thấp nhất có thể.

Giả sử ~m \in (a, b]~. Khi đó ~a < m \leq b~.

Theo các bất đẳng thức ta đã học ở bài trước, bất đẳng thức này tương đương với ~\lfloor a \rfloor < m \leq \lfloor b \rfloor~.

Do ~\lfloor \alpha \rfloor~ là số nguyên nên bất đẳng thức này tương đương với ~\lfloor a \rfloor + 1 \leq m \leq \lfloor b \rfloor~

Số số nguyên ~m~ thỏa mãn bất đẳng thức này là ~\lfloor b \rfloor - (\lfloor a \rfloor + 1) + 1 = \lfloor b \rfloor - \lfloor a \rfloor~

Làm tương tự như trên, ta sẽ có những công thức sau để đếm số số nguyên trong một tập liên tục:

• ~[a,b]~: Số giá trị nguyên là ~\lfloor b \rfloor - \lceil a \rceil + 1~
• ~[a,b)~: Số giá trị nguyên là ~\lceil b \rceil - \lceil a \rceil~
• ~(a,b]~: Số giá trị nguyên là ~\lfloor b \rfloor - \lfloor a \rfloor~
• ~(a,b)~: Số giá trị nguyên là ~\lceil b \rceil - \lfloor a \rfloor - 1~

Lưu ý là công thức chỉ đúng khi ~a \leq b~, và khi ta dùng công thức cho ~(a,b)~ thì ~a < b~. Trong trường hợp không thể áp dụng được công thức, ta coi số số nguyên bằng ~0~.

2. Tổng chứa hàm làm tròn

Trong casino có một trò chơi như sau:

• Nhà cái bốc ngẫu nhiên một số nguyên từ 1 đến 1000. Gọi số này là ~n~.
• Nếu ~n~ chia hết cho ~\lfloor \sqrt[3]{n} \rfloor~ thì nhà cái sẽ phải trả thưởng ~5~ nghìn đồng cho người chơi, còn nếu không thì người chơi sẽ phải trả nhà cái ~1~ nghìn đồng

Hãy tính xem người chơi có thể kì vọng có lãi nếu chơi trò chơi này rất nhiều lần hay không?

Gọi số số nguyên ~n~ thỏa mãn ~1 \leq n \leq 1000~ và ~n~ chia hết cho ~\lfloor \sqrt[3]{n} \rfloor~ là ~W~. Ta sẽ tính lợi nhuận kì vọng ~E~ của người chơi theo ~W~.

Ta có tổng cộng ~1000~ trường hợp của ~n~.

Có ~W~ trường hợp nhà cái sẽ phải trả thưởng ~5~ nghìn đồng.

Có ~1000-W~ trường hợp người chơi mất ~1~ nghìn đồng, tức được ~-1~ nghìn đồng.

Vậy lợi nhuận kì vọng của người chơi là ~E = \frac{5W - (1000 - W)}{1000} = \frac{6W - 1000}{1000}~

Người chơi có lãi khi ~E > 0 \Leftrightarrow 6W - 1000 > 0 \Leftrightarrow W > \frac{1000}{6} \Leftrightarrow W \geq 167~

Bây giờ ta sẽ tính ~W~. Sử dụng kí pháp Iverson, ta có:

~W = \sum_{n} [1 \leq n \leq 1000][n \text{ chia hết cho } \lfloor \sqrt[3]{n} \rfloor]~

Do ~n \text{ chia hết cho } \lfloor \sqrt[3]{n} \rfloor \Leftrightarrow \exists m \in \mathbb{Z}: n = m\lfloor \sqrt[3]{n} \rfloor~ nên

~W = \sum_{n, m} [1 \leq n \leq 1000][n = m\lfloor \sqrt[3]{n} \rfloor]~

~W = \sum_{n, m, k} [1 \leq n \leq 1000][k = \lfloor \sqrt[3]{n} \rfloor][n = mk]~

~W = \sum_{n, m, k} [1 \leq n \leq 1000][k \leq \sqrt[3]{n} < k+1][n = mk]~

~W = \sum_{n, m, k} [1 \leq n < 1001][k^3 \leq n < (k+1)^3][n = mk]~

~W = \sum_{n, m, k} [\max(1,k^3) \leq n < \min(1001, (k+1)^3)][n = mk]~

Giờ ta sẽ loại bỏ một biến. Để tránh vòng luẩn quẩn (sau khi biến đổi ta có lại biểu thức ban đầu), ta sẽ loại bỏ biến ~n~. Khi đó:

~W = \sum_{m, k} [\max(1,k^3) \leq mk < \min(1001, (k+1)^3)]~

Để đi tiếp, ta tìm cách tách các trường hợp của ~\max, \min~

Xét ~\max(1, k^3)~. Ta thấy ~1 \leq k^3 \Leftrightarrow 1 \leq k~. Vì thế nếu ~k = 0~, ~\max(1, k^3) = 1~, nếu ~k \geq 1~, ~\max(1, k^3) = k^3~

Xét ~\min(1001, (k+1)^3)~. Ta thấy ~1001 \leq (k+1)^3 \Leftrightarrow \sqrt[3]{1001} \leq k+1 \Leftrightarrow \lceil \sqrt[3]{1001} \rceil \leq k+1 \Leftrightarrow 11 \leq k+1 \Leftrightarrow k \geq 10~. Do đó nếu ~k \geq 10~ thì ~\min(1001, (k+1)^3) = 1001~, còn nếu ~k < 10~ thì ~\min(1001, (k+1)^3) = (k+1)^3~

Vậy ta xét ~k~ trong các trường hợp ~k = 0~, ~1 \leq k < 10~, và ~k \geq 10~

~W = \sum_m [1 \leq 0 < 1] + \sum_{m, k} [1 \leq k < 10][k^3 \leq mk < (k+1)^3] + \sum_{m, k} [k \geq 10][k^3 \leq mk < 1001]~

~W = 0 + \sum_{m, k} [1 \leq k < 10][k^2 \leq m < \lceil \frac{(k+1)^3}{k} \rceil] + \sum_{m, k} [k \geq 10][k^2 \leq m < \frac{1001}{k}]~

~W = \sum_{k} [1 \leq k < 10] \sum_m [m \in [k^2,\frac{(k+1)^3}{k})] + \sum_{k} [k \geq 10] \sum_m [m \in [k^2, \frac{1001}{k})]~

Giờ ta có thể áp dụng công thức đếm số số nguyên trong một tập liên tục để tính ~\sum_m [m \in [k^2,\frac{(k+1)^3}{k})]~ và ~\sum_m [m \in [k^2, \frac{1001}{k})]~, tuy nhiên trước đó ta phải kiểm tra điều kiện áp dụng công thức.

Dễ thấy ~k^2 \leq \frac{(k+1)^3}{k}~ khi ~1 \leq k < 10~, nên ta luôn có thể áp dụng được công thức cho tổng đầu tiên.

Với tổng thứ hai, ~k^2 \leq \frac{1001}{k} \Leftrightarrow k^3 \leq 1001 \Leftrightarrow k \leq \lfloor \sqrt[3]{1001} \rfloor \Leftrightarrow k \leq 10~. Kết hợp với ~k \geq 10~, ta thấy ta chỉ áp dụng được công thức khi ~k = 10~

Vậy

~W = \sum_{1 \leq k < 10} (\lceil \frac{(k+1)^3}{k} \rceil - \lceil k^2 \rceil) + \lceil \frac{1001}{10} \rceil - \lceil 10^2 \rceil~

~W = \sum_{1 \leq k < 10} (\lceil \frac{(k+1)^3}{k} - k^2 \rceil) + 101 - 100~

~W = \sum_{1 \leq k < 10} (\lceil 3k + 3 + \frac{1}{k} \rceil) + 1~

~W = \sum_{1 \leq k < 10} (3k + 3 + \lceil \frac{1}{k} \rceil) + 1~

Dễ thấy ~\forall k > 0: \lceil \frac{1}{k} \rceil = 1~ nên

~W = \sum_{1 \leq k < 10} (3k + 4) + 1~

~W = \frac{(7 + 31) \cdot 9}{2} + 1~ (dãy ~(3k+1)_{k=1}^9~ là dãy cấp số cộng có công thức tổng bằng (số đầu cộng số cuối) nhân số số hạng rồi chia đôi)

~\boxed{W = 172}~

Do ~W = 172 > 167~ nên người chơi sẽ có lãi khi chơi trò chơi này.

Bây giờ giả sử nhà cái bốc một số nguyên từ ~1~ đến ~N~ (ví dụ ~N = 10^9~). Liệu nhà cái và người chơi có tính trước được số trường hợp nhà cái phải trả thưởng cho người chơi để từ đó tính được nhà cái hay người chơi sẽ có lợi hay không?

Để giải đáp câu hỏi này, ta cần tổng quát hóa công thức trên bằng cách thay ~1000~ thành một số nguyên dương ~N~ bất kì. Khi đó,

~W = \sum_{m, k} [\max(1,k^3) \leq mk < \min(N+1, (k+1)^3)]~ (vì ở các bước trước ta không động đến hằng số ~1000~)

Xét ~\max(1,k^3)~. Ta thấy nếu ~k = 0~ thì ~\max(1, k^3) = 1~, nếu ~k \geq 1~ thì ~\max(1,k^3) = k^3~

Xét ~\min(N+1, (k+1)^3)~.

~N+1 < (k+1)^3 \Leftrightarrow \sqrt[3]{N+1} < k+1 \Leftrightarrow \lfloor \sqrt[3]{N+1} \rfloor - 1 < k~.

Vậy nếu ~k > \lfloor \sqrt[3]{N+1} \rfloor - 1~ thì ~\min(N+1, (k+1)^3) = N+1~, còn nếu ~k \leq \lfloor \sqrt[3]{N+1} \rfloor - 1~ thì ~\min(N+1, (k+1)^3) = (k+1)^3~.

Để đỡ lằng nhằng, ta giả sử ~\lfloor \sqrt[3]{N+1} \rfloor - 1 \geq 1 \Leftrightarrow \sqrt[3]{N+1} \geq 2 \Leftrightarrow N+1 \geq 8 \Leftrightarrow N \geq 7~. Nếu ~N < 7~, ta tính tay thay vì sử dụng công thức tổng quát.

Khi đó

~W = \sum_{m} [1 \leq 0 < 1] + \sum_{m,k} [1 \leq k \leq \lfloor \sqrt[3]{N+1} \rfloor - 1][k^3 \leq mk < (k+1)^3] + \sum_{m,k} [k \geq \lfloor \sqrt[3]{N+1} \rfloor][k^3 \leq km < N+1]~

~W = \sum_{k} [1 \leq k \leq \lfloor \sqrt[3]{N+1} \rfloor - 1] \sum_m [m \in [k^2, \frac{(k+1)^3}{2})] + \sum_{k} [k \geq \lfloor \sqrt[3]{N+1} \rfloor] \sum_m [m \in [k^2, \frac{N+1}{k})]~

Kiểm tra điều kiện sử dụng công thức đếm số số nguyên trong một tập liên tục. Ta thấy ta luôn có thể sử dụng được công thức cho tổng đầu tiên. Với tổng thứ hai:

~k^2 \leq \frac{N+1}{k} \Leftrightarrow k^3 \leq N+1 \Leftrightarrow k \leq \sqrt[3]{N+1}~

nên ta chỉ sử dụng được công thức khi ~k=\lfloor \sqrt[3]{N+1} \rfloor~

Để ngắn gọn, đặt ~K = \lfloor \sqrt[3]{N+1} \rfloor~

Khi đó

~W = \sum_{k=1}^{K-1} (\lceil \frac{(k+1)^3}{2} \rceil - \lceil k^2 \rceil) + \lceil \frac{N+1}{K} \rceil - \lceil K^2 \rceil~

~W = \sum_{k=1}^{K-1} (3k+4) + \lceil \frac{N+1}{K} \rceil - K^2~

~\boxed{W = \frac{(8 + 3K)(K-1)}{2} + \lceil \frac{N+1}{K} \rceil - K^2}~

Với công thức tổng quát này, ta có thể tính được ~W~ trong ~O(1)~ hoặc ~O(\log N)~ thay vì ~O(N)~.