Đến nội dung

Hình ảnh

$\frac{q}{m+n}.\binom{m+n}{m}$

- - - - - tổ hợp

  • Please log in to reply
Chủ đề này có 4 trả lời

#1
baopbc

baopbc

    Himura Kenshin

  • Thành viên nổi bật 2016
  • 410 Bài viết

Cho điểm $P(m,n)$ với $m,n$ là các số tự nhiên. Giả sử $P$ nằm trên đường thẳng $L:y=px+q$ với $p,q$ là các số tự nhiên. 

Một đường đi từ đỉnh $(0,0)$ đến đỉnh $P$ trong đó mỗi bước đi sẽ theo véctơ $(0,1)$ hoặc $(1,0)$. Chứng minh rằng số các đường đi chỉ cắt $L$ tại một điểm duy nhất là $P$ bằng $\frac{q}{m+n}.\binom{m+n}{m}$



#2
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết

Mình không giỏi lắm về khoản khai triển những biểu thức phức tạp nên sẽ nói hướng làm và việc trình bày cụ thể sẽ dành cho bạn Bảo:

Tất nhiên $q\neq 0$, nếu $q=1$ thì bước đầu tiên là ta sẽ di chuyển sang phải (hay di chuyển theo vector $(1,0)$). Ta sẽ quy nạp theo $m+n$ với $p$,$q$ bất kì, có thể xét riêng các trường hợp $m+n=1,2,3$ để suy ra dpcm.Giả sử bài toán đúng với $m+n=k$, xét $m+n=k+1$. Nếu $q=0$ thì ta có bài toán đúng, nếu $q>0$ thì đầu tiên ta có $2$ cách di chuyển:

+)Di chuyển theo vector $(0,1)$, lúc này ta tịnh tiến đồ thị theo vector $(0,-1)$ thì điểm $P$ sẽ thành điểm $(m,n-1)$, đường thẳng $L$ thành đường thẳng $y=px+q-1$, cách đi từ gốc $O$ (điểm ta đến được lúc đầu trước khi dùng phép tịnh tiến) đến $P$ là $\frac{q-1}{m+n-1}\binom{m+n-1}{m}$ theo giả thiết quy nạp

+)Di chuyển theo vector $(1,0)$, tịnh tiến theo vector $(-1,0)$, điểm đang đến trở thành gốc $O$, $P$ thành $(m-1,n)$, $L$ thành $y=px+p+q$, cách đi từ $O$ đến $P$ là $\frac{p+q}{m+n-1}\binom{m+n-1}{m-1}$

Cộng $2$ giá trị trên lại, lưu ý rằng $n=pm+q$, ta sẽ có cách đi từ $O$ đến $(m,n)$, suy ra dpcm theo nguyên lí quy nạp



#3
viet nam in my heart

viet nam in my heart

    Thượng sĩ

  • Điều hành viên OLYMPIC
  • 242 Bài viết

Hướng làm tính quy nạp theo hai ô cạnh nó xuất hiện nhiều trong các bài toán kiểu này và đếm bằng hai cách. Nhưng vấn đề ở đây là cách để tìm ra công thức kia khá khó (may măn ở bài này người ta bắt chứng minh chứ không phải bắt tính). Nếu bắt tính thì việc dự đoán kết quả thực sự khó khăn. Do vậy mình vẫn muốn tìm được một cách nào đó không mẫu mực để ra được công thức kia  :( Nếu ai có thì chia sẻ lên đây với nhé:) 


"Nếu bạn hỏi một người giỏi trượt băng làm sao để thành công, anh ta sẽ nói với bạn: ngã, đứng dậy là thành công." Isaac Newton

VMF's Marathon Hình học Olympic


#4
baopbc

baopbc

    Himura Kenshin

  • Thành viên nổi bật 2016
  • 410 Bài viết

Em nghĩ cái này liên quan đến đường đi ngắn nhất từ điểm $O$ đến $P$ và với mô hình kiểu này thì ta có một bài mẫu khá điển hình là bài $VNTST\ 2003$ và em nghĩ có lẽ bài liên quan đến bài toán đó! :)



#5
viet nam in my heart

viet nam in my heart

    Thượng sĩ

  • Điều hành viên OLYMPIC
  • 242 Bài viết

Cho điểm $P(m,n)$ với $m,n$ là các số tự nhiên. Giả sử $P$ nằm trên đường thẳng $L:y=px+q$ với $p,q$ là các số tự nhiên. 

Một đường đi từ đỉnh $(0,0)$ đến đỉnh $P$ trong đó mỗi bước đi sẽ theo véctơ $(0,1)$ hoặc $(1,0)$. Chứng minh rằng số các đường đi chỉ cắt $L$ tại một điểm duy nhất là $P$ bằng $\frac{q}{m+n}.\binom{m+n}{m}$

 

Em nghĩ cái này liên quan đến đường đi ngắn nhất từ điểm $O$ đến $P$ và với mô hình kiểu này thì ta có một bài mẫu khá điển hình là bài $VNTST\ 2003$ và em nghĩ có lẽ bài liên quan đến bài toán đó! :)

Hôm nay đọc lại bài này mình nghĩ có thể sử dụng $2$ cách để lý giải cho đáp số của bài toán (Cách chứng minh nếu đã biết sẵn đáp án thì quy nạp như cách của JUV sẽ là nhanh gọn nhất  :D )

Cách 1: Sử dụng phương pháp quỹ đạo (Có trong một chuyên đề của GGTH 2015)

Cách 2: Sử dụng bổ đề xích

Tình cờ hôm nay lang thang trên mạng mình có tìm thấy một chuyên đề rất hay về bổ đề xích và ứng dụng rất đẹp trong các tình huống như bài trên do đó up lại lên diễn đàn để mọi người tham khảo. Bài của Bảo cũng là $1$ bài trong chùm bài tập luyện tập của bổ đề này. Tác giả của tài liệu là thầy Vũ Thế Khôi 

File gửi kèm  VTKhoi_cycle-lemma.pdf   140.44K   1309 Số lần tải


"Nếu bạn hỏi một người giỏi trượt băng làm sao để thành công, anh ta sẽ nói với bạn: ngã, đứng dậy là thành công." Isaac Newton

VMF's Marathon Hình học Olympic






Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: tổ hợp

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

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