Đã gửi bởi
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
