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

cho $p \in P $là tập các số nguyên tố .Tìm số $ n \in Z^{+}$ lớn nhất thỏa mãn các cạnh của 1 graph $n$ đỉnh có thể tô bằng $p+1$ màu thỏa mãn :
a)Có tối thiểu 2 cạnh khác màu .
b)Nếu $A,B,C$ là 3 đỉnh của graph thì nếu $AB,AC$ cùng màu thì $BC$ cùng màu .

ta chứng minh $N max =p^2$
ta định nghĩa tô màu 1 p-giác là tô màu tất cả các cạnh và các đường chéo của nó.
Đánh số màu từ $0 \to p$ ,đánh số các đỉnh như sau:
1,1 ; 1,2;......; 1,p
2,1 ; 2,2;......; 2,p
...
p,1 ; p,2;......; p,p
với màu thứ i (với $0\leq i\leq p-1$) ta tô như sau :
-p-giác thứ nhất 1,1 ; 2,1+i;.......;p,1+(p-1)i

-p-giác thứ 2: 1,2 ; 2,2+i;........;p,2+(p-1)i
-...
-p-giác thứ p : 1,p ; 2,p+i......... ;p,p+(p-1)i
riêng màu thứ p ta tô p -giác j,1 ; j,2;......; j,p với $0\leq j\leq p$
tiếp theo ta c/m ko còn cách tô khác thỏa mãn
do có p+1 màu nếu tồn tại p+1 giác to cùng 1 màu thì tồn tại 1 đỉnh khác (p+1) đỉnh đó nối với p+1 đỉnh này mà chỉ dc tô bởi p màu ( do trừ màu vừa tô) nên tồn tại 2 đỉnh cùng màu do đó tam giác có 2 cạnh cùng màu nhưng cạnh kia khác màu (><) như vậy trong cách tô thỏa mãn cho $p^2$ đỉnh thì đa giác lớn nhất tô 1 màu là có p đỉnh
Xét 1 màu bất kì ta tô 1 đa giác thì tô được tối đa $C^2_p$ cạnh mà từ p^2 đỉnh tạo ra được p đa giác -mỗi đa giác p đỉnh nên có tối đa là $p.C^2_p$ cạnh được tô 1màu.Lại có p+1 màu nên có $p(p+1)C^2_p$ cạnh được tô và bằng số cạnh có thể nói được của đa giác $p^2$đỉnh.Do đó cách tô với p^2 đỉnh duy nhất là với mầy j nhóm p nhóm ,mỗi nhóm p đỉnh tạo thành tô cùng màu j.

+)c/m p^2 là số lớn nhất có thể :
Nếu có lớn hơn hoặc bằng p^2+1 đỉnh .Xét đỉnh A bất kìvà p^2 đỉnh còn lại , từ A kẻ đến đỉnh B bất kì bởi màu j nào đó mà B luôn là đỉnh của p-giác nào đó tô bởi 1 màu j nên theo c/m ở trên thì từ A nối đến đỉnh bất kì nào của p-giác đều có màu j do đó tạo thành (p+1) giác được tô cùng 1 màu ( ><)
--> đpcm

bữa nay là 30/7 r�#8220;i mà có ít đội đăng kí thi nhỉ
Em đăng kí cho đội A1k35pbc
1) Nguyễn Tiến Chương (chuong_pbc) -- số học
2) Đinh Tuấn Đông (dtdong91)--rời rạc
3)Phan Phương Đức ( duca1pbc)--hình học
4) Phan Sỹ Quang ( quangpbc)--BDT-cực trị
5) Lê Tiến Nam(nam_pbc ) --Đại số -GT

Đội em xin được edit lại vì có 1 thành viên phản bội
) Nguyễn Tiến Chương (chuong_pbc) -- số học
2) Đinh Tuấn Đông (dtdong91)--rời rạc
3)Phan Phương Đức ( duca1pbc)--hình học
4) Nguyễn Phước Lộc(loc_vip) -BDT-cực trị
5) Lê Tiến Nam(nam_pbc ) --Đại số -GT

( mỗi phần chỉ mang tính chất tượng trưng )
@ quế gà :kẻ phản bội sẽ chịu hậu quả thích đáng, spam nhiều bài trên box này quá rồi đó

Em thấy cái này cũng giống như bản 5.6 , ko biết có đúng ko

Chủ đề về chị Tây này hot thật đó, anh nào cũng tham gia bình loạn nhiều thật