Đến nội dung

Hình ảnh

Chứng minh số người quen nhiều nhất là $ \frac{2n}{5}$

- - - - -

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

#1
PSW

PSW

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

  • Quản trị
  • 493 Bài viết
Cho $1$ nhóm người đi du lịch gồm $n$ người . Trong $3$ người bất kỳ thì luôn có $2$ người không quen nhau .

Ta biết rằng với mọi cách chia nhóm trên ra $2$ xe buýt thì ta luôn có thể tìm $2$ người cùng đi trên $1$ xe và quen nhau .

Chứng rằng rằng có 1 du khách mà số người quen không lớn hơn $ \frac{2n}{5}$

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

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

Cho $1$ nhóm người đi du lịch gồm $n$ người . Trong $3$ người bất kỳ thì luôn có $2$ người không quen nhau .

Ta biết rằng với mọi cách chia nhóm trên ra $2$ xe buýt thì ta luôn có thể tìm $2$ người cùng đi trên $1$ xe và quen nhau .

Chứng rằng rằng có 1 du khách mà số người quen không lớn hơn $ \frac{2n}{5}$

Cho em hỏi số người trên 2 xe buýt có bằng nhau ko vậy :)

\


#3
PSW

PSW

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

  • Quản trị
  • 493 Bài viết
Àh ; ta hiểu là trên 1 xe buýt có thể không có người nào ; cũng có thể có n người . Nói chung số người trên 2 xe là tuỳ ý :)
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:

#4
Peter Pan

Peter Pan

    Sĩ quan

  • Thành viên
  • 360 Bài viết
cái này thêm đk " xe buýt" vào thu hẹp lại đl Mantel rồi :(

\


#5
Didier

Didier

    đẹp zai có một ko hai

  • Thành viên
  • 403 Bài viết
Cho em hỏi ở đây có thể có 3 người không quen nhau được không ạh


#6
PSW

PSW

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

  • Quản trị
  • 493 Bài viết
Didier : àhh có ; chính xác thì là : trong 3 người bất kỳ trong đòan thì luôn tìm dc 2 người không quen nhau .
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:

#7
Karl Heinrich Marx

Karl Heinrich Marx

    Sĩ quan

  • Thành viên
  • 321 Bài viết
Ký hiệu mỗi người là một đỉnh và hai người quen nhau thì được nối với nhau bởi 1 cạnh. Trong các đa giác tạo thành từ các cạnh này nếu như tất cả đều có số đỉnh chẵn thì ta chia mỗi đa giác đó thành 2 tập là 2 tập đỉnh xen kẽ của đa giác đó, với mỗi đường gấp khúc không kín ta cũng chia tập đỉnh của nó thành 2 tập xen kẽ (vd với tứ giác thì cho đỉnh 1,3 cùng tập, 2 vs 4 cùng tập). Khi đấy ta thấy rằng ở 2 tập trong mỗi tập ko có cặp nào quen nhau. Dẫn đến vô lí.
Tồn tại một đa giác có số đỉnh là lẻ, không có 3 ng` đôi một quen nhau nên ko có tam giác
Với ngũ giác thì mỗi đỉnh thuộc $n-5$ đỉnh còn lại không thuộc đa giác chỉ được nối với nhiều nhất 2 đỉnh. Do đó trong ngũ giác đó phải có một đỉnh có bậc bé hơn $\frac{2(n-5)}{5}<\frac{2n}{5}$
Nếu tồn tại một đa giác có $k>5$ cạnh, gồm các đỉnh là $p_1,p_2,...,p_k$ ($p_1$ được coi là $p_{k+1}$) thì mỗi điểm bên ngoài không được nối với $2$ điểm $p_i,p_j$ mà $|i-j|>2$ vì nếu như vậy sẽ tạo thành 1 đa giác ít cạnh hơn $k$. Như thế thì mỗi đỉnh thuộc $n-k$ đỉnh còn lại cũng chỉ được nối với nhiều nhất 2 đỉnh thuộc đa giác. Do đó tồn tại một đỉnh thuộc đa giác có bậc bé hơn $\frac{2(n-k)}{k}<\frac{2}{5}$

#8
Peter Pan

Peter Pan

    Sĩ quan

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

Cho $1$ nhóm người đi du lịch gồm $n$ người . Trong $3$ người bất kỳ thì luôn có $2$ người không quen nhau .

Ta biết rằng với mọi cách chia nhóm trên ra $2$ xe buýt thì ta luôn có thể tìm $2$ người cùng đi trên $1$ xe và quen nhau .

Chứng rằng rằng có 1 du khách mà số người quen không lớn hơn $ \frac{2n}{5}$

Đây là định lí Andrásfai-Erdos-Sós :)

\





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

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