Câu hỏi:
19/07/2024 122
Một cuộc họp có 6 người tham dự. Hai người bất kì trong họ hoặc quen nhau hoặc không quen nhau. Chứng minh rằng có 3 người trong 6 người đó đôi một quen nhau hoặc đôi một không quen nhau.
Một cuộc họp có 6 người tham dự. Hai người bất kì trong họ hoặc quen nhau hoặc không quen nhau. Chứng minh rằng có 3 người trong 6 người đó đôi một quen nhau hoặc đôi một không quen nhau.
Trả lời:
Giải bởi Vietjack
Gọi 6 người bất kì là A, B, C, D, E, G.
Trong 6 người đó ta chọn ra một người A.Trong 5 người còn lại ta chia thành 2 nhóm:
- Nhóm 1 gồm những người quen A.
- Nhóm 2 gồm những người không quen A.
Có 5 người mà chỉ có 2 nhóm. Do đó, tồn tại ít nhất 3 người thuộc cùng một nhóm. Tức là tồn tại ít nhất 3 người quen A hoặc tồn tại ít nhất 3 người không quen A.
- Nếu tồn tại ít nhất 3 người quen A. Gọi 3 người đó là B, C, D:
+ Nếu trong 3 người B, C, D có 2 người nào đó quen nhau. Giả sử 2 người đó là B và C thì ta có 3 người A, B, C là 3 người đôi một quen nhau.
+ Nếu trong 3 người B, C, D không có 2 người nào đó quen nhau thì 3 người B, C, D là 3 người đôi một không quen nhau.
- Nếu tồn tại 3 người không quen A. Giả sử 3 người đó là D, E, G:
+ Trong 3 người D, E, G nếu có 2 người nào đó không quen nhau. Giả sử 2 người đó là D và E thì 3 người A, D, E là 3 người đôi một không quen nhau.
+ Nếu trong 3 người D, E, G không có 2 người nào không quen nhau thì 3 người D, E, G là 3 người đôi một quen nhau.
Vậy trong 6 người bất kì luôn tồn tại 3 người đôi một quen nhau hoặc 3 người đôi một không quen nhau (đpcm).
Gọi 6 người bất kì là A, B, C, D, E, G.
Trong 6 người đó ta chọn ra một người A.Trong 5 người còn lại ta chia thành 2 nhóm:
- Nhóm 1 gồm những người quen A.
- Nhóm 2 gồm những người không quen A.
Có 5 người mà chỉ có 2 nhóm. Do đó, tồn tại ít nhất 3 người thuộc cùng một nhóm. Tức là tồn tại ít nhất 3 người quen A hoặc tồn tại ít nhất 3 người không quen A.
- Nếu tồn tại ít nhất 3 người quen A. Gọi 3 người đó là B, C, D:
+ Nếu trong 3 người B, C, D có 2 người nào đó quen nhau. Giả sử 2 người đó là B và C thì ta có 3 người A, B, C là 3 người đôi một quen nhau.
+ Nếu trong 3 người B, C, D không có 2 người nào đó quen nhau thì 3 người B, C, D là 3 người đôi một không quen nhau.
- Nếu tồn tại 3 người không quen A. Giả sử 3 người đó là D, E, G:
+ Trong 3 người D, E, G nếu có 2 người nào đó không quen nhau. Giả sử 2 người đó là D và E thì 3 người A, D, E là 3 người đôi một không quen nhau.
+ Nếu trong 3 người D, E, G không có 2 người nào không quen nhau thì 3 người D, E, G là 3 người đôi một quen nhau.
Vậy trong 6 người bất kì luôn tồn tại 3 người đôi một quen nhau hoặc 3 người đôi một không quen nhau (đpcm).
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Tìm hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị trong Hình 15
Tìm hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị trong Hình 15
Câu 4:
Quan sát đồ thị Hình 7 và cho biết:
a) Tổng các bậc của năm đỉnh trong đồ thị đó;
b) Số cạnh của đồ thị đó;
c) Tổng các bậc của năm đỉnh trong đồ thị gấp bao nhiêu lần số cạnh của đồ thị đó.
Quan sát đồ thị Hình 7 và cho biết:
a) Tổng các bậc của năm đỉnh trong đồ thị đó;
b) Số cạnh của đồ thị đó;
c) Tổng các bậc của năm đỉnh trong đồ thị gấp bao nhiêu lần số cạnh của đồ thị đó.
Câu 5:
Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.
Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.
Câu 6:
Quan sát đồ thị ở Hình 10 và đường đi CABDCB, cho biết:
a) Đường đi trên có đi qua tất cả các cạnh của đồ thị hay không?
b) Đường đi trên đi qua mỗi cạnh bao nhiêu lần?
Quan sát đồ thị ở Hình 10 và đường đi CABDCB, cho biết:
a) Đường đi trên có đi qua tất cả các cạnh của đồ thị hay không?
b) Đường đi trên đi qua mỗi cạnh bao nhiêu lần?
Câu 8:
Quan sát đồ thị ở Hình 4 và cho biết:
a) Với mỗi cặp đỉnh của đồ thị, có nhiều nhất bao nhiêu cạnh nối chúng;
b) Có hay không một đỉnh được nối với chính nó bởi một cạnh của đồ thị.
Quan sát đồ thị ở Hình 4 và cho biết:
a) Với mỗi cặp đỉnh của đồ thị, có nhiều nhất bao nhiêu cạnh nối chúng;
b) Có hay không một đỉnh được nối với chính nó bởi một cạnh của đồ thị.
Câu 9:
Cho ví dụ về một đồ thị liên thông và một đồ thị không liên thông.
Cho ví dụ về một đồ thị liên thông và một đồ thị không liên thông.
Câu 11:
Quan sát đường đi màu đỏ trên đồ thị ở Hình 13 và cho biết đường đi đó có đi qua tất cả các đỉnh của đồ thị hay không và mỗi đỉnh đi qua bao nhiêu lần.
Quan sát đường đi màu đỏ trên đồ thị ở Hình 13 và cho biết đường đi đó có đi qua tất cả các đỉnh của đồ thị hay không và mỗi đỉnh đi qua bao nhiêu lần.
Câu 12:
Có năm thành phố A, B, C, D, E sao cho hai thành phố bất kì trong chúng đều có đúng một đường nối với nhau. Sử dụng đồ thị để mô tả tình huống đó.
Có năm thành phố A, B, C, D, E sao cho hai thành phố bất kì trong chúng đều có đúng một đường nối với nhau. Sử dụng đồ thị để mô tả tình huống đó.
Câu 13:
Quan sát đồ thị ở Hình 6 và đếm số cạnh của đồ thị nhận đỉnh P làm đầu mút.
Quan sát đồ thị ở Hình 6 và đếm số cạnh của đồ thị nhận đỉnh P làm đầu mút.
Câu 15:
Có sáu thành phố A, B, C, D, E, G sao cho hai thành phố bất kì trong chúng đều có đường nối với nhau. Sử dụng đồ thị để mô tả tình huống đó.
Có sáu thành phố A, B, C, D, E, G sao cho hai thành phố bất kì trong chúng đều có đường nối với nhau. Sử dụng đồ thị để mô tả tình huống đó.
