Permutations

Cho $n$ là một số nguyên dương, $r$ là một số nguyên thoả mãn $0\leq r\leq n$ và $A$ là một tập hợp có $n$ phần tử. Một $r-$ hoán vị của $A$ (hay một chỉnh hợp chập $r$ của $A$ ) là một cách xếp $r$ phần tử nào đó của $A$ thành một hàng. Một $n-$ hoán vị của $A$ sẽ được gọi là một hoán vị của $A.$

Ví dụ 1. Cho tập $A=\{a,b,c,d\}$ . Khi đó các $3-$ hoán vị của $A$ là (có tất cả $24$ ):

$abc,acb,bac,bca,cab,cba,$

$abd,adb,bad,bda,dab,dba,$

$acd,adc,cad,cda,dac,dca,$

$bcd,bdc,cbd,cdb,dbc,dcb.$ $\Box$

Định lí 1. Cho $n$ là một số nguyên dương, $r$ là một số nguyên thoả mãn $0\leq r\leq n$ và $A$ là một tập hợp có $n$ phần tử. Khi đó số $r-$ hoán vị của $A$ bằng $A_n^r=\dfrac{n!}{(n-r)!}$ . Nói riêng, số hoán vị của $A$ bằng $P_n=n!$ .

Chứng minh. Một $r-$ hoán vị của $A$ sẽ được hình thành sau $r$ bước: Đầu tiên, chọn một phần tử từ $A$ và đặt nó vào vị trí thứ nhất; sau đó ta chọn trong các phần tử còn lại của $A$ một phần và đặt nó vào vị trí thứ hai;…; và cuối cùng ta chọn một phần tử từ $n-r+1$ phần tử còn lại của $A$ và đặt nó vào vị trí thứ $r$ . Vì có $n$ cách làm bước thứ nhất, $n-1$ cách làm bước thứ hai;…; và $n-r+1$ cách làm bước thứ $r$ nên theo quy tắc nhân, ta có $A_n^r=n(n-1)\cdots (n-r+1)=\dfrac{n!}{(n-r)!}.$ $\Box$

Ví dụ 2. Gọi $E$ là tập tất cả $26$ chữ cái tiếng Anh. Tìm số các từ gồm $5$ chữ trong $E$ sao cho chữ đầu tiên, chữ cuối cùng là các nguyên âm phân biệt và ba chữ còn lại là các phụ âm phân biệt.

Lời giải. Có $5$ nguyên âm trong $E$ đó là $a,e,i,o,u$ và $21$ chữ cái còn lại là các phụ âm. Một từ thỏa mãn yêu cầu của đầu bài sẽ được hình thành sau hai bước: Đầu tiên, chọn một $2-$ hoán vị của $\{a,e,i,o,u\}$ và đặt nguyên âm thứ nhất vào vị trí $1$ , nguyên âm thứ hai vào vị trí $5$ , sau đó chọn một $3-$ hoán vị của $E\setminus \{a,e,i,o,u\}$ và đặt phụ âm thứ nhất, hai, ba của hoán vị vào vị trí $2,3,4$ tương ứng.

Bởi vì có $A_5^2$ cách để làm bước thứ nhất và $A_{21}^3$ cách để làm bước thứ hai nên theo quy tắc nhân ta có số các từ thoả mãn là $A_5^2\times A_{21}^3=159600.$ $\Box$

Continue reading →

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?

(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$ .

(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 →

Asian Pacific Mathematics Olympiad 2009

Bài 1. Xét phép toán sau trên các số thực dương được viết trên bảng: Chọn một số $r$ được viết trên bảng, xóa số đó, và sau đó viết một cặp số thực dương $a$ và $b$ thỏa mãn điều kiện $2r^2=ab$ lên bảng. Giả sử ban đầu bạn chỉ có một số thực dương trên bảng, và thực hiện phép toán này $k^2-1$ lần để cuối cùng thu được $k^2$ số thực dương, không nhất thiết phân biệt. Chứng minh rằng tồn tại một số trên bảng không vượt quá $kr$ .

Bài 2. Cho $a_1, a_2, a_3, a_4, a_5$ là các số thực thỏa mãn $\frac{a_1}{k^2+1} + \frac{a_2}{k^2+2} + \frac{a_3}{k^2+3} + \frac{a_4}{k^2+4} + \frac{a_5}{k^2+5} = \frac{1}{k^2}$ với $k=1,2,3,4,5$ . Tìm giá trị của $\frac{a_1}{37} + \frac{a_2}{38} + \frac{a_3}{39} + \frac{a_4}{40} + \frac{a_5}{41}$ (Biểu diễn giá trị dưới dạng một phân số duy nhất.)

Bài 3. Cho ba đường tròn $\Gamma_1, \Gamma_2, \Gamma_3$ không giao nhau và rời nhau từng đôi một trên mặt phẳng. Với mỗi điểm $P$ trên mặt phẳng, nằm ngoài ba đường tròn, dựng sáu điểm $A_1, B_1, A_2, B_2, A_3, B_3$ như sau: Với mỗi $i=1,2,3$ , $A_i, B_i$ là các điểm phân biệt trên đường tròn $\Gamma_i$ sao cho các đường thẳng $PA_i$ và $PB_i$ đều là tiếp tuyến của $\Gamma_i$ . Gọi điểm $P$ là điểm ngoại lệ nếu, từ cách dựng trên, ba đường thẳng $A_1B_1, A_2B_2, A_3B_3$ đồng quy. Chứng minh rằng mọi điểm ngoại lệ trên mặt phẳng, nếu tồn tại, đều nằm trên cùng một đường tròn.

Bài 4. Chứng minh rằng với mọi số nguyên dương $k$ , tồn tại một cấp số cộng $\frac{a_1}{b_1}$ , $\frac{a_2}{b_2}$ , $\dots$ , $\frac{a_k}{b_k}$ gồm các số hữu tỉ, trong đó $a_i, b_i$ là các số nguyên dương nguyên tố cùng nhau với mỗi $i=1,2,\dots,k$ , sao cho các số nguyên dương $a_1, b_1, a_2, b_2, \dots, a_k, b_k$ đều phân biệt.

Bài 5. Larry và Rob là hai robot đi cùng một chiếc xe từ Argovia đến Zillis. Cả hai robot đều có quyền điều khiển vô lăng và rẽ theo thuật toán sau: Larry rẽ trái $90^\circ$ sau mỗi $l$ kilômét lái xe tính từ điểm xuất phát; Rob rẽ phải $90^\circ$ sau mỗi $r$ kilômét lái xe tính từ điểm xuất phát, trong đó $l$ và $r$ là các số nguyên dương nguyên tố cùng nhau. Trong trường hợp cả hai lượt rẽ xảy ra đồng thời, xe sẽ tiếp tục đi thẳng mà không chuyển hướng. Giả sử mặt đất bằng phẳng và xe có thể di chuyển theo bất kỳ hướng nào. Giả sử xe xuất phát từ Argovia và hướng về phía Zillis. Với những lựa chọn nào của cặp $(l, r)$ thì xe được đảm bảo sẽ đến Zillis, bất kể khoảng cách từ Argovia là bao xa?

T-Quiz 1

Gửi các bạn học sinh lớp 8 và lớp 9.

T.quiz001 Download

Polynomials in one variable: Basic definitions

Trong bài này $K$ là một trong các tập hợp $\mathbb{F}_p$ (tập các số nguyên modulo một số nguyên tố $p$ ), $\mathbb{Q}$ , $\mathbb{R},$ hoặc $\mathbb{C}$ .

Định nghĩa 1. Cho $n$ là một số tự nhiên và $a_0,a_1,...,a_n \in K$ . Mỗi tổng hình thức có dạng

$a_n x^n+a_{n-1} x^{n-1}+\ldots+a_1 x+a_0$

được gọi là một đa thức trên $K$ theo biến $x$ với hệ số $a_0,a_1,...,a_n$ . Nếu $k$ là chỉ số lớn nhất sao cho $a_k \neq 0$ , thì ta nói đa thức $f(x)=a_k x^k+\ldots+a_1x+a_0$ có bậc $k$ , viết $\text{deg}(f(x))=k$ , $a_k$ được gọi là hệ số đầu của đa thức $f(x)$ , và $a_0$ được gọi là hệ số tự do của $f(x)$ . Nếu $a_0$ là hệ số đầu của $f(x)$ , thì $f(x)$ được gọi là đa thức hằng.

Nếu hệ số đầu của $f(x)$ là $1$ , thì $f(x)$ được gọi là đa thức monic. Tập tất cả đa thức với hệ số trong $K$ được ký hiệu bởi $K[x]$ .

Theo định nghĩa này thì đa thức không, đa thức mà mọi hệ số là không, không có bậc. Để thuận tiện, ta qui ước nó là đa thức hằng và có bậc bằng $-\infty$ . Một đa thức hằng $f(x)=a_0$ có bậc $0$ nếu $a_0 \neq 0$ . Hai đa thức bằng nhau nếu chúng có cùng bậc và tất cả các hệ số tương ứng bằng nhau. Cần phân biệt giữa đa thức $f(x)$ và hàm đa thức tương ứng từ $K$ đến $K$ xác định bởi thay một phần tử của $K$ vào vị trí của $x$ . Nếu $f(x)=a_m x^m+\ldots+a_1x+a_0$ và $c \in K$ , thì $f(c)=a_m c^m+\ldots+a_1c+a_0$ được gọi là giá trị của $f(x)$ tại $c$ . Nếu $K$ là $\mathbb{F}_p$ thì có thể có hai đa thức khác nhau xác định cùng một hàm đa thức.

Ví dụ 1. Cho $K$ là $\mathbb{F}_3$ và xét các đa thức $x^3$ và $x$ . Với mỗi $c \in \mathbb{F}_3$ , ta có $c^3 \equiv c\pmod{3},$ do đó các hàm đa thức $f(x)=x^3$ và $g(x)=x$ là bằng nhau như các hàm từ $\mathbb{F}_3$ tới $\mathbb{F}_3$ .