MathLabs

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. mm nn kk kk 2m2m mm 2n2n nn
Bước 1 trên 5: Khai thác tính đối xứng
Bước trướcBước tiếp
r(m,n)=r(n,m);m≥n⟹it suffices to prove r(m,n)=2m+n−1r(m,n)=r(n,m);\qquad m\ge n\Longrightarrow\text{it suffices to prove }r(m,n)=2m+n-1
Phân tích chi tiết

Gọi r(m,n)r(m,n) là giá trị kk nhỏ nhất thỏa mãn. Đổi quan hệ quen biết và không quen biết sẽ hoán đổi mm và nn, nên r(m,n)=r(n,m)r(m,n)=r(n,m). Giả sử m≥nm\ge n; cần chứng minh r(m,n)=2m+n−1r(m,n)=2m+n-1.