Đến nội dung

Hình ảnh

Sắp xếp 4 người trên bàn tròn

- - - - -

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

#1
PSW

PSW

    Những bài toán trong tuần

  • Quản trị
  • 493 Bài viết
Trong $1$ lớp học có $2n$ học sinh ( $n \ge 2$) ; mỗi học sinh chơi thân với ít nhất $n$ bạn .

Chứng minh rằng ta có thể chọn ra $4$ học sinh để tổ chức học nhóm trên $1$ bàn tròn . Sao cho mỗi học sinh đều ngồi giữa $2$ người bạn thân của mình .

Bài viết đã được chỉnh sửa nội dung bởi PSW: 24-01-2012 - 11:35

1) Thể lệ
2) Danh sách các bài toán đã qua: 1-100, 101-200, 201-300, 301-400
Còn chờ gì nữa mà không tham gia! :luoi:

#2
Peter Pan

Peter Pan

    Sĩ quan

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

Trong $1$ lớp học có $2n$ học sinh ( $n \ge 2$) ; mỗi học sinh chơi thân với ít nhất $n$ bạn .

Chứng minh rằng ta có thể chọn ra $4$ học sinh để tổ chức học nhóm trên $1$ bàn tròn . Sao cho mỗi học sinh đều ngồi giữa $2$ người bạn thân của mình .

Dịch bài toán sang ngôn ngữ đồ thị,thứ nhất dễ nhận thấy đây là một chu trình Halminton. khi đó ta thấy $|E|=\frac{\sum_{i=1}^{2n}}{2} d(i) \geq \frac{2n^2}{2}=n^2=\frac{(2n)^2}{4}$
Nên theo đl Mantel thì đồ thị G này vẫn có thể không tồn tại chu trình tam giác.
+ Trường hợp 1: G ko có chu trình tam giác(TH xảy ra dấu bằng) thì tập đỉnh của G sẽ chia làm đồ thị lưỡng phân thành 2 tập đỉnh mỗi tập gồm n đỉnh, khi đó vì đỉnh của tập này đều có chung cạnh với tất cả các đỉnh của tập kia nên cứ hai đỉnh bên tập này và hai đỉnh ben tập kia tạp thành một chu trình 4 đỉnh. Khi đó bài toán được cm
+Trường hợp 2: G có chu trình tam giác thì bỏ đi 1 đỉnh tam giác đó ta tiếp tục xét với đồ thị $2n-1$ đỉnh còn lại, vì lúc này $|E|$ không lớn hơn hẳn $\frac{k^2}{4}$ ($k$ là đỉnh của G sau $2n-k$ lần phân hoạch) nên vẫn có thể tồn tại TH1, khi đó ta cũng có đpcm nên bây h ta xét bài toán với tất cả các cách phân hoạch đồ thị đều có chu trình tam giác.vì G là một chu trình Halminton nên ta xét G là một đa giác $2n$ đỉnh tô màu n tam giác ở biên và liên tiếp nhau ( tức là tam giác có 2 cạnh là 2 cạnh của $2n$ giác và ko chồng lên nhau) Khi đó sau $n+1$ lần phân hoạch đồ thị thì theo Dirichlet phải tồn tại 2 tam giác có chung cạnh. Hai tam giác này có 4 đỉnh tạo thành chu trình 4 đỉnh
Vậy bài toán đc chứng minh :)

Bài viết đã được chỉnh sửa nội dung bởi winwave1995: 25-01-2012 - 00:54

  • PSW yêu thích

\


#3
Karl Heinrich Marx

Karl Heinrich Marx

    Sĩ quan

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

Trong $1$ lớp học có $2n$ học sinh ( $n \ge 2$) ; mỗi học sinh chơi thân với ít nhất $n$ bạn .

Chứng minh rằng ta có thể chọn ra $4$ học sinh để tổ chức học nhóm trên $1$ bàn tròn . Sao cho mỗi học sinh đều ngồi giữa $2$ người bạn thân của mình .

Gọi A là người có số người quen nhiều nhất.
Nếu trong nhóm người quen của A, cứ 2 người người thì đôi một thì luôn quen nhau.
Trường hợp này dẫn đến số người quen của mỗi người thuộc nhóm người quen của A đều bằng nhau và đều bằng với A, như vậy tất cả những người này không thể quen 1 người ngoài nhóm (như vậy sẽ mâu thuẫn với đk A là người quen nhiều nhất). Ngoài nhóm này ra thì nhiều nhất còn $n-1$ người, lấy một người bất kì trong n-1 người này thì rõ ràng người đó quen biết ít hơn $n$ người. Suy ra A quen tất cả mọi người. Cứ chọn ra 4 người bất kì thì họ luôn đôi một quen nhau nên có cách xếp.
Nếu trong nhóm quen của A có một cặp không quen nhau. Xếp cặp này ngồi cạnh 2 bên của A. Theo nguyên lí dirichle thì trong số 2n-3 người còn lại 2 người này phải có 1 người quen chung. Xếp người đó vào vị trí cuối cùng. Thế là được cách xếp thỏa mãn
  • PSW yêu thích




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

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