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

[chardhdmovies]

Cho $20$ số nguyên dương $x_1,x_2,...,x_{20}$ với $x_1<x_2<...<x_{20}$.Kí hiệu $X=\left \{ x_1,x_2,...,x_{20} \right \}$

Chứng minh rằng tồn tại hai tập con $A,B$ của $X$ có dạng $A=\left \{ a_1,a_2,...,a_k \right \},B=\left \{ b_1,b_2,...,b_k \right \}$ với $0<k<8$ thỏa mãn $3$ điều kiện sau

$i)$ $A\cap B=\varnothing$

$ii)$ $x_i,x_{i+1}$ không cùng thuộc $1$ tập hợp với $i=\overline{1,19}$

$iii)$ $\left | \sum_{i=1}^{k}\frac{1}{a_i}-\sum_{i=1}^{k}\frac{1}{b_i} \right |<\frac{2}{3431}$

 

NTP

[Bui Ba Anh]

Bổ đề: Cho trước tập $20$ số tự nhiên :${1,2,3,..,20}$. Khi đó số cách chọn tập gồm $7$ phần tử sao cho không có hai phần tử liên tiếp trong tập trên được chọn là $C_{14}^7$

Thật vậy, gọi $7$ số đó là $x_1<x_2<..<x_7$. Từ giả thiết suy ra:$20\geq x_7\geq x_6+2\geq...\geq x_1+12\geq 13$. Đặt:

$x_7=a_7+13,x_6=a_6+11,..,x_1=a_1+1$(và khi đó thì $a_i \geq 0$)

Do $13\leq x_1+12\leq...\leq x_7\leq 20=>0\leq a_1\leq a_2\leq ...\leq a_7 \leq 7$ nên $a_i$ nhận $8$ giá trị

Như vậy, để đếm các bộ $7$ số thỏa bổ đề thì ta sẽ đếm các bộ $7$ số $a_i$. Tuy nhiên cách sắp xếp $x_1<x_2<..<x_7$ chỉ nhằm mục đích xác định giá trị của $a_i$ chứ không đếm theo bộ thứ tự, do đó ta cũng sẽ không đếm theo bộ thứ tự $a_i$ và như vậy nó tương ứng với Tổ hợp lặp(thay vì chỉnh hợp lặp) chập $8$ của $7$ phần tử, là $C_{14}^7=3432$ cách chọn

Trở lại bài toán:

Do tương ứng chỉ số các phần tử trong dãy với bộ ${1,2,...20}$ nên hai phần tử liên tiếp tương ứng với $2$ số liên tiếp trong khoảng trên

Xét $k=7$. Số tập $7$ phần tử thỏa $ii)$ là $3432$ tập

Tổng các nghịch đảo các phần tử trong tập này không quá $1+\frac{1}{3}+\frac{1}{5}+..+\frac{1}{13}<2$

Xét $3431$ khoảng:

$[\frac{0}{3231};\frac{2}{3432}),[\frac{2}{3431};\frac{4}{3431}),...,[\frac{6860}{3431};\frac{6862}{3431}=2)$

Do tổng các nghịch đảo các phần tử trong tập này không quá $2$ nên chúng sẽ thuộc vào một trong $3431$ khoảng này.

Tuy nhiên có $3432$ tập có $7$ phần tử thỏa $ii)$ nên tồn tại $2$ tập chung một khoảng

Khi đó hai tập này có chung số phần tử, hiệu của chúng có độ lớn $<\frac{2}{3431}$, các tập không có các phần tử liên tiếp trong dãy, và như thế chỉ cần loại đi cùng những phần tử chung của hai tập này, ta được hai tập còn lại thỏa mãn tất cả yêu cầu bài toán.

Bài viết đã được chỉnh sửa nội dung bởi Bui Ba Anh: 20-05-2015 - 23:39