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

[QUANVU]

Cho số nguyên dương n>1,http://dientuvietnam.net/cgi-bin/mimetex.cgi?B_1,B_2,...,B_n là n tập con của X,với mỗi http://dientuvietnam...mimetex.cgi?B_i có đúng 2 phần tử.Tìm giá trị nhỏ nhất của |X|,sao cho với mỗi cách chọn các http://dientuvietnam...tex.cgi?B_i,tồn tại tập con Y của X sao cho:
a)|Y|=n và
b) .

[kokichi_pbc]

đáp số|X|=2n-1

[kokichi_pbc]

lời giải bài này
giả sử X={1,2,...}
nhận thấy |X|=2n-2 không thỏa mãn
chọn các tập:{1,2} {1,3} {2,4} {5,6}{7,8}...{2n-3,2n-2}
gọi là các trị số của các phần tử của X thỏa mãn:
i, =k nếu i thuộc k tập hợp
ii, thay=0,=2 nếu a_i=a_j=1 và cùng thuộc một tập hợp
chọn Y là các phần tử nhận các trị số 0,1 Thấy Y thỏa mãn nếu |Y|=n
Ta có =2n
_ nếu =3,chọn Y là các phần tử nhận các trị số 0,1
_ngươc lại, ta xét tiếp 2 trường hợp
- không $a_i$=1chon Y là các phần tử có trị số là 0 và 1 phần tử bất kì có trị số là 2
-ngược lại,chọn Y là các phần tử nhận các trị số 0,1

[leecom]

Mình thì lại tính được đáp số là http://dientuvietnam...ex.cgi?|X|=2n-2 thì vô lý chỗ nào nhỉ?

Bài viết đã được chỉnh sửa nội dung bởi leecom: 24-11-2006 - 17:02

[kokichi_pbc]

giả sử tồn tại Y
do nó không chứa hai phần tử của cùng một tập hợp
nên nó chỉ chứa 1 phần tử của mỗi tập {5,6}{7,8}...{2n-3,2n-2}
nên Y chứa 3 phần tử trong {1,2}{1,3}{2,4}
mâu thuẫn