Lời giải bài Tổ hợp đề thi VMO 2020 ngày 2 (Bài 7)

Xin giới thiệu Lời giải bài Tổ hợp đề thi VMO 2020 ngày 2 (Bài 7 - kì thi chọn học sinh giỏi quốc gia năm 2020) của tác giả Lê Phúc Lữ . Đ...

Xin giới thiệu Lời giải bài Tổ hợp đề thi VMO 2020 ngày 2 (Bài 7 - kì thi chọn học sinh giỏi quốc gia năm 2020) của tác giả Lê Phúc Lữ.

Đề bài 7 - VMO 2020 ngày 2

a) Tính số phần tử của T.
b) Chứng minh rằng tồn tại một tập hợp liên kết với T có đúng 2n(n−1) phần tử.
c) Chứng minh rằng mỗi tập hợp liên kết với T có không ít hơn 2n(n−1) phần tử.

Lời giải bài 7 (tổ hợp) VMO 2020

Nhận xét. Bài toán này thực ra là một cách phát biểu của khéo léo, che giấu đi bản chất vấn đề của định lý Mantel – Turan. Quan hệ “không có tam giác” phát biểu thông qua ràng buộc khá rõ, nhưng cần phải xử lý cẩn thận, vì đề cho quan hệ có hướng (trong khi định lý chỉ áp dụng được cho graph vô hướng).

Theo Lê Phúc Lữ. Người đăng: Sơn Phan.

Xem thêm: Giải đề VMO 2020 ngày 2: Lời giải Bài 5 (Hệ phương trình) - Lời giải Bài 6 (Hình học) - Lời giải Bài 7 (Tổ hợp).