Đến nội dung

Hình ảnh

Chia thành hai nhóm có tổng các số trong nhóm bằng nhau

- - - - - tổ hợp

  • Please log in to reply
Chủ đề này có 9 trả lời

#1
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

Người ta viết lên bảng một số số thuộc tập $n$ số nguyên dương đầu tiên sao cho mỗi số thuộc tập này được viết ít nhất một lần và tổng tất cả các số đã viết lên bảng là một số chẵn. Chứng minh rằng có thể chia các số trên bảng thành hai nhóm có tổng tất cả các số trong mỗi nhóm bằng nhau.


  • LNH yêu thích

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#2
QDV

QDV

    Trung sĩ

  • Thành viên
  • 131 Bài viết

Ta chia các số này thành hai tập hợp A và B. Đặt (A),(B) là tổng các phần tử thuộc tập A,B.Đầu tiên lấy tất cả các tập hợp C={1,2,...,N} chia sen kẻ lần lượt cho A,B.Dễ thấy lúc này (A)-(B)<n ( Giả sử (A)>(B)).Còn các phần tử còn lại ta chia theo nguyên tắc : chia cho tập hợp có tổng nhỏ hơn cho đến khi không còn phần tử nào. Với cách chia này dễ thấy (A)-(B)=2t<n ( t thuộc C).Nếu phần tử t thuộc (A) đưa t sang (B) bài toán được giải quyết. Nếu phần tử t thuộc (B) vậy phần tử t-1và t+1 thuộc (A), chuyển t sang A chuyển t-1 và t+1 sang (B) bài toán được giải quyết



#3
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

Mình không hiểu lời giải của bạn lắm. Bài toán mình đọc có thấy rằng là phải chọn trước các số từ $\{ 1,2, \cdots , n \}$ rồi mới thực hiện chia các số thành hai nhóm. Còn trong lời giải của bạn theo mình hiểu thì bạn đang chia tập $\{ 1,2, \cdots , n \}$ thành hai nhóm bằng nhau chăng ?


Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#4
QDV

QDV

    Trung sĩ

  • Thành viên
  • 131 Bài viết

Theo đề bài tập hợp đã cho gồm các số thuộc C={1,2,...,n} được lâp laị ít nhất một lần điều này có nghĩa là có ít nhất một tập hợp C và các phần tử thuộc C(các phần tử này có thể nhiều hơn n phần tử nhưng không đủ n giá trị từ 1 đến n )



#5
khanghaxuan

khanghaxuan

    Trung úy

  • Thành viên
  • 969 Bài viết

Mình không hiểu lời giải của bạn lắm. Bài toán mình đọc có thấy rằng là phải chọn trước các số từ $\{ 1,2, \cdots , n \}$ rồi mới thực hiện chia các số thành hai nhóm. Còn trong lời giải của bạn theo mình hiểu thì bạn đang chia tập $\{ 1,2, \cdots , n \}$ thành hai nhóm bằng nhau chăng ?

Bạn có tài liệu gì về phần chia tập hợp này không :) . Chứ phần này khó quá :P


Điều tôi muốn biết trước tiên không phải là bạn đã thất bại ra sao mà là bạn đã chấp nhận nó như thế nào .

- A.Lincoln -

#6
QDV

QDV

    Trung sĩ

  • Thành viên
  • 131 Bài viết

Gọi Q là tập hợp tất cả các số đã viết.Theo đề bài C={1,2,...,n} là tập con của Q.Thực hiện phép chia như sau

A={x\x=2k+1$\leq n$}

B={x\x=2k$\leq n$}

Gọi (Q),(A),(B) lần lượt là tổng của tất cả các phần tử cuả các tập hợp Q,A,B.Dễ thấy

$\left | \left ( A \right )-\left ( B \right ) \right |< n$

Bây giờ các phần tử còn lại của Q được chia theo nguyên tắc cứ thêm lần lượt từng phần tử vaò A hoặc B nếu tập hợp nào có tổng các phần tử nhỏ hơn cho đến khi Q không còn phần tử nào.Lúc này ta được hai tập hợp $A_{1},B_{1}$

Vì $\left ( A_{1} \right )+\left ( B_{1} \right )=\left ( Q \right )$ chẳn

Nên $\left ( A_{1} \right )-\left ( B_{1} \right ) =2t<n (không mất tính tổng quát gỉa sử ( A_{1} \right )>\left ( B_{1} \right ))

Nếu phần tử t thuộc (A) đưa t sang (B) bài toán được giải quyết. Nếu phần tử t thuộc (B) vậy phần tử t-1và t+1 thuộc (A), chuyển t sang A chuyển t-1 và t+1 sang (B) bài toán được giải quyết



#7
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

Mình có đọc lại đề, quả đúng là đề bài yêu cầu như bạn nói.  :wub: Lời giải của bạn rất hay. :)

 

Bạn có tài liệu gì về phần chia tập hợp này không :) . Chứ phần này khó quá :P

Quả là khó tìm được một tài liệu nào nói về phần chia tập hợp này.  :(


Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#8
QDV

QDV

    Trung sĩ

  • Thành viên
  • 131 Bài viết

Quả thực mình cũng chưa đọc tài liệu nào nói về phương pháp giải quyết vấn đề này.Đây chỉ là kinh nghiệm bản thân,nếu có thời gian và đủ nguồn bài tâp có lẽ mình sẽ viết kỹ về chuyên đề này.Bây giờ mình xin nói sơ về dạng toán này và nguyên lý giải quyết.

DẠNG TOÁN: Cho dữ kiện A,thực hiện một số thao tác,chứng minh sự kiện B

NGUYÊN LÝ:

1) Dữ kiện A ta xem như một tập A thuộc trường X (có tính bất biến nào đó).Ví dụ bài trên luôn chứa tập C={1,2,...,n}

2) Mỗi thao tác thực hiện ta thu được tập hợp B thuộc trường Y (có tính bất biến nào đó).Ví dụ bài trên luôn chứa tập C,D sao cho $\left | \left ( C \right ) \right -\left ( D \right )|< n$ Từ đây dễ dàng CM được sự kiện B

Vắn đề nằm ở chỗ nếu cho cụ thể từng thao tác một thì đơn giản hơn. Nếu thao tác cho là kết quả cuối cùng ta cần lựa chọn từng bước thao tác để thỏa được tập hợp B thuộc trường Y (có tính bất biến nào đó)

 Bài viết mang tính chủ quan và còn thiếu sót do thiếu nguồn tư liệu kiểm chứng, mong bạn thông cảm



#9
cachuoi

cachuoi

    Trung sĩ

  • Thành viên
  • 117 Bài viết

 mình từng gặp 1 bài như sau , cho tập{ a1 ;a2 .....;an} mà a1=1 và a_i <=a_i+1 <= 2a_i  tổng các a_i là số chẵn cmr có thể chia thành 2 tập sao cho tổng các phần tử của mỗi tập bằng nhau


Bài viết đã được chỉnh sửa nội dung bởi cachuoi: 07-10-2015 - 19:32

  • QDV yêu thích

#10
QDV

QDV

    Trung sĩ

  • Thành viên
  • 131 Bài viết

 mình từng gặp 1 bài như sau , cho tập{ a1 ;a2 .....;an} mà a1=1 và a_i <=a_i+1 <= 2a_i  tổng các a_i là số chẵn cmr có thể chia thành 2 tập sao cho tổng các phần tử của mỗi tập bằng nhau

Thực hiện phép chia thành hai nhóm A và B như sau:

1. Chia các phần tử theo thứ tự giảm dần

2. Chia $a_{i}$ vào A hoặc B nếu nhóm nào có tổng các phần tử không lớn hơn tổng các phần tử của nhóm kia

 Gọi (A),(B) là tổng các phần tử của nhóm A và nhóm B. Ta CMR ở lượt chia thứ n-i +1 tức chia phần tử $a_{i}$ thì

$\left | (A_{i})-(B_{i}) \right |\leq a_{i}$ (ở đây ta ký hiệu $(X_{i})$ là tổng các phần tử của nhóm X sau khi chia phần tử $a_{i}$)

CM bằng quy nạp

 Ở lần chia thứ 1 (chia phần tử $a_{n}$).Dễ thấy

$\left | (A_{n})-(B_{n}) \right |=a_{n}\leq a_{n}$

 Giả sử BĐT đúng đến  lần chia thứ n-k+1 (chia phần tử $a_{k}$ ).Tức là

$\left | (A_{k})-(B_{k}) \right |\leq a_{k}$

 Ta cần CM BĐT đúng đến lần chia thứ n-k+2 ( chia phần tử $a_{k-1}$).Tức là

$\left | (A_{k-1})-(B_{k-1}) \right |\leq a_{k-1}$

 Thực vậy

$\left | (A_{k-1})-(B_{k-1}) \right |=\left | (A_{k})-(B_{k})) \right |-a_{k-1}\leq a_{k}-a_{k-1}\leq a_{k-1}$ ( theo giả thiết quy nạp và điều kiện bài toán) (Đpcm)

 Vậy ở lần chia thứ n ( chia phần tử $a_{1}$). Ta được

$\left | (A_{1})-(B_{1}) \right |\leq a_{1}=1$

Vì tổng các phần tử chẳn nên hiệu I(A)-(B)I cũng là số chẳn $\Rightarrow \left | (A_{1})-(B_{1}) \right |=0$ (đpcm)


Bài viết đã được chỉnh sửa nội dung bởi QDV: 08-10-2015 - 08:53






Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: tổ hợp

1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh