Chủ đề này có 1 trả lời

[QUANVU]

Cho http://dientuvietnam...mimetex.cgi?m,n là các số nguyên dương và http://dientuvietnam...n/mimetex.cgi?S là tập con với http://dientuvietnam...etex.cgi?(2^m-1)n+1 phần tử của tập http://dientuvietnam...n/mimetex.cgi?S chứa http://dientuvietnam...mimetex.cgi?m 1 số phân biệt sao cho với mỗi .

Nhìn lại các bài toán của Rumani TST 2006

[leecom]

Giả sủ không tồn tại tập http://dientuvietnam...n/mimetex.cgi?S thỏa mãn đk bài toán.
Xét n bộ sau đây:
http://dientuvietnam...2^{2},...,2^{m})
http://dientuvietnam...{2},...,n.2^{m})
Ta phân các bộ trên vào các lớp với định nghĩa: một bộ thuộc lớp http://dientuvietnam...n/mimetex.cgi?i nếu số nhỏ nhất của bộ đó có dạng http://dientuvietnam...tex.cgi?2^{q}.i ( http://dientuvietnam...imetex.cgi?(2,i)=1 và http://dientuvietnam...n/mimetex.cgi?i bất kỳ.
Giả sử bộ có phần tử nhỏ nhất lớn nhất so với phần tử nhỏ nhất của các bộ khác là http://dientuvietnam...tex.cgi?2^{q}.i
Vậy thì ở lớp này ta phải loại đi ít nhất http://dientuvietnam...mimetex.cgi?q 1 phần tử.
Vì nếu xét bộ sau http://dientuvietnam...n/mimetex.cgi?q phần tử thì ta vẫn sẽ được một bộ http://dientuvietnam.net/cgi-bin/mimetex.cgi?q+1 bộ, tức số số bị loại ở lớp đó ít nhất phải bằng số bộ nằm trong lớp đó.
Tổng số bộ của các lớp là n.
Vậy thì ta phải loại đi ít nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?n phần tử. (mâu thuẫn với giả thiết tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?S có tới http://dientuvietnam.net/cgi-bin/mimetex.cgi?(2^{m}-1).n+1 phần tử