Giả sử rằng người gặp nhau tại một cuộc họp, và mỗi người quen đúng 8 người khác. Hai người bất kỳ quen nhau có đúng 4 người quen chung, và 2 người không quen nhau bất kỳ có đúng 2 người quen chung. Tìm tất cả các giá trị có thể của .
Review all problems of Taiwan MO 1995
Taiwan MO 1995
Bắt đầu bởi Merlyn, 02-10-2006 - 11:25
#1
Đã gửi 02-10-2006 - 11:25
#2
Đã gửi 02-10-2006 - 15:25
Giả sử A quen người là
Xét tập B gồm người còn lại
Ta sẽ đếm số cạnh giữa 2 tập và với nhau
Với mỗi thì có người quen chung nên nối với người thuộc
Do đó số cạnh là
Mặt khác
Với mỗi và thì có đúng người quen chung
Do đó nối với đỉnh thuộc tập
Do đó số cạnh là
Từ đó ta có suy ra
Vậy giá trị có thể của là
Xét tập B gồm người còn lại
Ta sẽ đếm số cạnh giữa 2 tập và với nhau
Với mỗi thì có người quen chung nên nối với người thuộc
Do đó số cạnh là
Mặt khác
Với mỗi và thì có đúng người quen chung
Do đó nối với đỉnh thuộc tập
Do đó số cạnh là
Từ đó ta có suy ra
Vậy giá trị có thể của là
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#3
Đã gửi 11-10-2006 - 19:51
cái này có vấn đề,chắc gì 4 người quen chung ở tập BVới mỗi thì có người quen chung nên nối với người thuộc
Mừng 4 năm bạn tham gia Diễn đàn Toán ( Từ: NangLuong )
Chúc mừng gauss2
Hôm nay là tròn 4 năm bạn tham gia Diễn đàn Toán học.
Chúng tôi hy vọng bạn đã có thời gian tham gia Diễn đàn Toán vui & bổ ích.
Mong rằng trong thời gian tới bạn sẽ tiếp tục là một người bạn gắn bó với Diễn đàn Toán học. Ch�...
NangLuong là thành viên của Quản trị và có 2680 bài viết.
Gửi vào: 25 Jul 2009 - 7:00
Chúc mừng gauss2
Hôm nay là tròn 4 năm bạn tham gia Diễn đàn Toán học.
Chúng tôi hy vọng bạn đã có thời gian tham gia Diễn đàn Toán vui & bổ ích.
Mong rằng trong thời gian tới bạn sẽ tiếp tục là một người bạn gắn bó với Diễn đàn Toán học. Ch�...
NangLuong là thành viên của Quản trị và có 2680 bài viết.
Gửi vào: 25 Jul 2009 - 7:00
#4
Đã gửi 12-10-2006 - 10:51
Cái này thì quá đơn giản rồi còn gìcái này có vấn đề,chắc gì 4 người quen chung ở tập B
Với mỗi thì có người quen chung nên nối với người thuộc
Vì mỗi quen với người trong tập
Mà nên đỉnh còn lại phải nằm trong tập thôi
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#5
Đã gửi 13-10-2006 - 05:05
To HFZMATHS & anh em: đáp án bài này thế nào vậy ? có phải ko tồn tại n như thế ?
Tại hạ vừa lim dim ngủ vừa giải trong đầu như sau, mong anh em chỉ ra sai sót giùm nhé !
Giả sử http://dientuvietnam...n/mimetex.cgi?8 người quen của http://dientuvietnam...n/mimetex.cgi?A là: http://dientuvietnam...n/mimetex.cgi?A và http://dientuvietnam...mimetex.cgi?A_i quen nhau => có đúng http://dientuvietnam...n/mimetex.cgi?4 người quen chung. Bởi vì http://dientuvietnam...n/mimetex.cgi?4 người này quen với http://dientuvietnam...n/mimetex.cgi?A => họ thuộc tập http://dientuvietnam...n/mimetex.cgi?X => http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_i quen với đúng 4 người khác trong tập http://dientuvietnam...n/mimetex.cgi?X
Khẳng định 2) Do http://dientuvietnam.net/cgi-bin/mimetex.cgi?A' khác http://dientuvietnam.net/cgi-bin/mimetex.cgi?A và ko thuộc tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?X => http://dientuvietnam.net/cgi-bin/mimetex.cgi?A' ko quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?A => giữa http://dientuvietnam.net/cgi-bin/mimetex.cgi?A' và http://dientuvietnam.net/cgi-bin/mimetex.cgi?A tồn tại hai người quen chung. Tương tự, bởi vì hai người này quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?A nên sẽ thuộc tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?X => tập người quen http://dientuvietnam.net/cgi-bin/mimetex.cgi?X' của http://dientuvietnam.net/cgi-bin/mimetex.cgi?A' và tập người quen http://dientuvietnam.net/cgi-bin/mimetex.cgi?X của http://dientuvietnam.net/cgi-bin/mimetex.cgi?A có đúng 2 phần tử chung. Ta gọi 2 người này là http://dientuvietnam.net/cgi-bin/mimetex.cgi?B và http://dientuvietnam.net/cgi-bin/mimetex.cgi?C có thể quen hoặc ko quen nhau.
- Nếu ko quen nhau: Ta thấy rằng http://dientuvietnam.net/cgi-bin/mimetex.cgi?B phải quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?4 người trong http://dientuvietnam.net/cgi-bin/mimetex.cgi?X và http://dientuvietnam.net/cgi-bin/mimetex.cgi?4 người trong http://dientuvietnam.net/cgi-bin/mimetex.cgi?X' (theo 1) và họ hoàn toàn khác nhau (theo 2). Ngoài ra, http://dientuvietnam.net/cgi-bin/mimetex.cgi?B quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?B quen http://dientuvietnam.net/cgi-bin/mimetex.cgi?10 người !!!
- Nếu quen nhau: đối với http://dientuvietnam.net/cgi-bin/mimetex.cgi?B, ngoài quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?B phải quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?3 người khác trong mỗi tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?B quen http://dientuvietnam.net/cgi-bin/mimetex.cgi?9 người !!!
Tóm lại, ko thỏa mãn đề bài.
Nếu , mỗi người phải quen với 8 người còn lại => tất cả mọi người đều quen nhau => hai người bất kỳ có 7 người quen chung => sai. Và nếu thì ta ko còn đk mỗi người có đúng 8 người quen nữa => sai luôn.
Vậy ko tồn tại n như thế.
Anh em kiểm tra kỹ giùm nha, chắc là có sai chỗ nào đó
Tại hạ vừa lim dim ngủ vừa giải trong đầu như sau, mong anh em chỉ ra sai sót giùm nhé !
Giả sử http://dientuvietnam...n/mimetex.cgi?8 người quen của http://dientuvietnam...n/mimetex.cgi?A là: http://dientuvietnam...n/mimetex.cgi?A và http://dientuvietnam...mimetex.cgi?A_i quen nhau => có đúng http://dientuvietnam...n/mimetex.cgi?4 người quen chung. Bởi vì http://dientuvietnam...n/mimetex.cgi?4 người này quen với http://dientuvietnam...n/mimetex.cgi?A => họ thuộc tập http://dientuvietnam...n/mimetex.cgi?X => http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_i quen với đúng 4 người khác trong tập http://dientuvietnam...n/mimetex.cgi?X
Khẳng định 2) Do http://dientuvietnam.net/cgi-bin/mimetex.cgi?A' khác http://dientuvietnam.net/cgi-bin/mimetex.cgi?A và ko thuộc tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?X => http://dientuvietnam.net/cgi-bin/mimetex.cgi?A' ko quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?A => giữa http://dientuvietnam.net/cgi-bin/mimetex.cgi?A' và http://dientuvietnam.net/cgi-bin/mimetex.cgi?A tồn tại hai người quen chung. Tương tự, bởi vì hai người này quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?A nên sẽ thuộc tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?X => tập người quen http://dientuvietnam.net/cgi-bin/mimetex.cgi?X' của http://dientuvietnam.net/cgi-bin/mimetex.cgi?A' và tập người quen http://dientuvietnam.net/cgi-bin/mimetex.cgi?X của http://dientuvietnam.net/cgi-bin/mimetex.cgi?A có đúng 2 phần tử chung. Ta gọi 2 người này là http://dientuvietnam.net/cgi-bin/mimetex.cgi?B và http://dientuvietnam.net/cgi-bin/mimetex.cgi?C có thể quen hoặc ko quen nhau.
- Nếu ko quen nhau: Ta thấy rằng http://dientuvietnam.net/cgi-bin/mimetex.cgi?B phải quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?4 người trong http://dientuvietnam.net/cgi-bin/mimetex.cgi?X và http://dientuvietnam.net/cgi-bin/mimetex.cgi?4 người trong http://dientuvietnam.net/cgi-bin/mimetex.cgi?X' (theo 1) và họ hoàn toàn khác nhau (theo 2). Ngoài ra, http://dientuvietnam.net/cgi-bin/mimetex.cgi?B quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?B quen http://dientuvietnam.net/cgi-bin/mimetex.cgi?10 người !!!
- Nếu quen nhau: đối với http://dientuvietnam.net/cgi-bin/mimetex.cgi?B, ngoài quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?B phải quen với http://dientuvietnam.net/cgi-bin/mimetex.cgi?3 người khác trong mỗi tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?B quen http://dientuvietnam.net/cgi-bin/mimetex.cgi?9 người !!!
Tóm lại, ko thỏa mãn đề bài.
Nếu , mỗi người phải quen với 8 người còn lại => tất cả mọi người đều quen nhau => hai người bất kỳ có 7 người quen chung => sai. Và nếu thì ta ko còn đk mỗi người có đúng 8 người quen nữa => sai luôn.
Vậy ko tồn tại n như thế.
Anh em kiểm tra kỹ giùm nha, chắc là có sai chỗ nào đó
Bài viết đã được chỉnh sửa nội dung bởi longanimity: 13-10-2006 - 05:13
#6
Đã gửi 13-10-2006 - 17:57
Đồng ý với longanimity, đáp án là không tồn tại thỏa mãn đề bài. Tân xem lại lời giải hộ cái!!
#7
Đã gửi 13-10-2006 - 18:15
Cảm ơn HFZMATHS đã xem xét lời giải giùm mình.
Về lời giải của Tân, sau khi tìm ra n=21, Tân khẳng định rất đúng, đó là giá trị "có thể". Nghĩa là cần một bước nhỏ nữa để xác thực n=21 có thỏa mãn hay ko.
Về lời giải của Tân, sau khi tìm ra n=21, Tân khẳng định rất đúng, đó là giá trị "có thể". Nghĩa là cần một bước nhỏ nữa để xác thực n=21 có thỏa mãn hay ko.
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh