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 4 trên 5: Quy nạp từ trường hợp cơ sở

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

r(s,1)=2s,\qquad r(m,n)\le2m+n-1

Phân tích chi tiết

Trường hợp cơ sở là $r(s,1)=2s$ : trong $2s$ người, hoặc có $2s$ người đôi một quen nhau, hoặc có hai người không quen nhau. Lặp hệ thức truy hồi cho $r(m,n)\le2m+n-1$ khi $m\ge n$ . Kết hợp cận dưới, ta có đẳng thức.