Đến nội dung

Hình ảnh

Chứng minh rằng có thể chia lớp ra làm 2 tổ sao cho ...

- - - - - psw

  • Please log in to reply
Chủ đề này có 5 trả lời

#1
kelieulinh

kelieulinh

    Thượng sĩ

  • Thành viên
  • 226 Bài viết

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



#2
The Gunner

The Gunner

    Hạ sĩ

  • Thành viên
  • 93 Bài viết
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

Những ngày cuối cùng còn học toán

winwave1995

#3
hoangtrunghieu22101997

hoangtrunghieu22101997

    Thượng sĩ

  • Thành viên
  • 206 Bài viết
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

Sự im lặng du dương hơn bất kỳ bản nhạc nào.


#4
hoangtrunghieu22101997

hoangtrunghieu22101997

    Thượng sĩ

  • Thành viên
  • 206 Bài viết
$\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*$

Sự im lặng du dương hơn bất kỳ bản nhạc nào.


#5
The Gunner

The Gunner

    Hạ sĩ

  • Thành viên
  • 93 Bài viết
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

Những ngày cuối cùng còn học toán

winwave1995

#6
PSW

PSW

    Những bài toán trong tuần

  • Quản trị
  • 493 Bài viết
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
1) Thể lệ
2) Danh sách các bài toán đã qua: 1-100, 101-200, 201-300, 301-400
Còn chờ gì nữa mà không tham gia! :luoi:





Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: psw

2 người đang xem chủ đề

0 thành viên, 2 khách, 0 thành viên ẩn danh