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) .
n tập con 2 phần tử
Bắt đầu bởi QUANVU, 16-11-2006 - 12:35
#1
Đã gửi 16-11-2006 - 12:35
1728
#2
Đã gửi 23-11-2006 - 15:58
đáp số|X|=2n-1
#3
Đã gửi 24-11-2006 - 10:55
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
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
#4
Đã gửi 24-11-2006 - 17:01
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
The Past, The Present, and The Future...
#5
Đã gửi 25-11-2006 - 11:54
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
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
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh