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
Chứng minh rằng có thể chia lớp ra làm 2 tổ sao cho ...
Bắt đầu bởi kelieulinh, 17-02-2005 - 15:21
psw
#1
Đã gửi 17-02-2005 - 15:21
- E. Galois, minhdat881439, daovuquang và 4 người khác yêu thích
#2
Đã gửi 02-08-2012 - 22:27
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
- E. Galois, perfectstrong, minhdat881439 và 9 người khác yêu thích
Những ngày cuối cùng còn học toán
winwave1995
#3
Đã gửi 03-08-2012 - 08:18
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
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
- E. Galois và C a c t u s thích
Sự im lặng du dương hơn bất kỳ bản nhạc nào.
#4
Đã gửi 03-08-2012 - 08:28
$\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*$
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*$
- E. Galois và Stranger411 thích
Sự im lặng du dương hơn bất kỳ bản nhạc nào.
#5
Đã gửi 03-08-2012 - 16:12
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
- E. Galois, perfectstrong và hoangtrunghieu22101997 thích
Những ngày cuối cùng còn học toán
winwave1995
#6
Đã gửi 03-08-2012 - 20:28
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
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
- hoangtrunghieu22101997 yêu thích
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!
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!
Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: psw
Toán Trung học Phổ thông và Thi Đại học →
Giải tích →
Tích phân - Nguyên hàm →
$\int f(\lfloor x\rfloor)dx…$Bắt đầu bởi hxthanh, 20-07-2022 psw |
|
|||
Toán thi Học sinh giỏi và Olympic →
Dãy số - Giới hạn →
Bài toán đáp lễ supermember $\mathbb{F}_n(x)=...$Bắt đầu bởi hxthanh, 13-07-2022 supermember, psw |
|
|||
Toán Trung học Phổ thông và Thi Đại học →
Đại số →
Tổ hợp - Xác suất và thống kê - Số phức →
$\sum_{k=1}^n k^n{n\choose k}=?$Bắt đầu bởi dark templar, 17-11-2012 psw |
|
|||
|
Cửa sổ Diễn Đàn Toán Học →
Những sự kiện đã kết thúc →
Thi đấu giải Toán →
Những bài toán trong tuần →
[Archive] Cập nhật list Những bài toán trong tuần (1 - 100)Bắt đầu bởi T*genie*, 30-07-2012 psw |
|
||
Toán Trung học Phổ thông và Thi Đại học →
Đại số →
Các bài toán Đại số khác →
Chứng minh rằng đồ thị hàm số sau có ba điểm uốn thẳng hàng: $y = \dfrac{{2x - 1}}{{x^2 - x + 1}}$Bắt đầu bởi Thanh Ha, 23-05-2009 psw |
|
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh