ĐỊNH LÝ LUCAS

Add a comment

A: Nelson Niu, người truyển cảm hứng toán học.

Khoảng 2 năm trước, tôi có vinh dự được nghe Po – Shen Loh giải thích định lý Lucas và đưa ra một chứng minh chặt chẽ cho nó. Trước đó tôi từng xem qua định lý Lucas cùng chứng minh, và mặc dù có thể hiểu được phát biểu định lý cũng như chứng minh, bản chất của lời giải thích dường như cực kì gượng gạo, và sau một thời gian thì cả nội dung định lý lẫn chứng minh chẳng còn đọng lại gì trong đầu tôi cả.

Trái lại, buổi nói chuyện với Po – Shen Loh là một câu chuyện hoàn toàn khác biệt. Anh giải thích định lý và chứng minh theo một cách cực kì rõ ràng; và thực tế, định lý dễ hơn ta tưởng rất nhiều. Dưới đấy tôi sẽ diễn giải lại giải thích của anh, với chút ít chỉnh sửa, nhưng tất nhiên vẫn trung thành với nội dung ban đầu.

Tôi sẽ giả định rằng ta có đủ kiến thức cần thiết về hệ số nhị thức, hay “tổ hợp” nếu nói theo ngôn ngữ thông thường, số cách chọn ra k vật phân biệt từ n vật khác nhau. Ta sẽ kí hiệu hệ số này dưới dạng {n}\choose{k}

Bây giờ ta xét hệ số nhị thức sau đây:

{1193}\choose {407}

Đây là một số rất lớn. Viết dưới dạng tường minh thì nó có 331 chữ số, lớn tới nỗi nếu bạn gõ vào Google “1193 choose 407”, nó sẽ không cho ra kết quả như trường hợp bạn gõ “4 choose 2”.

Nhưng nếu bạn chỉ muốn một số trong 331 chữ số đó thì sao: cụ thể, là chữ số tận cùng. Liệu có cách nào để xác định được chữ số tận cùng mà không cần phải biết giá trị cụ thể của số trên không? Hay hơn thế nữa, liệu có thể xác định được chữ số tận cùng mà chỉ cần tính tay thôi được không?

Chà {{1193}\choose{407}} =\frac{1193!}{407!\left(1193-407\right)!}, và với một chút tính toán đơn giản, bạn có thể dễ dàng chỉ ra tử chia hết cho lũy thừa 2 bậc bao nhiêu, và cả mẫu nữa. Nếu như lũy thừa của 2 ở tử khử hết lũy thừa của 2 ở mẫu, thì hệ số nhị thức trên là lẻ, còn nếu không nó chẵn. Tôi sẽ không giải thích chi tiết ở đây ngay, vì chúng ta sẽ có một phương pháp khác để xác định tính chẵn lẻ ngay thôi, nhưng nếu bạn hứng thú, hãy xem thử công thức Legendre.

Rồi, hãy giả sử rằng ta đã xác định xong, và {1193}\choose{407}, là chẵn. Khi đó lựa chọn cho chữ số tận cùng giảm xuống chỉ còn 5 số 0, 2, 4, 6, 8. Giá như ta biết được số dư của hệ số này khi chia cho 5, ta sẽ xác định được chữ số tận cùng của nó: nếu số dư là 0 thì chữ số tận cùng sẽ là 0, nếu dư 1 thì chữ số tận cùng là 6, nếu dư 2 chữ số tận cùng là 2, nếu dư 3 chữ số tận cùng là 8 và dư 4 thì chữ số tận cùng là 4. (Và lần nữa, nếu bạn hứng thú tại sao như vậy , xem định lý Thặng dư Trung Hoa.)

Bằng kĩ thuật tương tự như cách mà ta dùng để xác định tính chẵn lẻ của {1193}\choose{407}, ta có thể dùng để xác định xem hệ số trên có chia hết cho 5. Hóa ra là không. Nhưng như thế vẫn còn lại những 4 khả năng: 2, 4, 6, 8. Câu hỏi bây giờ không chỉ đơn giản là có chia hết hay không nữa. Ta cần phải chỉ ra được số dư của {1193}\choose{407} khi chia cho 5.

Bây giờ ta sẽ sắp xếp lại các con số một chút để làm cho vấn đề trở nên dễ hơn. Ta biết rằng có thể viết 1193 dưới dạng 1.1000 + 1.100 + 9.10 + 3.1, ta có thể thay 10 bởi một số nào đó khác, mà ta gọi chung là cơ số. Có thể trước đây bạn đã thấy qua số nhị phân rồi đấy, trong cơ số 2, với các chữ số là 0 và 1. Vì vấn đề ta đang xử lý liên quan đến 5, hãy thử viết 1193 và 407 trong cơ số 5, với chỉ số ở dưới để tránh nhầm qua hệ thập phân:

1193 = 1.5^{4} + 4. 5^{3} + 2. 5^{2} + 3.5^{1} + 3.5^{0} = 14233_{5}

407=3. 5^{3} + 1. 5^{2} + 1.5^{1} + 2.5^{0} = 3112_{5}

Có 2 thứ cần chú ý ở đây: các chữ số đều là những số từ 0 đến 4 ( hay nói chung, là các số nằm từ 0 đến số liền kề cơ số), và cũng như có duy nhất cách viết một số xác định trong hệ thập phận, chỉ có duy nhất một cách viết 1193 trong hệ cơ số 5, hay hệ cơ số 8, hoặc bất kỳ một hệ nào khác.

Giờ ta có thể viết lại hệ số nhị thức dạng

{14233_{5}}\choose{03112_{5}}

Tới đây ta có một mẹo để làm gọn tính toán. Khi chia cho 5, hệ số trên có cùng số dư với tích các hệ số nhị thức sau:

{{1}\choose{0}}{{4}\choose{3}}{{2}\choose{1}}{{3}\choose{1}}{{3}\choose{2}}

Phải: đây chỉ đơn giản là các chữ số trong hệ cơ số 5, tách ra thành từng cặp rời nhau.

Và giờ tính toán trở nên đơn giản hơn rất nhiều. Khải triển trên ứng với

1.4.2.3.3=72

có số dư là 2 khi chia cho 5. Vậy trong 4 lựa chọn còn lại cho chữ số tận cùng, số 2 là số thỏa mãn yêu cầu.

Mẹo mà ta sử dụng ở trên chính là định lý Lucas, và không chỉ sử dụng được riêng cho số 5, và còn hiệu quả với bất kỳ số nguyên tố nào khác. Ta có thể sử dụng định lý trên thay vì định lý Legendre để xác định tính chẵn lẻ của tử và mẫu, bằng cách chuyển các số về dạng nhị phân và tìm tích của các hệ số nhị thức với giá trị nhỏ hơn rất nhiều mà không làm thay đổi số dư khi chia cho 2. (2 định lý trên bản chất là tương đương, chỉ có cấu trúc của chúng là hơi khác một chút).

Ta có thể phát biểu định lý Lucas một cách hàn lâm hơn như sau: Cho

m = m_{k}p^{k} + m_{k-1}p^{k-1} + \dotsc +m_{1}p + m_{0}

m = n_{k}p^{k} + n_{k-1}p^{k-1} +\dotsc + n_{1}p + n_{0}

là các phân tích của m,n trong cơ số p, thì hệ số nhị thức m \choose n và tích các hệ số nhị thức:

{m_{k} \choose n_{k}}{m_{k-1} \choose n_{k-1}} \dotsc {m_{1} \choose n_{1}}{m_{0} \choose n_{0}}

Có cùng số dư khi chia cho p, với mọi số nguyên không âm m, n và p nguyên tố.

Mẹo này có thể gây ngạc nhiên đấy. Trước đây chắc bạn đã từng thấy một mẹo rút gọn phân số ngớ ngân như sau:

\frac{64}{16}=\frac{6}{1}.\frac{4}{6}=4

Hiển nhiên, mẹo này không đúng, ví dụ:

\frac{43}{31} \neq \frac{4}{3}.\frac{3}{1}=4

Tuy nhiên nếu ta xét các số này được viết trong hệ cơ số 7, tức là {64_{7} \choose 16_{7}}, ta có thể nói, “tương tự ” như {6 \choose 1}{4 \choose 6} — ít nhất là khi ta xét số dư của nó khi chia cho 7. Tương tự {43_{7} \choose 31_{7}} có cùng số dư {4 \choose 4}{3 \choose 1} khi chia cho 7.

Có một điều cần làm rõ trước ở đây: nếu n<k, thì t quy ước {n \choose k}=0. Do đó trong ví dụ trên, {4 \choose 6}=0. Điều này cũng tương tự như hỏi, “có bao nhiêu cách bốc ra 6 vật từ 4 vật?”. Câu trả lời hợp lý là 0 cách, vì cách chọn như vậy là bất khả thi.

Vậy câu hỏi bây giờ là, tại sao định lý Lucas lại đúng?

Tôi sẽ giải thích vì sao định lý Lucas đúng cho trường hợp 25 \choose 15, với 3 là số nguyên tố cần chia. Nói cách khác, ta sẽ giải thích, một cách trực quan, lý do tại sao {25 \choose 15}={221_{3} \choose 120_{3}} có cùng số dư với {2 \choose 1}{2 \choose 2}{1 \choose 0} khi chia cho 3. Dựa trên một ví dụ cụ thể, bạn sẽ thấy rằng cách chúng ta chọn số không có gì đặc biệt: lập luận có thể dùng để tổng quát hóa với bất kỳ số nguyên không âm m,n và số nguyên tố p nào.

Trước tiên, hãy xem 25 \choose 15 thật sự cho ta biết điều gì: chỉ đơn giản cho ta cách chọn ra 15 chấm đen từ 25 chấm đen và tô chúng thành màu xanh:

Để ý rằng cách xếp chấm như trên đưa ra một gợi ý: có 2 vòng tròn gồm 9 chấm tròn, 2 vòng gồm 3 chấm tròn và 1 vòng gồm 1 chấm tròn. Nói cách khác, ta đã viết 25 dưới dạng: 25 = 2.3^{2} + 2.3^{1} +1.3^{0}=221_{3}

Ta biết rằng có 25 \choose 15 cách chọn 15 chấm và tô xanh. Nhưng rõ ràng cách tô màu sau hoàn toàn tương tự:

Ta chỉ đơn giản là quay một số đường tròn và giữ nguyên một số đường tròn khác; ta không hề thay đối số chấm màu xanh trong mỗi đường tròn, và cũng không thay đổi vị trí tương đối giữa chúng với nhau.

Vậy, giờ ta sẽ chia 25 \choose 15 cách chọn ra các chấm và tô màu thành các lớp, trong đó các cách tô màu bất biến qua phép quay sẽ thuộc về cùng một lớp, nếu không thì chúng thuộc các lớp khác nhau. Vậy 2 cách tô màu trên thuộc cùng một lớp, nhưng cách tô màu sau sẽ thuộc một lớp khác:

Giờ, ta sẽ đếm số cách tô màu trong mỗi lớp. 2 cách tô màu đầu tiên thuộc cùng một lớp, trong đó đường tròn bên trái có 9 cách quay, đường tròn bên phải có 9 cách quay. 2 đường tròn gồm 3 chấm mỗi đường tròn có 3 cách quay. Tổng kết lại ta có 9.9.3.3=729 cách tô trong lớp này, và rõ ràng là một bội số của 3.

Thực tế, ta sẽ thấy phần lớn các lớp đều chứa số cách tô màu là bội của 3. Để đếm số cách tô màu trong lớp chứa hình thứ 3, ta cần cẩn trọng hơn một chút. Quay đường tròn bên trái một khoảng bằng 1/3 đường tròn thì ta được một đường đồng nhất với đường ban đầu. Do đó số cách quay đường tròn này, thực tế, chỉ có 3 cách. Bạn có thể tư kiếm chứng rằng, dù tô màu cách nào đi nữa, thì số cách quay đường tròn luôn là ước số của số chấm tròn. Tôi sẽ bỏ qua chi tiết giải thích ở đây, bạn có thể tự tô màu và quay các đường tròn để thấy tại sao khẳng định này lại đúng.

Để ý rằng, một ước số của một lũy thừa của 3 luôn là một bội của 3 – trừ khi nó là 1. (Đây là lý do tại sao ta cần nhận xét p là một nguyên tố, cụ thể trong trường hợp này là 3). Do đó phần lớp các trường hợp, các lớp sẽ chứa số cách tô màu chỉ đơn giản là tích một số lũy thừa nào đó của 3. Ngoại lệ duy nhất, là số cách tô màu của từng đường tròn đều không nhận giá trị nào khác ngoài 1.

Vậy làm thế nào để trường hợp này xảy ra? Lấy đường tròn thứ 3 trong ví dụ thứ 3 của ta. Có duy nhất một cách quay vì toàn bộ các chấm đều màu xanh.

Dấu chấm duy nhất bên phải là một ví dụ khác. Hiển nhiên chỉ có 1 cách quay duy nhất.

Vậy nếu như mỗi đường tròn chỉ có một cách quay duy nhất thì sao? Khi đó các đường tròn của ta phải có dạng như sau:

Nếu một đường tròn hoàn toàn không được tô màu, chỉ có một cách quay. Nếu đường tròn được tô màu toàn bộ, cũng chỉ có một cách quay. Các trường hợp khác số cách quay sẽ là bội của 3. Vậy cách duy nhất để tìm một lớp có số cách tô màu không là bội của 3 là tìm các lớp có cách tô màu các đường tròn sao cho hoặc không được tô màu hoặc đường tròn đó được tô màu toàn bộ – trong những trường hợp này những đường tròn được tô màu cũng chính là phần tử của lớp đó.

Có bao nhiêu cách tô thỏa yêu cầu như vậy? Chà, ta muốn có 15 chấm được tô màu. Các chấm màu phải được lập thành các nhóm 9,3 hoặc 1. Hơn thế nữa, số nhóm của ta bị giới hạn bởi số vòng tròn sẵn có, số nhóm có 9 điểm không vượt quá 2, số nhóm 3 điểm không vượt quá 2 và số nhóm 1 điểm không vượt quá 1.ta có thể có thể tách 15 thành các nhóm lũy thừa của 3 được không?

Hiển nhiên là được rồi! Đó chính là biểu diễn của 15 trong hệ cơ số 3

15 = 1.3^{2} + 2.3^{1} +0.3^{0}=120_{3}

Vậy ta cần chọn ra 1 trong 2 đường tròn 9 điểm, 2 trong 2 đường tròn 3 điểm và 0 đường tròn trong 1 đường tròn 1 điểm. Tức là có

{2 \choose 1}{2 \choose 2}{1 \choose 0}

cách để tô màu sao cho nhóm này bất biến qua phép quay.

Nói cách khác, ta có thể chia 25 \choose 15 thành các lớp được tô màu, mỗi lớp có số cách tô chia hết cho 3 trừ {2 \choose 1}{2 \choose 2}{1 \choose 0} cách tô còn dư. Do đó

{25 \choose 15}= 3k + {2 \choose 1}{2 \choose 2}{1 \choose 0} với k là số tự nhiên nào đó.

Vậy 25 \choose 15 và {2 \choose 1}{2 \choose 2}{1 \choose 0} phải có cùng số dư khi chia cho 3.

Tổng quát hóa, ta có kết quả cần chứng minh.

Bình luận về bài viết này