Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Sơ Cấp > Việt Nam và IMO > 2012

News & Announcements

Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé !

* Nội quy MathScope.Org

* Một số quy định chung !

* Quy định về việc viết bài trong diễn đàn MathScope

* Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 18-04-2012, 08:31 AM   #31
Mr Stoke
+Thành Viên Danh Dự+
 
Mr Stoke's Avatar
 
Tham gia ngày: Dec 2007
Bài gởi: 252
Thanks: 40
Thanked 455 Times in 95 Posts
Bài 6 hệ quả trực tiếp từ định lý Bondy . Đầu tiên chọn ra 40 hs ta được 1 chu trình Hamiton. Chia 2 trường hợp: 2 hs còn lại quen nhau => xong. Nếu không quen thì 40 hs đó hợp hai hs thừa lập thành chu trình Hamiton.

Bài 3 khá hay, không bạn nào quan tâm à?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Mr Stoke is offline   Trả Lời Với Trích Dẫn
Old 18-04-2012, 10:55 AM   #32
VengefulSpirit
+Thành Viên+
 
VengefulSpirit's Avatar
 
Tham gia ngày: Jan 2012
Đến từ: ĐHSP Hà Nội, nhưng sau này sẽ là CHV
Bài gởi: 15
Thanks: 0
Thanked 6 Times in 6 Posts
Trích:
Nguyên văn bởi Mr Stoke View Post
Bài 3 khá hay, không bạn nào quan tâm à?
Bài này mình làm nhưng theo hướng khá đơn giản và ngắn nên ko ro đúng ko,bạn có thế post lời giải lên đc không?
Xét $ax+by+cz+d\equiv 0 $( mod p)
$\Leftrightarrow (y-x)b+(z-x)c\equiv -d $(mod p)
$ \Leftrightarrow mb+cn\equiv -d $ (mod p)$m,n\in \left \{ \left \lfloor \frac{p}{3}-1,..1-\left \lfloor \frac{p}{3} \right \rfloor \right \rfloor \right \} $
$b^{-1}bm+ncb^{-1}\equiv db^{-1} $(mod p)
$nx\equiv y-m $ (mod p)
$nx\equiv t $(mod p)
Trong đó n,ttnhận $2\left \lfloor \frac{p}{3} \right \rfloor-1 $
giá trị mà
$2(2\left \lfloor \frac{p}{3} \right \rfloor-1)>p $ với p>17 nên dễ chọn được n,z thỏa mãn vậy t=3 thỏa mãn,
với t>3 ta chọn a,b,c,d hoặc làm tiếp theo hướng kia hình như cũng được
Một số chỗ hơi tắt các bạn thông cảm!
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
첸옥 H

thay đổi nội dung bởi: VengefulSpirit, 18-04-2012 lúc 06:09 PM
VengefulSpirit is offline   Trả Lời Với Trích Dẫn
Old 18-04-2012, 11:57 AM   #33
ductho
+Thành Viên+
 
Tham gia ngày: Nov 2010
Bài gởi: 9
Thanks: 12
Thanked 1 Time in 1 Post
Mr Stoke là thầy đấy bạn ơi!
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
ductho is offline   Trả Lời Với Trích Dẫn
Old 18-04-2012, 01:35 PM   #34
namdung
Administrator

 
Tham gia ngày: Feb 2009
Đến từ: Tp Hồ Chí Minh
Bài gởi: 1,341
Thanks: 209
Thanked 4,062 Times in 777 Posts
Gửi tin nhắn qua Yahoo chát tới namdung
Trích:
Nguyên văn bởi Mr Stoke View Post
Bài 6 hệ quả trực tiếp từ định lý Bondy . Đầu tiên chọn ra 40 hs ta được 1 chu trình Hamiton. Chia 2 trường hợp: 2 hs còn lại quen nhau => xong. Nếu không quen thì 40 hs đó hợp hai hs thừa lập thành chu trình Hamiton.
Chỗ này không đơn giản như thế. Nếu chọn 40 học sinh chưa chắc đã có chu trình Hamilton. Phản ví dụ: Hai đồ thị $K_{21} $ rời nhau.

Bài này đúng là có liên quan đến các định lý Dirac, Ore, Bondy-Chvatal nhưng phải xem kỹ lại các chứng minh để xử lý việc "thiếu 1 chút".
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
namdung is offline   Trả Lời Với Trích Dẫn
Old 18-04-2012, 02:21 PM   #35
vulalach
+Thành Viên+
 
Tham gia ngày: May 2009
Bài gởi: 20
Thanks: 30
Thanked 36 Times in 13 Posts
Vậy bài này nếu xét trường hợp có hai thành phần liên thông thì suy ra mỗi thành phần liên thông là K21 đầy đủ, còn nếu G liên thông thì chứng minh có chu trình Hamilton, hướng đi vậy đúng ko thầy?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
vulalach is offline   Trả Lời Với Trích Dẫn
Old 18-04-2012, 04:29 PM   #36
LTNL
+Thành Viên+
 
LTNL's Avatar
 
Tham gia ngày: Jan 2012
Đến từ: Khu Rồng Thiên
Bài gởi: 10
Thanks: 0
Thanked 10 Times in 3 Posts
Trích:
Bài 6: Giả sử ko có cách chia 2 nhóm. Ban đầu ta chia các thí sinh đó thành các nhóm gồm hai thành viên và hai thí sinh đó phải quen nhau. Gọi tập các nhóm là S. Nếu S có đủ 21 nhóm thì ta đc đpcm. Xét trường hợp S có ít hơn 21 nhóm và các thí sinh ko thuộc S ko thể tạo nên1 cặp vs thí sinh khác để thuộc S. Thì ta xét thí sinh b thuộc S quen với a ko thuộc S mà người thuộc nhóm vs b trong S là c cũng quen vs d ko thuộc S thì ta chỉ cần cho a và b, c và d thành 1 cặp. Cách chọn này luôn tồn tại vì số người quen cuả mỗi người là 20 mà số nhóm trong S nhỏ hơn hoặc bằng 20. Như thế sau mỗi lần thực hiện số người ko thuộc S giảm đi 2. Mà số người ko thuộc S ko âm nên qúa trình này phải dừng. Vì ta giả sử ko có cách chia 2 nhóm tức là tập đỉnh của đồ thị này ko thể chia làm 2 thành phần đày đủ 21 phần và ko có cầu, nên quá trình này ko thể dừng ở 2.Vì nếu nó dừng ở 2 thì do trong S có 20 cặp . Và bậc đỉnh mỗi đỉnh là 20 nên theo định lí Turản ta suy ra được trong S chứa tập đầy đủ 20 đỉnh.. và 20 đỉnh còn lại cũng tạo thành 1 tập đầy đủ. Do đó 2 đỉnh ko thuộc S sẽ phải lần lượt thuộc 2 tập này lúc đó tạo ra 2 nhóm thỏa mãn ( mâu thuẫn với điều giả sử) vậy phải dừng ở 0. Lúc này ta có 21 tập thỏa mãn
Một bài giải của bạn The Gunner bên VMF, ko biết có đúng ko
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
LTNL is offline   Trả Lời Với Trích Dẫn
Old 18-04-2012, 05:20 PM   #37
namdung
Administrator

 
Tham gia ngày: Feb 2009
Đến từ: Tp Hồ Chí Minh
Bài gởi: 1,341
Thanks: 209
Thanked 4,062 Times in 777 Posts
Gửi tin nhắn qua Yahoo chát tới namdung
Trích:
Bài 6: Giả sử ko có cách chia 2 nhóm. Ban đầu ta chia các thí sinh đó thành các nhóm gồm hai thành viên và hai thí sinh đó phải quen nhau. Gọi tập các nhóm là S. Nếu S có đủ 21 nhóm thì ta đc đpcm. Xét trường hợp S có ít hơn 21 nhóm và các thí sinh ko thuộc S ko thể tạo nên1 cặp vs thí sinh khác để thuộc S. Thì ta xét thí sinh b thuộc S quen với a ko thuộc S mà người thuộc nhóm vs b trong S là c cũng quen vs d ko thuộc S thì ta chỉ cần cho a và b, c và d thành 1 cặp. Cách chọn này luôn tồn tại vì số người quen cuả mỗi người là 20 mà số nhóm trong S nhỏ hơn hoặc bằng 20. Như thế sau mỗi lần thực hiện số người ko thuộc S giảm đi 2. Mà số người ko thuộc S ko âm nên qúa trình này phải dừng. Vì ta giả sử ko có cách chia 2 nhóm tức là tập đỉnh của đồ thị này ko thể chia làm 2 thành phần đày đủ 21 phần và ko có cầu, nên quá trình này ko thể dừng ở 2.Vì nếu nó dừng ở 2 thì do trong S có 20 cặp . Và bậc đỉnh mỗi đỉnh là 20 nên theo định lí Turản ta suy ra được trong S chứa tập đầy đủ 20 đỉnh.. và 20 đỉnh còn lại cũng tạo thành 1 tập đầy đủ. Do đó 2 đỉnh ko thuộc S sẽ phải lần lượt thuộc 2 tập này lúc đó tạo ra 2 nhóm thỏa mãn ( mâu thuẫn với điều giả sử) vậy phải dừng ở 0. Lúc này ta có 21 tập thỏa mãn
Lời giải này cũng có vấn đề. Chẳng hạn không hiểu làm thế nào mà áp dụng định lý Turan lại suy ra được S có chứa $K_{20} $.
------------------------------
Trích:
Nguyên văn bởi vulalach View Post
Vậy bài này nếu xét trường hợp có hai thành phần liên thông thì suy ra mỗi thành phần liên thông là K21 đầy đủ, còn nếu G liên thông thì chứng minh có chu trình Hamilton, hướng đi vậy đúng ko thầy?
Có lẽ đây là hướng đi đúng.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: namdung, 18-04-2012 lúc 05:23 PM Lý do: Tự động gộp bài
namdung is offline   Trả Lời Với Trích Dẫn
Old 18-04-2012, 06:42 PM   #38
pth_tdn
+Thành Viên+
 
Tham gia ngày: Dec 2009
Đến từ: HCM City
Bài gởi: 183
Thanks: 25
Thanked 240 Times in 122 Posts
Bài 3 em có lời giải như sau:
*Cho $b=c=1, a=p-2 $. Ta có:
$ax+by+cz \equiv y+z-2x $ phải lập thành một hệ thặng dư đầy đủ mod p.
Mà $-2([\frac{p}{t}]-1) \leq y+z-2x \leq 2([\frac{p}{t}]-1) $ nên ta có $4[\frac{p}{t}]+1 \geq p+1 \Rightarrow [\frac{p}{t}] \geq \frac{p}{4} \Rightarrow t<4 $.
*Với $t=3 $: Ta sẽ chứng minh $ax+by+cz $ có thể nhận bất kì số dư nào khi chia cho p.
$ax+by+cz \equiv b(y-x)+c(z-x) (mod p) $.
Gọi $x_0, y_0, gcd(x_0,y_0)=1 $ thỏa $x_0b \equiv y_0c $, chứng minh được $(x_0,y_0) $ tồn tại duy nhất.
Và $x_1b+y_1c \equiv x_2b+y_2c \Leftrightarrow x_1-x_2=tx_0, y_2-y_1}=ty_0 $.
Khi đó, số cặp $(x_1,y_1), (x_2,y_2) $ thỏa điều trên là nhiều nhất khi $x_0=y_0=1 $, tức là số các số đồng dư nhau theo mod p trong tập $mb+nc $ là nhiều nhất, hay các số dư phân biệt khi chia cho p của tập là $mb+nc $ là ít nhất (chú ý rằng số phần tử của tập $b(y-x)+c(z-x) $ là không đổi khi b,c thay đổi (x,y,z thuộc ${0;1;...;[\frac{p}{t}]-1 $) ) khi $x_0=y_0=1 $.
Ta chứng minh rằng khi đó, tập $ax+by+cz $ vẫn có thể lập thành hệ thặng dư đầy đủ mod p.
Thật vậy: Trong trường hợp đó $ax+by+cz \equiv b(y+z-2x) (mod p) $.
Chú ý rằng $gcd(b,p)=1, -2([\frac{p}{t}]-1) \leq y+z-2x \leq 2([\frac{p}{t}]-1) $ và $[-2([\frac{p}{t}]-1); 2([\frac{p}{t}]-1) ] $ chứa nhiều hơn p số nguyên khi $p>9 $, ta có điều cần chứng minh.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
pth_tdn is offline   Trả Lời Với Trích Dẫn
The Following 2 Users Say Thank You to pth_tdn For This Useful Post:
gomis (22-04-2012), huynhcongbang (20-04-2012)
Old 18-04-2012, 06:58 PM   #39
chemthan
Super Moderator
 
chemthan's Avatar
 
Tham gia ngày: Mar 2009
Bài gởi: 341
Thanks: 0
Thanked 297 Times in 153 Posts
Trích:
Nguyên văn bởi VengefulSpirit View Post
Bài này mình làm nhưng theo hướng khá đơn giản và ngắn nên ko ro đúng ko,bạn có thế post lời giải lên đc không?
Xét $ax+by+cz+d\equiv 0 $( mod p)
$\Leftrightarrow (y-x)b+(z-x)c\equiv -d $(mod p)
$ \Leftrightarrow mb+cn\equiv -d $ (mod p)$m,n\in \left \{ \left \lfloor \frac{p}{3}-1,..1-\left \lfloor \frac{p}{3} \right \rfloor \right \rfloor \right \} $
$b^{-1}bm+ncb^{-1}\equiv db^{-1} $(mod p)
$nx\equiv y-m $ (mod p)
$nx\equiv t $(mod p)
Trong đó n,ttnhận $2\left \lfloor \frac{p}{3} \right \rfloor-1 $
giá trị mà
$2(2\left \lfloor \frac{p}{3} \right \rfloor-1)>p $ với p>17 nên dễ chọn được n,z thỏa mãn vậy t=3 thỏa mãn,
với t>3 ta chọn a,b,c,d hoặc làm tiếp theo hướng kia hình như cũng được
Một số chỗ hơi tắt các bạn thông cảm!
Sai rồi. Chỗ $m,n\in \left \{ \left \lfloor \frac{p}{3}\right \rfloor-1,..1-\left \lfloor \frac{p}{3} \right \rfloor \right \} $ phải thêm $m-n\in \left \{ \left \lfloor \frac{p}{3}\right \rfloor-1,..1-\left \lfloor \frac{p}{3} \right \rfloor \right \} $ nữa.

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: chemthan, 18-04-2012 lúc 07:05 PM
chemthan is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to chemthan For This Useful Post:
huynhcongbang (20-04-2012)
Old 18-04-2012, 08:04 PM   #40
VengefulSpirit
+Thành Viên+
 
VengefulSpirit's Avatar
 
Tham gia ngày: Jan 2012
Đến từ: ĐHSP Hà Nội, nhưng sau này sẽ là CHV
Bài gởi: 15
Thanks: 0
Thanked 6 Times in 6 Posts
Trích:
Nguyên văn bởi chemthan View Post
Sai rồi. Chỗ $m,n\in \left \{ \left \lfloor \frac{p}{3}\right \rfloor-1,..1-\left \lfloor \frac{p}{3} \right \rfloor \right \} $ phải thêm $m-n\in \left \{ \left \lfloor \frac{p}{3}\right \rfloor-1,..1-\left \lfloor \frac{p}{3} \right \rfloor \right \} $ nữa.
Chắc bạn nói đến Đl Cauchz-Davenport nhưng định lý này cao cấp va phải động chạm đên Zp nên không hay lắm.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
첸옥 H
VengefulSpirit is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to VengefulSpirit For This Useful Post:
gomis (22-04-2012)
Old 18-04-2012, 08:10 PM   #41
chemthan
Super Moderator
 
chemthan's Avatar
 
Tham gia ngày: Mar 2009
Bài gởi: 341
Thanks: 0
Thanked 297 Times in 153 Posts
Trích:
Nguyên văn bởi VengefulSpirit View Post
Chắc bạn nói đến Đl Cauchz-Davenport nhưng định lý này cao cấp va phải động chạm đên Zp nên không hay lắm.
Uh, có dùng thì cũng chưa chắc giải ra.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
chemthan is offline   Trả Lời Với Trích Dẫn
Old 18-04-2012, 08:29 PM   #42
lethanhtu
+Thành Viên+
 
Tham gia ngày: Jan 2012
Đến từ: THPT chuyên Lý Tự Trọng Cần Thơ
Bài gởi: 4
Thanks: 0
Thanked 3 Times in 1 Post

Cách giải khác cho bài 1:
Xét bổ đề: Trên đường tròn (O) cho dây cung BC và một điểm A di động trên (O). Gọi D là trung điểm BC, đường tròn (O') đường kính AD cắt cạnh AB, AC tại E,F. Tiếp tuyến của (O') tại E, F cắt nhau tại T. Chứng minh T cố định.
Chứng minh
Gọi M, N là trung điểm BD, DC; ta có đường tròn đường kính BD đi qua E và đường tròn đường kính CD đi qua F.
Ta có \[\widehat{MET} = \widehat{MEB} - ({180^0} - \widehat{AET}) = \widehat{MBE} + \widehat{AET} - {180^0}\]
tương tự \[\widehat{NET} = {180^0} - \widehat{AFT} - \widehat{NCF}\]
ta lại có: \[\widehat{MBE} + \widehat{AET} - {180^0} = {180^0} - \widehat{AFT} - \widehat{NCF}\]
hay \[\widehat{AET} + \widehat{AFT} + 180 - \widehat{BAC} = 360\]
hay \[\widehat{AET} - \widehat{O'EA} + \widehat{AFT} - \widehat{O'FA} = 180\] (đúng do tứ giác O'ETF nội tiếp) suy ra
\[\widehat{MET} = \widehat{NET}\]
Suy ra tam giác MET= tam giác NET
Suy ra TM=TN => TD vuông góc với BC
Ta lại có $P_{T/(M)}=TB^2-DB^2$ ; $P_{T/(O)}=TO^2-BO^2$
Như vậy nếu ta chúng minh đc $P_{T/(M)}=P_{T/(O)}$
Thì ta có thể kết luận rằng T là giao của trung trực BC và trục đẳng phương của (O) và (M), và do đó T cố định. Ta chứng minh cho $P_{T/(M)}=P_{T/(O)}$ (1) , thật vậy:
(1) <=> $TO^2-BO^2=TB^2-DB^2$ <=> $TO^2-TB^2=BO^2-DB^2$
<=> $TO^2=OD^2+TB^2$ <=> $(OD+DT)^2=OD^2+DT^2+DB^2$
<=> $DB^2=2DO.DT$ (2)
Gọi G là trung điểm của OD thì (2) <=> $DG.DT=DM^2$ <=> tam giác MGT vuông tại M
<=> \[\widehat{MGD} + \widehat{MTD} = {90^0} < = > \widehat{BAC} + \frac{1}{2}\widehat{MTN} = {90^0}\]
<=> \[\frac{1}{2}\widehat{EO'F} + \frac{1}{2}\widehat{ETF} = {90^0}\] (đúng)
Áp dụng bổ đề trên cho tam giác HBC với H là trực tâm tam giác ABC và để ý rằng đường tròn ngoại tiếp tam giác HBC cố định, ta có đpcm
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: lethanhtu, 18-04-2012 lúc 10:22 PM
lethanhtu is offline   Trả Lời Với Trích Dẫn
The Following 3 Users Say Thank You to lethanhtu For This Useful Post:
AnhIsGod (18-04-2012), huynhcongbang (19-04-2012), pqhoai (18-04-2012)
Old 18-04-2012, 09:08 PM   #43
Traum
Moderator
 
Traum's Avatar
 
Tham gia ngày: Nov 2007
Đến từ: cyber world
Bài gởi: 413
Thanks: 14
Thanked 465 Times in 170 Posts
Trích:
Nguyên văn bởi chemthan View Post
Nếu sử dụng định lý Cauchy-... gì đó thì chứng mình số các số dư ít nhất là $3*\left \lfloor \frac{p}{3} \right \rfloor-2 $, nhưng chưa sử dụng điều kiện $a+b+c\vdots p $
Cái này chỉ đúng nếu $a,b,c $ khác nhau.

Ta có thể giải quyết như sau:

Kí hiệu $S = \left\{0,1,...,\left[\frac{p}{3}\right]-1\right\} $

Trường hợp 1: 2 trong 3 số $a,b,c, $ bằng nhau theo mod p ( tất nhiên sẽ khác với số còn lại). Giả sử $a = b $

Ta có $ax+by+cz+d\equiv a(x+y)-2az +d \equiv a(x+y-2z) + d\pmod p $.

Ta sẽ phải chứng minh tập $X = \{x+y-2z|x,y,z\in S\} $ là một hệ thặng dư đầy đủ mod p. (dễ chứng minh)

Trường hợp 2: 3 số $a,b,c $ khác nhau và khác 0 theo mod p

Xét tập $A = \{0,a,b,c\} $ thì $|A| = 4 $. Theo định lý Cauchy-Davenport thì tập $S(A) = \{ax+by+cz|x,y,z\in S\} $ có ít nhất là $\min\{p,4\left\lfloor\frac{p}{3}\right\rfloor-3\} $ phần tử khác nhau theo mod p.

Với $p\ge 17 $ thì $4\left\lfloor\frac{p}{3}\right\rfloor-3\ge p $ nên ta có S(A) là một hệ thặng dư đầy đủ mod p. Do đó với $t = 3 $ thì tồn tại $x,y,z $ thỏa mãn.

Với $t = 4 $ thì cũng có thể chỉ ra được $a,b,c,d $ sao cho không tồn tại $x,y,z $ thỏa mãn ( ví dụ $a = b = 1, c = p-2 $ và $d = \frac{p+1}{2} $
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Traum is giấc mơ.

thay đổi nội dung bởi: Traum, 18-04-2012 lúc 09:10 PM
Traum is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to Traum For This Useful Post:
huynhcongbang (20-04-2012)
Old 18-04-2012, 09:31 PM   #44
Làng Sình
+Thành Viên+
 
Tham gia ngày: Nov 2011
Bài gởi: 6
Thanks: 1
Thanked 1 Time in 1 Post
Trích:
Nguyên văn bởi Traum View Post

Trường hợp 2: 3 số $a,b,c $ khác nhau và khác 0 theo mod p

Xét tập $A = \{0,a,b,c\} $ thì $|A| = 4 $. Theo định lý Cauchy-Davenport thì tập $S(A) = \{ax+by+cz|x,y,z\in S\} $ có ít nhất là $\min\{p,4\left\lfloor\frac{p}{3}\right\rfloor-3\} $ phần tử khác nhau theo mod p.
Bạn xem lại chổ này giùm, nó đâu có đúng theo đinh lý Cauchy-Davenport ở đây:
Trích:
Let t be a nonnegative integer and let $x_1, ..., x_t$ be nonzero elements of $Z_p$ which are not necessarily distinct. Then the number of elements of $Z_p$ that can be written as the sum of some subset (possibly empty) of the $x_i$ is at least $\min\{p,t+1\}$. In particular, if $t>=p-1$, then every element of $Z_p$ can be so written.
Xem thêm ở đây: [Only registered and activated users can see links. ]
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Làng Sình is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to Làng Sình For This Useful Post:
huynhcongbang (20-04-2012)
Old 18-04-2012, 09:35 PM   #45
Traum
Moderator
 
Traum's Avatar
 
Tham gia ngày: Nov 2007
Đến từ: cyber world
Bài gởi: 413
Thanks: 14
Thanked 465 Times in 170 Posts
Trích:
Nguyên văn bởi namdung View Post
Lời giải này cũng có vấn đề. Chẳng hạn không hiểu làm thế nào mà áp dụng định lý Turan lại suy ra được S có chứa $K_{20} $.
------------------------------
Có lẽ đây là hướng đi đúng.
Hướng đó em tin là khá phức tạp, mặc dù các điều kiện bài toán rất gần với các điều kiện để sử dụng các định lý trên nhưng để xử lý cái "một tí còn thiếu" sẽ không dễ chút nào.


Một hướng khác là sử dụng định lý Tutte cho đồ thị có perfect matching.

Chú ý: Lời giải cho bài toán trong cuộc thi chắc chắn sẽ đơn giản hơn rất nhiều so với ở đây!!!


Trường hợp 1: Đồ thị không liên thông

Có ít nhất là 2 thành phần liên thông rời nhau, do bậc mỗi đỉnh là 20 nên chỉ có duy nhất một đồ thị thỏa mãn là hợp của 2 $K_{21} $ rời nhau.

Trường hợp 2: Đồ thị liên thông
Xem [Only registered and activated users can see links. ], cho các định nghĩa và kí hiệu.

Giả sử không có perfect matching, khi đó theo định lý Tutte tồn tại một tập các đỉnh $U $ sao cho $odd(G-U)>|U| $.

Đặt $|U| = k $ và $odd(G-U) = q $, gọi các thành phần liên thông có lẻ đỉnh đó là $A_{1},...,A_{q} $.

Tổng số đỉnh trong đồ thị là $42 \equiv |A_{1}|+...+|A_{q}| + |U| \pmod 2 $. Do $|A_{i}| $ lẻ nên ta có $q + k \equiv 0 \pmod 2 $.

Ở trên ta giả sử $q>k $ nên $q\ge k+2 $.

Gọi $t_i $ là số cạch có một đầu thuộc $U $ và một đầu thuộc $A_{i} $. Do đồ thị liên thông nên $t_i\ge 1 $.

Tổng số bậc của các đỉnh nằm trong $U $ là $20k\ge\sum\limits_{i=1}^{q}t_i $. Vì $q\ge k+2 $ nên phải có ít nhất là 3 chỉ số $i $ sao cho $t_i<20 $. Giả sử $t_1,t_2,t_3 \le 19 $. Do bậc mỗi đỉnh là 20 nên ta có $|A_1|,|A_2|,|A_3| >1 $ và do chúng lẻ nên $\ge 3 $.

Do $|A_1|+|A_2|+|A_3|\le 42-k $ nên ta có giả sử $|A_1|\le 13 $

Đặt $a = |A_1|\le 13 $. Tổng số bậc của các đỉnh trong $A_1 $ không quá $a(a-1) + t_1 $, mà mỗi đỉnh có bậc là 20 nên $a(a-1)+t_1\ge 20a $. Ở trên ta có $t_1\le 19 $ nên $a(a-1)+20>20a $ do đó $a(a-1)>20(a-1) $ hay $a>20 $ mâu thuẫn.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Traum is giấc mơ.
Traum is offline   Trả Lời Với Trích Dẫn
The Following 3 Users Say Thank You to Traum For This Useful Post:
chemgiodaihiep (18-04-2012), huynhcongbang (20-04-2012), thefallen (18-04-2012)
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT. Hiện tại là 03:28 AM.


Powered by: vBulletin Copyright ©2000-2018, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 116.97 k/133.57 k (12.43%)]