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

[kelieulinh]

Trong một lớp học mỗi học sinh có không quá ba người bạn thân.Chứng minh rằng có thể chia lớp ra làm $2$ tổ sao cho ở mỗi tổ mỗi bạn có không quá $1$ bạn thân

KCT

[The Gunner]

Ban đầu chia bất kì các học sinh thành 2 tổ, gọi S là số các cặp bạn thân trong cùng 1 tổ, nếu 1 người có số bạn thân ít nhất là 2 trong tổ này thì sẽ có nhiều nhất 1 bạn thân trong tổ kia, giờ ta chuyển người này qua tổ kia thì S sẽ giảm đi ít nhất là 1.Vì S là số nguyên dương ko âm nên quá trình này sẽ dừng sau hữu hạn bước khi đó ta được 2 tổ thỏa mãn

Bài viết đã được chỉnh sửa nội dung bởi The Gunner: 02-08-2012 - 22:27

[hoangtrunghieu22101997]

Cách khác:
Ta sẽ chứng minh bằng quy nạp
Giả sử lớp đó có n bạn $(n \in N*)$
Thấy n=1;2 đúng
Giả sử lớp đó với k học sinh có thể chia lớp ra làm 2 tổ sao cho ở mỗi tổ mỗi bạn có không quá 1 bạn thân
Ta sẽ chứng minh mệnh đề đúng $k+1$
Thật vậy
Xét bạn thứ $k+1$ không nằm trong $k$ bạn gọi là :X
+)Nếu bạn có 3 bạn thân là:A,B,C
-Trong 3 bạn có 3 cặp quen nhau có nghĩa là A quen B ;B quen C; C quen A
Giả sử A,B một nhóm ;C một nhóm.Xếp X vào nhóm C.
- Trong 3 bạn chỉ có 2 cặp quen nhau
Giả sử A quen B; B quen C. Chia 2 Th
# AB (hoặc BC) một nhóm xếp X vào C (hoặc B)
# AC cùng nhóm xếp X vào B
- Trong 3 bạn chỉ có 1 cặp quen nhau
Giả sử A quen B.
Xếp A,B vào 2 nhóm
Xếp X vào nhóm không có C thì thoả mãn.
-Trong A,B,C không ai quen nhau
# A,B,C cùng nhóm
# A,B cùng nhóm
Nếu C có bạn ở cùng nhóm .Ta xếp X vào nhóm A,B
Nếu C không có bạn cùng nhóm .Ta xếp X vào nhóm C
+) Chứng minh tương tự với
Nếu bạn đó có 2;1;0 bạn thân.
Bài toán được chứng minh xong

Bài viết đã được chỉnh sửa nội dung bởi hoangtrunghieu22101997: 03-08-2012 - 20:43

[hoangtrunghieu22101997]

$\fbox{Tổng quát}$

Trong một lớp học mỗi học sinh có không quá người $an-1$ bạn thân.Chứng minh rằng có thể chia lớp ra làm $n$ tổ sao cho ở mỗi tổ mỗi bạn có không quán$a$ bạn thân.
Với $a;n \in N*$

[The Gunner]

phần cm quy nạp của bạn chưa chặt, lỡ trong nhóm đó, C đã có 1 người quen rồi, giờ thêm người này vào tổ nữa thì C sẽ có đến 2 người quen. Nên chưa thỏa mãn nên buộc ta phải chuyển C sang nhóm còn lại. Như thế bài tóan mới chặt

Bài viết đã được chỉnh sửa nội dung bởi The Gunner: 03-08-2012 - 16:14

[PSW]

Chấm điểm:

The Gunner: 10 điểm


hoangtrunghieu22101997: 5 điểm

Chú ý: từ bài này, nêu ra mở rộng, phải giải quyết mới được điểm