Hoán vị tròn


Định nghĩa. Cho A là một tập có n phần tử(n\in\mathbb{N}) và 1\leq r\leq n là một số nguyên. Một r-hoán vị tròn của A là một cách xếp r phần tử nào đó của A lên một đường tròn, hai cách xếp được coi là như nhau nếu chúng sai khác nhau một phép quay. Một n-hoán vị tròn của A sẽ gọi đơn giản là một hoán vị tròn của A.

Số hoán vị tròn. Cho A là một tập có n phần tử(n\in\mathbb{N}) và 1\leq r\leq n là một số nguyên. Khi đó số các r-hoán vị tròn của A bằng Q_n^r=\dfrac{A_n^r}{r}. Nói riêng, số các hoán vị tròn của A bằng Q_n^n=(n-1)!.

Chứng minh. Ta sẽ dùng nguyên lý chia để chứng minh công thức này.

Nguyên lý chia. Nếu tập An phần tử được phân hoạch thành các tập hợp có k phần tử thì số khối của phân hoạch bằng \dfrac{n}{k}.

Tập các r-hoán vị tuyến tính có thể phân hoạch thành các phần nhỏ sao cho hai hoán vị tuyến tính thuộc cùng một phần nếu chúng xác định cùng một hoán vị tròn. Vì số các hoán vị tuyến tính trong mỗi phần bằng r nên số các hoán vị tròn bằng Q_n^r=\dfrac{A_n^r}{r}\Box.

Ví dụ 3.1. Có bao nhiêu cách để 5 bé trai và 3 bé gái ngồi quanh một bàn tròn nếu

a)Không có thêm điều kiện gì?

b)Bé trai T_1 và bé gái G_1 không ngồi cạnh nhau?

c)Không có bé gái nào ngồi cạnh nhau?

Đáp số. a)Q_8^8.

b)6!\times 5.

c)4!\times 5\times 4\times 3\Box.

Ví dụ 3.2. Tìm số cách xếp n cặp vợ chồng ngồi quanh một bàn tròn sao cho

a)Đàn ông và đàn bà ngồi xen kẽ nhau;

b)Mỗi người đàn bà ngồi cạnh chồng của cô ấy.

Hướng dẫn. a)Chọn chỗ cho đàn ông trước sau đó đến đàn bà, đáp số (n-1)!\times n!.

b)Coi một cặp là một người, xếp n người này, và sau đó xếp vị trí vợ-chồng, đáp số (n-1)!\times 2^n\Box.

Ví dụ 3.3. Người ta định xếp 6 cậu bé và 5 cô bé ngồi xung quanh một cái bàn. Tìm số cách xếp nếu

a)Không có thêm điều kiện gì;

b)Không có hai cô bé nào ngồi cạnh nhau;

c)Tất cả các cô bé ngồi liền nhau;

d)Cô bé G ngồi cạnh hai cậu bé T_1,T_2.

Đáp số. a)10!.

b)5!\times A_6^5.

c)6!\times 5!.

d)2\times 8!\Box.

Ví dụ 3.4. Cho n,k là các số nguyên dương. Chứng minh rằng có \dfrac{(kn)!}{n^k} cách xếp kn người ngồi xung quanh k cái bàn khác nhau sau cho mỗi bàn có n người.

Hướng dẫn. Chọn một n-hoán vị tròn xếp vào bàn 1, sau đó bàn 2,…\Box.

Test 8


Bài 1. (5 điểm)

Giải các hệ phương trình

a)\begin{cases} x^4+x^2y^2+y^4=481\\ x^2+xy+y^2=37; \end{cases}

b)\begin{cases} 3y=\dfrac{y^2+2}{x^2}\\ 3x=\dfrac{x^2+2}{y^2}. \end{cases}

Bài 2. (2 điểm)

Cho phương trình x^2+px-\dfrac{1}{2p^2}=0, ở đây p là tham số thực khác 0. Chứng minh rằng với mỗi p phương trình luôn có hai nghiệm, và nếu kí hiệu các nghiệm này là x_1,x_2 thì ta có bất đẳng thức x_1^4+x_2^4\geq 2+\sqrt{2}.

Bài 3. (3 điểm)

Cho hệ phương trình \begin{cases} x^2-4xy+y^2=a\\ y^2-3xy=4. \end{cases}

(Ẩn là x,ya là tham số)

1) Giải hệ khi a=4;

2) Tìm a để hệ có nghiệm.

Chọn đội tuyển Thổ Nhĩ Kì năm 2012


Ngày thứ nhất

Bài 1. Cho A=\{1,2,\ldots,2012\}, \: B=\{1,2,\ldots,19\}S là tập tất cả các tập con của A. Tìm số ánh xạ f : S\to B thỏa mãn f(A_1\cap A_2)=\min\{f(A_1),f(A_2)\} với mỗi A_1, A_2 \in S.

Bài 2. Cho tam giác nhọn ABC, cho D là một điểm trên cạnh BC. Gọi M_1, M_2, M_3, M_4, M_5 lần lượt là trung điểm của các đoạn thẳng AD, AB, AC, BD, CD,O_1, O_2, O_3, O_4 lần lượt là tâm của các đường tròn ngoại tiếp của các tam giác ABD, ACD, M_1M_2M_4, M_1M_3M_5,. Nếu ST là trung điểm của các đoạn AO_1AO_2, tương ứng, chứng minh rằng SO_3O_4T là một hình thang cân.

Bài 3. Với các số thực dương a, b, c thỏa mãn ab+bc+ca \leq 1, chứng minh rằng

\displaystyle a+b+c+\sqrt{3} \geq 8abc \left(\frac{1}{a^2+1}+\frac{1}{b^2+1}+\frac{1}{c^2+1}\right).

Continue reading “Chọn đội tuyển Thổ Nhĩ Kì năm 2012”