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

[leanh9adst]

Trong phòng họp có n người (n>=3) sao cho mỗi người quen với ít nhất 2 người khác.Cmr có thể chọn ra trong số đó một số người để xếp ngồi quanh một bàn tròn sao cho mỗi người đều ngồi gần 2 người quen.

[toannguyenebolala]

Trong phòng họp có n người (n>=3) sao cho mỗi người quen với ít nhất 2 người khác.Cmr có thể chọn ra trong số đó một số người để xếp ngồi quanh một bàn tròn sao cho mỗi người đều ngồi gần 2 người quen.

  =))) Mình làm biếng vẽ cái đồ thị, bạn tự hình dung giúp nhé 

Xét với n=3, thỏa mãn.

Với n>3. Ta biểu diễn n người này dưới dạng n điểm $(A_{1},A_{2},...A_{n})$ trên một mặt phẳng, không có 3 điểm nào thẳng hàng. Thể hiện mối quan hệ quen bằng nét liền và không quen bằng nét đứt.

Cố định một điểm $(A_{1})$. Từ $A_{1}$ ta vẽ n-1 đoạn thẳng đến n-1 điểm còn lại.

Trường hợp 1: Người này quen với tất cả người còn lại, hay n-1 đoạn thẳng nối điểm này với các điểm còn lại đều là nét liền.

Lúc này từ một điểm $A_{i}$ bất kì, phải tồn tại một đoạn thẳng nối $A_{i}$ với một điểm $A_{j}(j\neq 1)$ là nét liền (theo giả thiết). Rõ ràng bây giờ thấy tồn tại một tam giác có 3 cạnh đều là nét liền hay nói cách khác tồn tại 3 người có thể xếp ngồi quanh một bàn tròn và mỗi người đều quen 2 người ngồi cạnh mình.

Trường hợp 2: Người này không quen với tất cả người còn lại, hay tồn tại một đoạn thẳng $A_{1}A_{k}$ nào đó là nét đứt. Lúc này, ta luôn chọn ra được 3 điểm $A_{k}, A_{l}, A_{m}$ sao cho 3 đoạn thẳng nối $A_{1}$ với 3 điểm trên có 2 đoạn là nét liền, 1 đoạn là nét đứt. Dễ dàng thấy được 1 tứ giác có cạnh đều là nét liền (cái này bạn tự vẽ). Suy ra ta có thể chọn ra 4 người để xếp vào bàn tròn và thỏa mãn đề bài.

Hoàn tất chứng minh.       

Bài viết đã được chỉnh sửa nội dung bởi toannguyenebolala: 04-09-2016 - 08:42

[leanh9adst]

The bạn có thể nói rõ hơn được không ạ? Mình dốt phần này lắm, thanks

[leanh9adst]

Ở trường hợp 2 ý

[toannguyenebolala]

Ở trường hợp 2 ý

Mình nhầm là đa giác chứ không phải tứ giác nhé bạn.

Còn để nói rõ hơn về trường hợp 2. Bạn vẽ hình với 1 điểm làm cố định, 2 đoạn thẳng liền 2 bên và các đoạn đứt ở giữa. Sau đó chia ra 3 trường hợp để giải. Chỗ này mình làm hơi dài dòng không ngắn gọn được

[12345678987654321123456789]

Trong phòng họp có n người (n>=3) sao cho mỗi người quen với ít nhất 2 người khác.Cmr có thể chọn ra trong số đó một số người để xếp ngồi quanh một bàn tròn sao cho mỗi người đều ngồi gần 2 người quen.

Xếp $n$ người trong phòng theo hàng dọc theo quy tắc sau :

B1. Chọn một người bất kì đứng đầu hàng. Đánh số $1$ cho người đó.

B2. Chọn một người quen với người đứng đầu hàng và xếp người đó vào cuối hàng. Đánh số $2$ cho người đó.

B3. Chọn một người trong phòng sao cho quen với người đang đứng cuối hàng, không tính người đứng liền trước người đứng cuối hàng. Ta luôn tìm được một người như vậy bởi mỗi người trong phòng quen với ít nhất $2$ người khác.

* Nếu người đó chưa đứng vào hàng thì xếp người đó vào cuối hàng và đánh số $i$ là vị trí đứng cho người đó.

* Nếu người đó đã đứng vào hàng, giả sử chỉ số của người đó là $i$ thì rõ ràng từ người $i$ đến người đứng cuối hàng là nhóm người cần chọn. Kết thúc bài toán ở đây.

B4. Lặp lại bước 3 cho đến khi đủ $n$ người trong hàng hoặc tìm được nhóm người cần chọn.

B5. Đến bước này nếu đã tìm được nhóm người cần chọn thì kết thúc việc xếp. Nếu ta vẫn chưa chọn được nhóm người phù hợp thì : Hiển nhiên ta có người đầu hàng quen với người thứ $2$, mà mỗi người trong phòng đều quen với ít nhất $2$ người khác nên tồn tại một người có chỉ số $i$ trong hàng quen với người đầu hàng. Rõ ràng từ người đầu hàng đến người thứ $i$ là nhóm người cần chọn. Ta kết thúc bài toán ở đây.

Sau khi hoàn thành xong cách xếp ta luôn tìm được nhóm người thỏa mãn đề bài. Bài toán được giải quyết.

P/s : Ghi nó dài thế thôi chứ ý tưởng cũng không có gì khó đâu bạn chịu khó đọc nha

Viết mỏi tay lắm đấy hay thì like cho mình mừng nhé. Có chỗ nào không hiểu hoặc thấy mình làm sai thì bạn trả lời ở dưới nha

Bài viết đã được chỉnh sửa nội dung bởi 12345678987654321123456789: 04-09-2016 - 13:34