Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

Trên đường tròn cho n điểm

toán tổ hợp và rời rạc

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

#1 nguyen kd

nguyen kd

    Hạ sĩ

  • Thành viên
  • 62 Bài viết
  • Giới tính:Nam
  • Đến từ:Quảng Nam
  • Sở thích:Giải Toán

Đã gửi 14-12-2018 - 22:35

Trên đường tròn cho n điểm, từ các điểm nói trên hiển nhiên ta có ${C_n}^2$ đoạn thẳng và tổng số các đa giác là

$({C_n}^3 + {C_n}^4 + {C_n}^5 + ... + {C_n}^n)$ .Hãy tìm số cách bỏ bi các đoạn thẳng sao cho không còn đa giác nào , biết rằng mỗi cách bỏ đi các đoạn thẳng như vậy thì mỗi điểm nói trên , vẫn tồn tại ít nhất một đoạn thẳng nhận nó làm đầu mút ?

 



#2 Karl Heinrich Marx

Karl Heinrich Marx

    Sĩ quan

  • Thành viên
  • 322 Bài viết
  • Giới tính:Nam

Đã gửi 03-01-2019 - 02:08

Trên đường tròn cho n điểm, từ các điểm nói trên hiển nhiên ta có ${C_n}^2$ đoạn thẳng và tổng số các đa giác là

$({C_n}^3 + {C_n}^4 + {C_n}^5 + ... + {C_n}^n)$ .Hãy tìm số cách bỏ bi các đoạn thẳng sao cho không còn đa giác nào , biết rằng mỗi cách bỏ đi các đoạn thẳng như vậy thì mỗi điểm nói trên , vẫn tồn tại ít nhất một đoạn thẳng nhận nó làm đầu mút ?

Yêu cầu bài này phải phát biểu lại là với một cấu hình xóa đi các đoạn thẳng thỏa mãn 2 điều kiện nêu ra thì cấu hình này có nhiều nhất bao nhiêu đoạn thẳng.

 

Có nhiều nhất là $n-1$ đoạn thẳng (vd $1$ điểm nối với $n-1$ điểm còn lại chẳng hạn). Cái này liên quan đến định nghĩa cây ( đồ thị liên thông, không có chu trình) trong lý thuyết đồ thị.

 

Mình sẽ chỉ ra một cách chứng mình mình nghĩ ra (tham khảo sách về tính chất của cây với $n$ điểm có thể bạn sẽ tìm thấy chứng minh hay hơn).

 

- Hai điểm gọi là liên thông nếu có một đường đi tạo bởi ít nhất 2 đoạn thẳng nối hai điểm đó.

 

- Nếu một cấu hình thỏa mãn 2 điều kiện bài toán mà có hai điểm không liên thông, ta có thể nối chúng lại với nhau để có một cấu hình mới thỏa mãn yêu cầu mà có số đoạn thẳng lớn hơn. Do đó cần tìm max số đoạn thẳng trong trường hợp 2 điểm bất kì trong $n$ điểm liên thông với nhau.

 

- Xét một cấu hình thỏa mãn : không có đa giác, mỗi điểm trong $n$ điểm là mút của ít nhất một đoạn thẳng, cấu hình này có nhiều đoạn thẳng nhất và 2 điểm bất kì (khác 2 mút một đoạn thẳng) trong $n$ điểm liên thông với nhau. Xét tập $S$ chứa một điểm bất kì trong $n$ điểm.

 

- Mỗi bước ta xóa đi một đoạn thẳng thỏa mãn : đoạn thẳng này có một mút là một điểm thuộc $S$ và một điểm không thuộc $S$ và sau đó thêm cái điểm nằm ngoài $S$ của đoạn thẳng vừa xóa vào $S$.

 

- Rõ ràng khi tập $S$ chưa lấp đầy bởi $n$ phần tử thì luôn tìm được ít nhất một đoạn thẳng thỏa mãn để xóa. Nếu không các điểm trong $S$ không liên thông với điểm nào ngoài $S$.

 

- Khi đó tất cả các điểm thuộc $S$ mà không nối với nhau bởi một đoạn thẳng đã bị xóa thì liên thông với nhau.

 

- Khi tập $S$ đầy $n$ phần tử thì không còn đoạn thẳng nào nữa. Vì nếu tồn tại một đoạn thẳng nối 2 điểm trong $S$ mà đoạn này chưa bị xóa, khi đó tồn tại một đường đi lớn hơn 2 đoạn thẳng nối 2 điểm đó, như thế thì cấu hình ban đầu chứa một đa giác.

 

Vậy cấu hình ban đầu nêu ra có đúng $n-1$ đoạn thẳng.






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

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