Chủ đề này có 4 trả lời

[supermember]

Cho trước số nguyên dương $ n \ge 2$

Tính số bộ $2n-2$ số nguyên $\left ( x_1 ; x_2;...; x_{2n-2} \right )$ thoả mãn $3$ điều kiện:

1/ $x_i \in \left \{ -1; 1 \right \} \ \ \forall i = 1;2 ;...; 2n-2$
2/ $x_1+x_2+...+x_i \ge 0 \ \ \forall i = 1;2;...; 2n-2$
3/ $x_1+x_2+...+x_{2n-2}=0$

Bài viết đã được chỉnh sửa nội dung bởi supermember: 02-04-2012 - 09:29

[tanlsth]

Anh xin góp vui chút
Để giải quyết bài toán này ta sẽ chuyển về dạng tọa độ trong mặt phẳng cho dễ thấy
Ta cũng thay $2n-2$ bằng $2n$ cho dễ viết
Đặt $ s_m=x_1+x_2+...+x_m$ với $m=1,2,..,2n$
Xét trong mặt phẳng tọa độ các điểm $(m,s_m)$, xuất phát từ điểm $(0,0)$ và nối các điểm này lại ta sẽ được 1 đường gấp khúc
Để thỏa mãn điều kiện đề bài thì các đường này phải không cắt đường thẳng $y=-1$
Nhận thấy $s_1=1$, từ $(1,s_1)$ đi đến $(2n,s_{2n})$ (ở đây $s_{2n}=0$) có tất cả $C_{2n-1}^{n}$ cách và ta cần loại các cách đi cắt đường $y=-1$. Xét điểm $(1,-3)$ và tất cả các cách đi từ điểm này tới $(2n,s_{2n})$.Nhận thấy có tất cả $C_{2n-1}^{n-2}$ cách và dễ dàng nhận thấy mỗi cách đi sẽ đều cắt đường thẳng $y=-1$
Với mỗi cách đó xét giao điểm đầu tiên của nó với đường thẳng $y=-1$ và gọi nó là $A$. Lấy đối xứng phần từ $(1,-3)$ tới $A$ qua đường thẳng $y=-1$ ta sẽ ra 1 cách đi từ $(1,s_1)$ đến $(2n,s_{2n})$ mà cắt đường thẳng $y=-1$
Nhận thấy phép lấy đối xứng này là 1 phép song ánh, do đó kết quả ta cần tìm là $C_{2n-1}^{n}-C_{2n-1}^{n-2}$ bộ

[Peter Pan]

Cũng xét bài toán với $2n$. Ta có: số số $1$ luôn nhiều hơn số số $-1$ trong mọi dãy $s_i$. Do đó số đường đi này là một song ánh với số dãy 1-trội chứa $n+1$ số 1 và $n$ số -1. Vì dãy 1- trội này bắt đầu từ 1 nên ta có thể bỏ số 1 ở đầu là được dãy là được dãy $s_i$, và ngược lại nếu có dãy $s_i$ thì ta chỉ cần thêm số 1 vào đầu là được ngay một dãy 1- trội. Do đó theo bổ đề xích. thì sẽ có đúng 1 dãy 1-trội. số dãy 1 trội này bằng
$\frac{C^n_{2n+1}}{2n+1}=\frac{C^n_{2n}}{n+1}$
P/s: ĐS khác anh Tân

Bài viết đã được chỉnh sửa nội dung bởi winwave1995: 03-04-2012 - 22:38

[tanlsth]

Đáp số như nhau cả đó em, khai triển cái biểu thức của anh là ra kết quả giống của em

[Karl Heinrich Marx]

Cho trước số nguyên dương $ n \ge 2$

Tính số bộ $2n-2$ số nguyên $\left ( x_1 ; x_2;...; x_{2n-2} \right )$ thoả mãn $3$ điều kiện:

1/ $x_i \in \left \{ -1; 1 \right \} \ \ \forall i = 1;2 ;...; 2n-2$
2/ $x_1+x_2+...+x_i \ge 0 \ \ \forall i = 1;2;...; 2n-2$
3/ $x_1+x_2+...+x_{2n-2}=0$

Số cách chọn ra 1 bộ $n$ số 1 và $n$ số -1 là $C_{2n}^{n}$. Xét 1 bộ 2n số sao cho tồn tại $i$ để $x_1+x_2+...+x_i<0$ với $i$ nhỏ nhất, khi đó đổi dấu tất cả những số đứng sau $x_i$ trong bộ này
ta được một bộ gồm $n+1$ số -1. Và với mỗi bộ gồm $n+1$ số -1 bằng cách xác định trên ta cũng chỉ ra 1 bộ không thỏa đề bài. Đây là song ánh. Do đó đáp số là $C_{2n}^{n}-C_{2n}^{n+1}$
Bài toán này liên quan đến một trong số những cách xác định số Catalan. Tức là số đường đi từ điểm $(0;0)$ đến điểm $(n;n)$ mà không vượt lên đường thẳng $y=x$. Ta có thể xây dựng song ánh đường đi này tương ứng với nếu $x_i=1$ thì ta đi sang phải 1 bước còn nếu $x_=-1$ thì ta đi lên trên.