Basic counting principles


Nguyên lý thứ nhất (Quy tắc cộng). Giả sử có n_1 cách thực hiện việc E_1, n_2 cách thực hiện việc E_2,…,n_k cách thực hiện việc E_k. Nếu k việc này không thể làm đồng thời thì sẽ có n_1+n_2+\cdots+n_k cách thực hiện một trong các việc E_1,E_2,\ldots,E_k.

Ví dụ 1. Người ta có thể đi từ Hải Phòng đến Đà Nẵng bằng một trong ba phương tiện: tàu hoả, tàu thuỷ và máy bay. Nếu có hai cách đi bằng tàu hoả, ba cách đi bằng tàu thuỷ, và 1 cách đi bằng máy bay thì sẽ có 2+3+1=6 cách đi từ Hải Phòng đến Đà Nẵng. \Box

Ví dụ 2. Tìm số các cặp có thứ tự (x;y) các số nguyên thoả mãn x^2+y^2\leq 5.

Lời giải. Mỗi i=0,1,2,3,4,5 ta đặt S_i=\{(x,y)|x,y\in\mathbb{Z},x^2+y^2=i\}, khi đó tập cần tính số phần tử sẽ là hợp rời rạc của các S_i. Ta tính số phần tử của các S_i bằng phương pháp liệt kê và cuối cùng được đáp số của bài toán là 21. \Box

Nguyên lý thứ hai (Quy tắc nhân). Giả sử rằng việc E có thể được làm bằng cách thực hiện liên tiếp các việc E_1,E_2,\ldots,E_k; và có n_1 cách thực hiện việc E_1, n_2 cách thực hiện việc E_2,…,n_k cách thực hiện việc E_k. Khi đó số cách làm việc E là n_1\times n_2\times\cdots\times n_k.

Ví dụ 3. Đề đi từ thành phố A đến thành phố D người ta phải đi lần lượt qua hai thành phố B và C. Nếu có hai cách đi từ A đến $B$, ba cách đi từ B đến C và một cách đi từ C đến D thì sẽ có 2\times 3\times 1=6 cách đi từ A đến D. \Box

Ví dụ 4. Cho k và n là các số nguyên dương. Một dãy k-phân độ dài n là một dãy (a_1,a_2,\ldots,a_n) với a_1,a_2,\ldots,a_n\in\{0,1,\ldots,k-1\}. Hỏi có bao nhiêu dãy này?

Lời giải. Đặt A=\{0,1,\ldots,k-1\}. Để hình thành một dãy k-phân, đầu tiên chúng ta cần chọn a_1 từ B, sau đó chọn a_2 từ B, và cứ như thế cho đến cuối cùng cần chọn a_n từ B. Bởi vì có k cách để làm mỗi bước nên theo quy tắc nhân, số các dãy như vậy bằng k^n. \Box

Ví dụ 5. Tìm số các ước dương của 600.

Lời giải. Ta có 600=2^3\times 3^1\times 5^2 nên một số nguyên dương m là một ước dương của 600 khi và chỉ khi nó có dạng m=2^a\times 3^b\times 5^c với a,b,c là các số nguyên thoả mãn 0\leq a\leq 3,0\leq b\leq 1,0\leq c\leq 2. Như vậy số các ước dương của 600 bằng số các bộ ba (a,b,c) thoả mãn a\in\{0,1,2,3\},b\in\{0,1\},c\in\{0,1,2\}, theo quy tắc nhân, số ước dương của 600 bằng 4\times 2\times 3=24. \Box

Tổng quát hơn ta có: Nếu số nguyên dương n có phân tích tiêu chuẩn n=\prod p_i^{k_i} thì số các ước dương của n bằng \prod (k_i+1).

Ví dụ 6. Cho X=\{1,2,\ldots,100\} và

S=\{(a,b,c)\mid a,b,c\in X,a<b,a<c\}. Tính |S|.

Lời giải. Với mỗi k=1,2,\cdots,99 ta đặt S_k=\{(k,b,c)|b,c\in X, b>k,c>k\}. Khi đó S là hợp rời rạc của các S_k, mà theo quy tắc nhân ta có |S_k|=(100-k)^2 nên suy ra |S|=\sum S_k=328350\Box.

Để ý đến lời giải ví dụ thứ hai và thứ sáu, ta thấy chúng có một điểm chung là chia bài toán đã cho thành các bài toán con đơn giản hơn và giải chúng. Đây là cách cơ bản nhất để giải các bài toán đếm, có thể sẽ có cách khác ngắn gọn hơn, nhưng việc chia một bài toán thành các bài toán con mà chúng ta đã biết cách giải sẽ giúp ta ít gặp phải các sai lầm hơn.

Ví dụ 7. Có bao nhiêu số tự nhiên có ba chữ số được lấy từ tập \{1,2,3,4,5,6\} nếu

(a) Các chữ số không cần phải khác nhau?

(b) Các chữ số phải khác nhau?

(c) Các chữ số phải khác nhau và chứa số 3?

(d) Các chữ số không cần phải khác nhau và chứa số 3?

Lời giải.

(a) 6^3.

(b) 6\times 5\times 4.

(c) Đầu tiên ta chọn vị trí cho số 3, sau đó chọn hai số còn lại lần lượt. Đáp số là 3\times 5\times 4.

(d) Nếu tiếp tục làm như trên ta sẽ được kết quả là 3\times 6\times 6, đây là một kết quả không chính xác! Vì làm như vậy những số như 323 sẽ được đếm hai lần. Vấn đề ở chỗ ta đã dùng sai quy tắc nhân, mỗi hai tổ hợp khác nhau cách thực hiện các công việc E_i phải cho hai kết quả khác nhau thì ta mới áp dụng được quy tắc nhân. Bài này ta lại phải chia thành các bài toán con và giải chúng lần lượt.

Ta chia trường hợp theo vị trí của số 3 nằm bên trái nhất. Nếu số 3 này nằm ở vị trí hàng trăm thì số có ba chữ số phải có dạng \overline{3ab}, nếu nó nằm ở vị trí hàng chục thì số có ba chữ số phải có dạng \overline{a3b} với a\not=3, và cuối cùng, nếu số 3 này nằm ở vị trí hàng đơn vị thì số ba chữ số phải có dạng \overline{ab3} với a,b\not=3. Giải các bài toán con ta được đáp số của bài toán là 6\times 6+5\times 6+5\times 5. \Box

Continue reading “Basic counting principles” →

An Elementary Proof of the Gauss–Lucas Theorem


Các bạn xem lại bài sau để theo dõi cho dễ https://nttuan.org/2007/10/26/poly01/

Định lý Gauss–Lucas. Cho đa thức khác hằng P\in\mathbb{C}[z]. Chứng minh rằng mọi nghiệm phức của đạo hàm hình thức P' đều nằm trong bao lồi của tập hợp các nghiệm phức của P.

Chứng minh. Đặt n=\deg P và gọi z_1,\ldots,z_n là các nghiệm của P (kể cả bội). Khi đó

\displaystyle P(z)=c\prod_{i=1}^{n}(z-z_i),\qquad c\in\mathbb{C}\setminus\{0\}.

Lấy w\in\mathbb{C} sao cho P'(w)=0. Nếu P(w)=0 thì w thuộc tập nghiệm của P, nên hiển nhiên nằm trong bao lồi của tập này.

Xét trường hợp P(w)\ne0. Áp dụng quy tắc đạo hàm của tích rồi chia cho P(w), ta được

\displaystyle 0=\frac{P'(w)}{P(w)}=\sum_{i=1}^{n}\frac{1}{w-z_i}.

Lấy liên hợp hai vế, suy ra

\displaystyle 0=\sum_{i=1}^{n}\frac{w-z_i}{|w-z_i|^2}=w\sum_{i=1}^{n}\frac{1}{|w-z_i|^2}-\sum_{i=1}^{n}\frac{z_i}{|w-z_i|^2}.

Do đó

\displaystyle w=\sum_{i=1}^{n}\lambda_i z_i,

trong đó

\displaystyle \lambda_i=\frac{|w-z_i|^{-2}}{\sum_{j=1}^{n}|w-z_j|^{-2}}\quad(1\le i\le n).

Các hệ số \lambda_i đều dương và có tổng bằng 1. Vì vậy, w là một tổ hợp lồi của z_1,\ldots,z_n, nên nằm trong bao lồi của tập nghiệm của P. \Box

Pell’s equation II


Các bạn có thể xem phần đầu về phương trình Pell ở đây: https://nttuan.org/2007/12/15/pell-equation/

Cho d là số nguyên dương không phải là số chính phương. Xét phương trình Pell âm

\displaystyle x^2-dy^2=-1. \qquad (1)

Định lý 1. Nếu (x_1,y_1) và (x_2,y_2) là hai nghiệm nguyên dương của (1) thì

\displaystyle x_1<x_2 \Longleftrightarrow y_1<y_2 \Longleftrightarrow x_1+y_1\sqrt d<x_2+y_2\sqrt d.

Chứng minh. Từ giả thiết, ta có

\displaystyle (x_2-x_1)(x_2+x_1)=d(y_2-y_1)(y_2+y_1).

Vì x_1+x_2>0 và d(y_1+y_2)>0, hai hiệu x_2-x_1 và y_2-y_1 cùng dấu hoặc đồng thời bằng 0. Do đó tổng (x_2-x_1)+(y_2-y_1)\sqrt d cũng cùng dấu với hai hiệu ấy. Các tương đương cần chứng minh suy ra ngay. \Box

Định lý 2. Giả sử (1) có nghiệm nguyên dương và (x',y') là nghiệm có x' nhỏ nhất. Khi đó cặp (X_0,Y_0) xác định bởi

\displaystyle X_0+Y_0\sqrt d=(x'+y'\sqrt d)^2

là nghiệm cơ bản của phương trình x^2-dy^2=1, tức là nghiệm nguyên dương có hoành độ nhỏ nhất.

Chứng minh. Đặt \alpha=x'+y'\sqrt d>1. Ta có

\displaystyle \alpha^{-1}=-x'+y'\sqrt d.

Rõ ràng X_0=x'^2+dy'^2 và Y_0=2x'y' là các số nguyên dương thỏa mãn X_0^2-dY_0^2=1. Nếu đây chưa phải là nghiệm cơ bản thì tồn tại một nghiệm nguyên dương (a,b) của phương trình này sao cho

\displaystyle 1<\varepsilon=a+b\sqrt d<\alpha^2.

Đặt

\displaystyle \beta=\frac{\varepsilon}{\alpha}=(a+b\sqrt d)(-x'+y'\sqrt d)=u+v\sqrt d,

với u,v\in\mathbb Z. Khi đó

\displaystyle u^2-dv^2=-1,\qquad \alpha^{-1}<\beta<\alpha.

Do u-v\sqrt d=-\beta^{-1}, ta có v=(\beta+\beta^{-1})/(2\sqrt d)>0. Hơn nữa, u\ne0, vì u=0 sẽ dẫn đến dv^2=1, trái với d\ge2. Vì vậy (|u|,v) là một nghiệm nguyên dương của (1), nhưng

\displaystyle |u|+v\sqrt d=\max\{\beta,\beta^{-1}\}<\alpha=x'+y'\sqrt d.

Theo Định lý 1, điều này mâu thuẫn với tính nhỏ nhất của x'. Vậy (X_0,Y_0) là nghiệm cơ bản của phương trình x^2-dy^2=1. \Box

Định lý 3. Giả sử (1) có nghiệm nguyên dương và (x',y') là nghiệm có x' nhỏ nhất. Khi đó tất cả các nghiệm nguyên dương của (1) là (x_n,y_n), với

\displaystyle x_n+y_n\sqrt d=(x'+y'\sqrt d)^{2n+1},\qquad n=0,1,2,\ldots.

Cặp (x',y') được gọi là nghiệm cơ bản của phương trình Pell âm (1).

Chứng minh. Đặt \alpha=x'+y'\sqrt d. Với mỗi n\ge0, khai triển nhị thức cho thấy x_n,y_n là các số nguyên dương. Đồng thời,

\displaystyle x_n^2-dy_n^2=(x'^2-dy'^2)^{2n+1}=-1.

Ngược lại, cho (a,b) là một nghiệm nguyên dương bất kỳ của (1). Theo Định lý 1, a+b\sqrt d\ge\alpha. Vì \alpha>1, tồn tại số nguyên n\ge0 sao cho

\displaystyle \alpha^{2n+1}\le a+b\sqrt d<\alpha^{2n+3}.

Đặt

\displaystyle \gamma=\frac{a+b\sqrt d}{\alpha^{2n+1}}=u+v\sqrt d.

Vì \alpha^{-1}=-x'+y'\sqrt d, ta có u,v\in\mathbb Z. Hơn nữa,

\displaystyle u^2-dv^2=1,\qquad 1\le\gamma<\alpha^2.

Nếu \gamma>1 thì u-v\sqrt d=\gamma^{-1}, nên

\displaystyle u=\frac{\gamma+\gamma^{-1}}2>0,\qquad v=\frac{\gamma-\gamma^{-1}}{2\sqrt d}>0.

Khi đó (u,v) là một nghiệm nguyên dương của phương trình x^2-dy^2=1 với u+v\sqrt d<\alpha^2, trái với Định lý 2. Vậy \gamma=1, tức là a+b\sqrt d=\alpha^{2n+1}. Do \sqrt d vô tỉ, suy ra (a,b)=(x_n,y_n). \Box

Nhận xét. Phương trình Pell âm có thể vô nghiệm nguyên. Chẳng hạn, x^2-3y^2=-1 vô nghiệm, vì khi lấy modulo 3 ta được x^2\equiv2\pmod3, điều không thể xảy ra.

Existence of Non-Trivial Solutions in Homogeneous Linear Systems


Định lý. Cho hai số nguyên dương N>M và một bảng các số thực (phức, hữu tỷ) (a_{i,j}) có cỡ M\times N. Khi đó, hệ phương trình

\displaystyle \sum_{j=1}^Na_{i,j}x_j=0,\quad i=1,2,\ldots,M

luôn có nghiệm thực (tương ứng phức, hữu tỷ) không tầm thường.

Chứng minh. Ta chứng minh đồng thời cho các hệ có hệ số trong mỗi trường \mathbb K\in\{\mathbb Q,\mathbb R,\mathbb C\} bằng quy nạp theo số phương trình M.

Với M=1, ta có N\ge2. Nếu mọi hệ số a_{1,j} đều bằng 0 thì có thể lấy (x_1,\ldots,x_N)=(1,0,\ldots,0). Nếu không, chọn k sao cho a_{1,k}\ne0 và chọn \ell\ne k. Đặt

\displaystyle x_\ell=1,\qquad x_k=-\frac{a_{1,\ell}}{a_{1,k}},\qquad x_j=0\quad(j\notin\{k,\ell\}).

Đây là một nghiệm không tầm thường.

Giả sử kết luận đúng với mọi hệ gồm M-1 phương trình và có số ẩn lớn hơn M-1. Xét hệ gồm M phương trình với N>M. Nếu phương trình thứ M có mọi hệ số bằng 0, bỏ phương trình ấy rồi áp dụng giả thiết quy nạp.

Trong trường hợp còn lại, bằng cách đổi thứ tự các ẩn, ta có thể giả sử a_{M,N}\ne0. Từ phương trình thứ M, suy ra

\displaystyle x_N=-\sum_{j=1}^{N-1}\frac{a_{M,j}}{a_{M,N}}x_j.

Thay vào M-1 phương trình đầu, ta được hệ thuần nhất

\displaystyle \sum_{j=1}^{N-1} \left(a_{i,j}-\frac{a_{i,N}a_{M,j}}{a_{M,N}}\right)x_j=0, \qquad i=1,\ldots,M-1.

Hệ này có N-1>M-1 ẩn và các hệ số vẫn thuộc \mathbb K. Theo giả thiết quy nạp, nó có nghiệm (x_1,\ldots,x_{N-1}) không tầm thường. Xác định x_N bằng công thức trên, ta thu được một nghiệm của hệ ban đầu. Nghiệm này không tầm thường vì ít nhất một trong các số x_1,\ldots,x_{N-1} khác 0.

Vậy kết luận đúng với mọi M<n. \Box

Đây là một kết quả hữu ích khác về hệ phương trình tuyến tính nhiều ẩn https://nttuan.org/2007/10/21/siegel/