Về cách giải một bài toán

Trước tiên, tôi phải xin lỗi vì lặn quá lâu. Thực ra thì tôi không cần phải xin lỗi, bởi vốn dĩ việc viết lách không cưỡng cầu được, nhưng rồi tôi vẫn làm, chỉ bởi đợt này tôi cài ứng dụng Spiderum trên điện thoại và thi thoảng vẫn thấy thông báo rằng có người vào upvote bài của tôi. Tức là đâu đó vẫn có người đọc. Mà vẫn có người đọc là một thứ duyên nợ của người viết. Duyên vì biết đến, nợ vì áy náy. "Ô hay, biết đâu người ta chờ mình".

Tôi sẽ đưa ra lý do (muôn thuở) rằng vì tôi không biết viết cái gì. Cuộc sống của tôi vừa phải ít thứ để phàn nàn. Những thứ có thể phàn nàn được thì lại không phải có thể viết được. Vì một là vụn vặt quá, hai là cá nhân quá. Vụn vặt quá thì khó liên kết, mà cá nhân quá thì khó nói ra. Tôn chỉ viết của tôi vốn không muốn đụng vào hai thứ đấy. Bởi vì tôi vẫn tôn trọng người đọc của tôi ở một mức độ nhất định.

Thứ tôi sắp viết, xuất thân cũng chỉ là một thứ vụn vặt. Nhưng sự vụn vặt này lại đem cho tôi một chút hứng thú. Tôi vốn đắn đo việc có nên đem ra cho bàn dân thiên hạ hay không, rồi đến hôm nay, tự dưng tôi nghĩ tôi có thể viết được. Nên tôi viết thôi.

Vài lời mở đầu, còn giờ vào vấn đề.

Ở trong khuôn khổ bài viết này, tôi sẽ chỉ đưa ra cách giải câu b. Lý do:

1. Câu a tương đối dễ, còn câu c nặng về tính toán cơ học

2. Câu b là câu tôi tìm ra được một cách giải đẹp, câu c tôi chưa nghĩ ra được cách giải nào đẹp cả

3. Tôi sẽ bỏ qua những phần tính toán cơ học, bởi phần đấy không phải là thứ tôi muốn đề cập đến quá nhiều và thêm nữa là tôi lười viết hết ra (cách kinh điển của Fermat khi không giải được bài toán)

4. Nếu ai muốn biết hướng giải câu c thì nhắn.

Trước khi bước vào phần tìm lời giải, thì nên nhớ rằng đây là một bài toán cấp 3. Tức là việc sử dụng lý thuyết xác suất chỉ nên dừng ở cơ bản, cụ thể hơn ở bài này là lý thuyết đếm, không đụng vào những lý thuyết cao hơn (ví dụ như xác suất có điều kiện chẳng hạn).

Đầu tiên thì nên để ý rằng về mặt tổng quát, đây là bài toán xác suất với không gian mẫu có kết quả tương đương nhau (sample spaces with equally likely outcomes). Chính vì vậy nên câu a là để xác định số lượng kết quả của không gian mẫu (S), còn câu b và câu c chỉ đơn thuần là tính toán số lượng kết quả của các sự kiện khác nhau (E). Cả hai câu b và c đều tuân thủ theo nguyên tắc về xác suất của một sự kiện (P(E)) trong một không gian S:

Khi đã xác định được như vậy thì ta chỉ cần đếm được số lượng kết quả của sự kiện là xong. Thông thường thì sẽ có hai cách để làm việc này:

- Cách dễ nhất là liệt kê, hay mấy thằng bọn tôi hay gọi vui với nhau là cách trâu bò súc vật

- Tìm được quy luật để đếm cho một kết quả, và suy ra công thức tổng quát, hay còn gọi là cách cho con người

Đối với câu b, hai cách này sẽ được triển khai như sau:

Trước tiên, biết rằng với x_1, x_2, x_3, x_4 có một xúc sắc với tổng bằng ba xúc sắc còn lại, mà trong đó:

- min(x_n) = 1

- max(x_n) = 6

Suy ra:

Giá trị của một xúc sắc x_i bất kỳ trong trường hợp x_i bằng tổng ba xúc sắc còn lại chỉ có thể ở trong khoảng [3, 6]. Như vậy:

Thì... đếm thôi. Đối với giá trị của mặt xúc sắc trong khoảng [3,6]. Ta biết được sẽ có các trường hợp sau:

3 = 1 + 1 + 1

4 = 1+ 1 + 2

5 = 1 + 1 + 3

5 = 1 + 2 + 2

6 = 1 + 1 + 4

6 = 1+ 2 + 3

6 = 2 + 2 + 2

Từ đây các bạn có thể dễ dàng tính ra được số lượng kết quả cho từng trường hợp. Chỉ có một lưu ý nhỏ ở đây, đấy là vì các bạn gieo xúc sắc nên thứ tự của xúc sắc sẽ quan trọng. Cụ thể hơn, ví dụ với trường hợp tổng bằng 4 thì sẽ có 3 trường hợp khác nhau là (1, 1, 2), (1, 2, 1), (2, 1, 1) - hay còn gọi là cách đếm hoán vị (permutation) điển hình.

Nên nhớ rằng đây luôn là một cách để kiểm chứng kết quả tốt. Nếu bạn có học lập trình thì trong nhiều trường hợp, brute force luôn là một lựa chọn. Tuy nhiên, trong các bài thi, thường cách này sẽ không được điểm cao. Và ở một trường hợp tệ hơn, nếu như chúng ta có bài toán là n xúc sắc (1 xúc sắc bằng tổng của n-1 xúc sắc còn lại) thì cách này là bất khả thi.

Xin nói lại một lần nữa là việc gọi trâu bò súc vật hay con người thuần túy là gọi vui của những người giải toán, chứ không có ý định xúc phạm.

Quay trở lại bài toán. Ở đây chúng ta thấy điều kiện của bài toán là một xúc sắc bằng tổng của ba xúc sắc còn lại. Nếu như viết tất cả các trường hợp trên ra thì dài, nhưng nếu có một công thức tổng quát thì sao? Thực ra việc này rất đơn giản, đấy chính là:

Với X là một số tự nhiên bất kỳ:

X = 1 + 1 + .... + 1 (với X số 1)

Như vậy, chúng ta có thể viết lại các trường hợp trên chỉ với một cách biểu diễn. Ví dụ:

3 = 1 + 1 + 1

4 = 1 + 1 + 1 + 1

5 = 1 + 1 + 1 + 1 + 1

6 = 1 + 1 + 1 + 1 + 1 + 1

Và để quy về việc một xúc sắc có tổng bằng 3 xúc sắc còn lại, hãy thử biến vế bên phải thành một tập hợp xem sao. Ví dụ:

4 sẽ được biểu diễn bằng tập hợp {1, 1, 1, 1}. Và việc có tổng bằng 3 xúc sắc sẽ tương ứng với việc phân vùng cho tập hợp này thành 3 phần riêng biệt nhau. Thử biểu diễn việc phân vùng này bằng một dấu gạch dọc "|". Ta sẽ dễ dàng thấy rằng để phân vùng cho tập hợp này thành 3 phần riêng biệt, ta cần đưa 2 vạch dọc vào 3 chỗ trống giữa các phần tử theo cách như sau:

Tập hợp: 1 . 1 . 1 . 1 ( "." hiển thị chỗ trống giữa 2 phần tử)

Một ví dụ của chia 3: 1 . 1 | 1 | 1

Và như vậy, bài toán sẽ trở thành "Chọn 2 "." trong 3 "."

Kết quả sẽ là 2C3 (tổ hợp chập 2 của 3), cũng chính là 3. Các trường hợp khác tương tự.

"Cách dành cho con người", khi tổng quát hóa lên chính là Các số Stirling loại hai (Stirling number of the second kind), một trong những bài toán phân hoạch tập hợp (partition) điển hình. Bài toán có thể được diễn giải như sau:

Phân hoạch của một tập hợp S, là tổng hợp của n tập con không giao nhau P_1, P_2, ..., P_n thỏa mãn các điều kiện sau:

- P_i không phải là tập rỗng

- Hợp của các tập con phải bằng tập S: P1 ∪ P2 ∪ ... ∪ Pn = S

- Giao của hai tập con bất kỳ phải rỗng: Pa ∩ Pb = { ∅ }, với a ≠ b và n ≥ a, b ≥ 0

Cách tính n trong bài toán này tương tự như cách giải cho con người ở trên, tôi sẽ để các bạn tự xử.

Thực ra thì cũng chẳng có ý nghĩa gì cả. Chỉ có một điều thú vị đấy là tôi tìm ra lời giải của bài toán này trong một tình huống hơi buồn cười. Lúc mới đọc đề thì tôi cũng chỉ nghĩ đến cách đếm trâu bò trước, và dành cả buổi tối hôm đấy tìm cách giải đẹp. Tôi nghĩ đến tận hôm sau, và trong lúc trên đường đi làm, nhìn cái đèn đỏ, với mỗi giây giảm đi một, tự nhiên có một cái công tắc đèn đâu đó trong đầu sáng lên, khiến tôi chợt nghĩ: Hay thử biến nó thành bài toán phân hoạch tập hợp toàn số 1 xem sao?

Khi đến văn phòng, việc đầu tiên tôi làm là lôi cái bảng của công ty ra viết lên lời giải. Trong suốt thời gian nhiều chuyện đau đầu vừa rồi, đấy là giây phút tôi hạnh phúc nhất. Phần vì tôi giải được bài toán, phần (trẻ con) khác là tôi tìm ra lời giải đẹp hơn thằng bạn thân của tôi, mà hôm nọ nó vừa bêu xấu tôi trên mạng xã hội rằng tôi không nhớ cách giải của định lý Fermat nhỏ. Trong suốt hơn 20 năm chơi với nó chắc tôi chỉ có vài ba pha tỏa sáng như vậy. Đùa vậy thôi chứ nó là người khiến đến giờ tôi vẫn học và làm toán, đôi khi chỉ vì những giây phút sung sướng khi tìm ra được lời giải đẹp cho một bài toán nào đó.

Thôi, thế là hết giờ nghỉ trưa. Hi vọng sắp tới tôi có thể có hứng thú mà viết thêm cái gì đó. Mong là mình vẫn có người đọc.