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

[dtdong91]

Trong mp cho 1 số điểm X Đ t.mãn
-1 điểm Đ được nối với ít nhất 1 điểm X
-1 điểm X nối với 1 hoặc 2 điểm Đ
CMR có thể xóa đi ko quá 1/2 số điểm sao cho sau khi xóa 1 điểm X được nối với đúng 1 điểm Đ

[chuong_pbc]

Lộc Vip xin trả lời :dễ cái kon khỉ! Chú làm được chưa. Sau đây anh bày cho chú nghen! (học tí tiếng miền Nam, híhí). Anh mới là đc tối ni đó.
Ta sẽ chứng minh bằng quy nạp.
Gọi số điểm là $M$.
Dễ thấy với $M $nhỏ thì thỏa mãn. Chú nào ko bít thì cứ vẽ hình ra mà xem nha .
Giả sử bài toán đúng đến $M = M_0$ .
+) Nếu $M_0 = 2k+1$ thì số điểm xóa nhìu nhất là $k$. Do đó với $M = M_0 + 1$ thì chỉ cần xóa điểm mới thêm vào thì số điểm xóa là $k+1$ còn tổng số điểm là $2k + 2$, thỏa mãn.
+) Nếu $M_0 = 2k$, ta sẽ chứng minh rằng số điểm xóa ít hơn$ k$ khi số điểm X khác số điểm Đ và nếu số điểmX bằng số điểm Đ thì luôn xóa được $k$ điểm.
Giả sử số điểm xóa là $k$ và không thể tìm được thêm điểm X (có thể cả Đ nữa) để thỏa mãn mỗi điểm X chỉ nối với một điểm Đ.
Điều kiện trên tương đương với 2 đk sau:
* Mọi điểm X đã xóa đều nối với 2 điểm Đ chưa xóa hoặc nối với 2 điểm Đ đã xoá
* Mọi điểm $D$ đã xóa nối đúng với 1 điểm $X$ chưa xóa và không có 2 điểm Đ nào cùng nối với một điểm X chưa xoá.
Gọi số điểm X xhưa xóa là , số điểm Đ chưa xóa là ta được + $=k$.Theo điều kiện sau của 2 đk trên thì số điểm Đ đã xóa bằng . Do đó số điểm X bằng số điểm Đ xét vào thời điểm ban đầu.
-) Nếu số điểm X khác số điểm Đ thì số điểm xóa $k-1$ nên khi thêm 1 điểm nữa ta chỉ cần xóa điểm vừa thêm thì tổng số điểm xóa là $k$ mà tổng số điểm là $2k+1$ nên thỏa mãn.
-) Nếu số điểm X bằng số điểm Đ, ta sẽ chứng minh rằng luôn có cách xóa không quá $k$ điểm.
Thật vậy, ta định nghĩa 1 đường nối là đoạn nối 1 điểm X với 1 điểm Đ. Theo đề ra thì trong trường hợp này có số đường nối lớn hơn hoặc bằng $k$ và nhỏ hơn hoặc bằng $2k$.
Do số điểm X bằng số điểm Đ nên có $k$ đường nối giữa 1 điểm X và 1 điểm Đ sao cho trong $k$ đường đó thì không có điểm nào cùng thuộc 2 đường.
Gọi số đường nối là $n$. Ta có k $n$ 2k. Ta quy nạp rằng với $n = k + x$ thì số điểm xóa không quá $x$.
Với $x = 0$ thì ko cần xoá.
Với $x = 1$ thì bằng hình vẽ ta có thẻ xóa 1 điểm.
Giả sử với $n = k + x$ ta xóa được $x$ điểm và các điểm sau khi xóa thỏa mnã bài toán. Nếu có thêm 1 đường nối nữa thì số điểm xóa cho phép là $x+1$. Ta chỉ cần xét trường hợp đuờng nối đó nối với điểm $ X_0 $ và $ D_0 $mà hai điểm này ko bị xóa khi số đường nối là $k+x$
Điểm mà $ X_0 $ nối khi số đường nối là $k+x$ là $D_1$.
Nếu điểm $ D_1 $ đã nối với điểm $X$ khác điểm $X_0$ thì ta sẽ xóa điểm $ X_0 $.
Nếu điểm $ D_1 $ ko nối với điểm nào khác điểm $X_0$ thì xóa điểm $ D_1 $.
Nghĩa là trong trường hợp số đường nối nhỏ hơn $2k$ thì ta chỉ cần xóa $k-1$ điểm. Lúc đó với $M=M_0 +1$ thì bài toán đúng. Trong trường hợp số đỉêm nối là $2k$ thì chỉ có thể thêm vào 1 điểm $X$. Dễ thấy lúc này thì $2k$ điểm ban đầu điểm $X$ nào cũng được nối 2 lần nên có thể chọn được $k $điểm để xoá.
Bài này anh làm như vậy, ko bít có chỗ mô chưa đúng
Đ?#8220;ng chí nào dân Phan có thắc mắc gì gọi điện cho anh LỘC VIP nha

Bài viết đã được chỉnh sửa nội dung bởi chuong_pbc: 11-09-2007 - 21:45

[chuyentoan]

Hơ hơ, nhớ lại ngày xưa thầy Khắc Minh dạy anh với anh Quý bài này. He he, cần gì phải khó nhọc thế

[tanlsth]

Ngày xưa khi bọn em đi học thầy Khắc Minh cũng tương bài này vào luôn,cả đội ngồi trên giường để học
Cách giải là xét các khả năng rồi dùng nguyên lí Đirichle là xong
Ngắn gọn và đơn giản hơn nhiều.Với cách làm của em mà gặp thầy ấy thì kiểu gì cũng bị vặn vẹo và lục các trường hợp ra và cuối cùng là thầy bảo về chỗ và nói chung là thầy không chấp nhận lời giải đó

[vnm]

bài này trước mình post lời giải 1 lần rồi,ý là xét 1 tập điểm đỏ bất kì và xét tập tương ứng các điểm xanh nối với đúng 1 điểm đỏ trong tập đó.Ta xét tổng số phần tử tập xanh xác định như trên với các tập điểm đỏ bất kì rồi dùng dirichle.Bài tổng quát là bài thi nga 1999

[chicken_1991]

Các anh post lời giải và bài tổng quát đi ạ .Em gà lắm không hiểu thế nào. Chú Lộc giải cách kinh quá

[thanhvienmoi]

tình hình bên ấy thế nào?nghe bảo kiểm tra nghiêm túc lắm à lớp chị thì ko kiểm tra, thầy lấy luôn(có muốn xin ra cung ko được) :cry :cry :cry

[PLURIREGULAR]

tình hình bên ấy thế nào?nghe bảo kiểm tra nghiêm túc lắm à lớp chị thì ko kiểm tra, thầy lấy luôn(có muốn xin ra cung ko được) :cry :cry :cry

vi lop ay gioi rui. ko can kiem tra cung co the chon duoc. con lop nay kiem tra mai ma ko chon duoc. Vi bai kt nao cung let det ca!. hen nam sau vay!hehe

[chicken_1991]

Còn bài này em cũng vạch ra xét các Th của điểm Đ r?#8220;i sau cũng n/xét ,biện luận lung tung hết ,thấy nó cũng dễ dễ nên nói chơi vậy thui

dtdong91 nên thận trọng khi bình luận bài nha
Có làm được đâu mà khệnh khạng, chỉ là chắp bu tí, lời giải đâu, biện luận như thế nào, có mà làm , hí hí
Đừng lên mặt dạy đời nghe chưa Sơn con.

p/s:hơi quá lời rồi đấy!

Bài viết đã được chỉnh sửa nội dung bởi LvanhTuan: 24-09-2007 - 13:13