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

[phong than]

Tìm tất cả các số nguyên dương $n$ sao cho tập $1,2, . . . ,3n$ có thể phân hoạch thành $n$ tập mà mỗi tập gồm 3 phần tử trong đó 1 số bằng tổng 2 số kia.

Bài viết đã được chỉnh sửa nội dung bởi phong than: 28-06-2009 - 15:10

[phong than]

Không ai giúp em à. Đây là đề thi TST Phú Thọ đấy.

[phong than]

Một lời giải ở đây.

Bài viết đã được chỉnh sửa nội dung bởi phong than: 22-07-2009 - 10:01

[KhùngLãoQuái]

Quả thật anh văn mình hơi kém nên không hiểu được lời giải đó . Bạn Trung nếu hiểu được lời giải này thì vui lòng post bản tiếng Việt lên cho anh em tham khảo nhé .

[phong than]

Mình thuộc dạng mid đặc tiếng anh, nhưng bạn nói thể thì mình cũng :
Trước hết ta chứng minh bổ đề:
Cho $n$ là một số nguyên dương dạng $4k,4k+1$. Chứng minh rằng ta có thể sắp xếp được tập
$1,1,2,2, . . . ,n,n$ thành một dãy sao cho giữa 2 số $k$ có đúng $k-1$ số.
Ta sẽ chứng minh bổ đề này bằng quy nạp với $n=4k$.
Đặt $A_1=11,B_1=423243$ là các dãy kí tự số.$A_n,B_n$ được xác định bởi các công thức:
$A_{k+1}=B_k$,
$B_{k+1}=(4k+4)(4k+2)(4k+3)(4k+1)A_k(4k+2)(4k+1)(4k+4)(4k+3)$.
Như vậy ta dễ dàng kiểm tra rằng dãy $A_kB_k$ thỏa mãn điều kiện.
Bây giờ ta sẽ chứng minh với $n=4k+1$.
Dãy số kí tự $B_k^'$ được xác định bằng cách thay các số $4k$ của $B_k$ bằng số $4k+1$ và thêm vào vị trí giữa số đầu tiên và số thứ $2$ số $4k$. Khi đó ta nhận được dãy $(4k)A_kB_k'$
Tóm lại bổ đề được chứng minh.
Trở lại bài toán.
Trước hết ta dễ thấy rằng điều kiện cần là $n=4k, 4k+1$.
Điều kiện đủ:
Theo bổ đề ta có dãy $a_1,a_2, . . . ,a_{2n}$, trong đó mỗi số $k$ xuẩt hiện 2 lần và giữa hai số này có đúng $k$ số.
Giả sử hai số $a_{\sigma(i)},a_{\sigma(i)'}$ là hai vị trí của số $i$ trong dãu trên .
Ta có phân hoạch sau:
$ \{ 1,\sigma(1)+n,\sigma'(1)+n \} , \{ 2,\sigma(2)+n,\sigma'(2)+n \} ; ...;\{ n,\sigma(n)+n,\sigma'(n)+n \} $.

Bài viết đã được chỉnh sửa nội dung bởi mai quoc thang: 23-07-2009 - 11:53