Đến nội dung

Hình ảnh

Trận 3 - Tổ hợp rời rạc


  • Chủ đề bị khóa Chủ đề bị khóa
Chủ đề này có 27 trả lời

#21
E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản lý Toán Phổ thông
  • 3861 Bài viết

Đã kết thúc trận đấu, mời các toán thủ nhận xét bài làm của nhau


  • LNH yêu thích

1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#22
gk25dtm

gk25dtm

    Binh nhất

  • Thành viên
  • 37 Bài viết

Gọi A là thành phố có nhiều đường đi nhất.

Khi đó ta chia các thành phố còn lại thành 3 nhóm sao cho:

+Nhóm 1: có đường đi xuất phát từ A 

+Nhóm 2: có đường đi đến A

+Nhóm 3:không có đường đi đến A hoặc xuất phát từ A

Gọi $a$ là số thành phố của nhóm 1

       $b$ là số thành phố của nhóm 2

       $c$ là số thành phố của nhóm 3

Khi đó ta có $a+b+c=209$

Theo giả thiết thì không có đường đi giữa các thành phố trong nhóm và nhóm 2

Số các đường đi liên quan đến các thành phố nhóm 3 không vượt quá c(a+b) (Do bậc của $A=a+b$ lớn nhất)

Khi đó tổng số đường đi bao gồm:

+Số đường đi liên quan đến A: $a+b$

+Số đường đi liên quan đến các thành phố trong nhóm 3: $\leq c(a+b)$ 

+Số đường đi giữa nhóm 1 và 2: $\leq a.b$

Suy ra tổng số đường đi nhỏ hơn:

$ab+a+b+c(a+b)=ab+a(c+1)+b(c+1) \geq \frac{(a+b+c+1)^2}{3}=\frac{210^2}{3}$ (Theo AM-GM)

Dấu "=" xảy ra khi đồ thị có 3 nhóm, mỗi nhóm có 70 thành phố, thành phố nhóm 1 có đường đi đến thành phố nhóm 2, thành phố nhóm 2 có đường đi đến thành phố nhóm 3,thành phố nhóm 3 có đường đi đến thành phố nhóm 1 

chỗ tô đỏ nhầm dấu 



#23
gk25dtm

gk25dtm

    Binh nhất

  • Thành viên
  • 37 Bài viết

Quy ước : đường xuất phát từ thành phố X đến thành phố Y gọi là đường đi đối với thành phố X và là đường kết đối với thành phố Y ( X đi , Y kết ) .

 

Lời giải :

Ta xét thành phố H có nhiều đường đi nhất ( giả sử có $x$ đường đi và $y$ đường kết thì có $x$ thành phố kết , $y$ thành phố đi) .

Theo giả thiết thì trong hai thành phố bất kỳ mà H đi  ( hoặc kết ) thì không có con đường nào nối .

Chọn một thành phố mà H đi và một thành phố mà H kết thì giữa chúng có thể có ( một và chỉ một ) đường nối nên số đường nhiều nhất tạo được là $xy$ .

Bây giờ ta xét một trong $z$ thành phố mà không có đường đi và kết H thì có thể xây tối đa $x+y$ đường nối nên số đường nhiều nhất là $z(x+y)$

Tổng số đường xây nhiều nhất là $A=x+y+xy+z(x+y)$ và thêm đó $x+y+z+1=210$

Theo BDT quen thuộc : $A=xy+y(z+1)+(z+1)x\leq \frac{(x+y+z+1)^2}{3}=\frac{210^3}{3}$

Dấu bằng xảy ra với cách xây như sau : có 3 nhóm thành phố A,B,C , mỗi nhóm 70 . Mối thành phố ở nhóm A có đường đi tới thành phố nhóm B , mối thành phố ở nhóm B có đường đi tới mỗi thành phố nhóm C và mối thành phố ở nhóm C có đường đi tới thành phố nhóm A .

chỗ tô đỏ sai



#24
anhminhkhon

anhminhkhon

    Hạ sĩ

  • Thành viên
  • 99 Bài viết
Ví dụ 13. (Trận đấu toán học Nga 2010) Một quốc gia có 210 thành phố. Ban đầu giữa 
các thành phố chưa có đường. Người ta muốn xây dựng một số con đường một chiều nối  
giữa các thành phố sao cho: Nếu có đường đi từ A đến B và từ B đến C thì không có 
đường đi từ A đến C.Hỏi có thể xây dựng được nhiều nhất bao nhiêu đường?

lời giải đầy đủ ở đây

http://vie.math.ac.v..._Ly_Cuc_Han.pdf

 


Bài viết đã được chỉnh sửa nội dung bởi anhminhkhon: 11-02-2014 - 21:18


#25
TRONG TAI

TRONG TAI

    Trọng tài MO2014

  • Thành viên
  • 38 Bài viết

Vì đề ra lần này trùng với một đề thi HSG cấp tỉnh trở lên của Nga nên BTT quyết định như sau:

- Mọi toán thủ tham gia có lời giải giống hoặc tương tự lời giải tại http://vie.math.ac.v...Ly_Cuc_Han.pdf đều không tính điểm. Chỉ những toán thủ có mở rộng, giải cách khác cho bài toán sẽ được tính điểm, theo quy tắc tính điểm cho mở rộng, lời giải mới.
- Riêng toán thủ ra đề sẽ bị trừ nửa số điểm.


1) Hãy tham gia các cuộc thi dành cho THCS, THPT, Olympic
2) Tham gia gameshow toán học PSW tại đây
3) Học gõ công thức toán tại:
http://diendantoanho...oạn-thảo-latex/
4) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...

#26
Near Ryuzaki

Near Ryuzaki

    $\mathbb{NKT}$

  • Thành viên
  • 804 Bài viết
Trên hết , em xin có ý kiến như sau :
_Thứ nhất , việc BTC kỉ luật đối với toán thủ ra đề là vô lý , tại sao chứ ? Chẳng lẽ ra đề là phải tự nghĩ ra sao ? Thậm chí lỡ bản thân người ra đề ( anh LNH) cũng không biết đó là đề thi HSG tỉnh ở Nga mà chỉ tham khảo ở 1 tư liệu nào đó thì sao ? Việc tham khảo này có lẽ không sai luật chứ?
_ Thứ hai , chuyện các toán thủ có lời giải giống nhau và giống trong tư liệu đó là chuyện bình thường , chắc hẳn trong các kì thi HSG cũng sẽ có trường hợp này ! Nên việc BTC đưa ra quyết định không tính điểm là không có cơ sở, căn cứ ạ !
P/s: Em chỉ có ý kiến như vậy thôi ạ !

#27
gk25dtm

gk25dtm

    Binh nhất

  • Thành viên
  • 37 Bài viết

tóm lại là điểm chác bài này ntn hả BTC ?



#28
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3916 Bài viết

Lại thêm một hạn sạn của MO! (Kết quả trận này có thể hủy?)






0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh