Bài 5

Cho các số nguyên dương , tìm số nguyên dương nhỏ nhất sao cho trong mọi nhóm người, hoặc có người chia được thành cặp đôi quen biết nhau, hoặc có người chia được thành cặp đôi không quen biết nhau.

m

n

k

k

2m

m

2n

n

Bước 2 trên 5: Dựng ví dụ cho cận dưới

Bước trước Bước tiếp

(2m-1)+(n-1)=2m+n-2

Phân tích chi tiết

Lấy nhóm $2m+n-2$ người gồm một nhóm $(2m-1)$ người đôi một quen nhau và $n-1$ người cô lập không quen ai khác. Không có $2m$ người đôi một quen nhau để ghép thành m cặp, cũng không có $2n$ người để ghép thành $n$ cặp đôi một không quen nhau. Vì vậy $r(m,n)\ge2m+n-1$ .