Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

Tìm số cách đi trong hình chữ nhật mxn.


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

#1 duong vi tuan

duong vi tuan

    Thượng sĩ

  • Thành viên
  • 229 Bài viết
  • Giới tính:Nam
  • Đến từ:Quy NHơn

Đã gửi 19-05-2018 - 18:49

 Cho một hình chữ nhật m hàng n cột, có 2 người xuất phát từ góc dưới trái đi lên tới góc phải trên, mỗi người chỉ có thể đi lên hoặc đi qua phải và không được gặp nhau trên đường (trừ vị trí đầu tiên và đích cuối cùng). Tình tổng số cách đi.

Để rõ hơn các bạn xem hình bên dưới.

vd) m = n = 3, có 3 cách

3x3.png

m = 3, n =4, có 6 cách

3x4.png


Bài viết đã được chỉnh sửa nội dung bởi duong vi tuan: 19-05-2018 - 19:29

NGU
Hình đã gửi

#2 dottoantap

dottoantap

    Trung sĩ

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

Đã gửi 07-10-2019 - 10:40

 Cho một hình chữ nhật m hàng n cột, có 2 người xuất phát từ góc dưới trái đi lên tới góc phải trên, mỗi người chỉ có thể đi lên hoặc đi qua phải và không được gặp nhau trên đường (trừ vị trí đầu tiên và đích cuối cùng). Tình tổng số cách đi.

Để rõ hơn các bạn xem hình bên dưới.

vd) m = n = 3, có 3 cách

3x3.png

m = 3, n =4, có 6 cách

3x4.png

Mình không xem được hình trong ví dụ để hiểu rõ câu hỏi của bài toán!

Không biết đúng không nếu mình hiểu yêu cầu của bài toán như sau:

Giả sử 2 người là $A$ và $B$ thì một cách đi là một cặp đường đi gồm 1 đường đi của $A$ và 1 đường đi của $B$ mà 2 đường đi này không cắt nhau, thì bài toán yêu cầu tính số cặp đường đi này, phải không ạ? 

Nếu đúng vậy, thì ta có bài toán:

 Cho một hình chữ nhật m hàng n cột, có 2 người $A$ và $B$ xuất phát từ góc dưới trái (0,0) đi lên tới góc phải trên (n,m), mỗi người chỉ có thể đi lên hoặc đi qua phải và không được gặp nhau trên đường (trừ vị trí đầu tiên và đích cuối cùng). Tình tổng số các cặp đường đi (gồm đường đi  của $A$ và đường đi của $B$ mà 2 đường này không gặp nhau).

Giải:

Bài toán không thay đổi khi ta cho  $A$ đi từ (0,1) đến (n-1,m) và $B$ đi từ (1,0) đến (n,m-1).

Số đường $A$ đi là: $\binom{\left (n-1 \right )-0+m-1 }{\left (n-1 \right )-0}=\binom{n+m-2}{n-1}$

Tương tự, số đường $B$ đi là: $\binom{n-1+\left (m-1 \right )-0}{n-1}=\binom{n+m-2}{n-1}$

Do đó số cặp đường đi không có ràng buộc (tức là có thể cắt nhau) là $\binom{n+m-2}{n-1}^{2}$.

Nhận thấy các cặp đường cắt nhau là đường mà một anh $C$ nào đó bắt đầu đi theo đường của $A$ đến điểm cắt nhau thì đi theo đường của $B$ để đến đích và đường bắt đầu đi theo đường của $B$ đến điểm cắt nhau thì đi theo đường của $A$ để đến đích.

Như vậy, số cặp đường cắt nhau ( đường đi từ (0,1) đến (n,m-1) và đi từ (1,0) đến (n-1,m)) là:

$\binom{n+m-2}{m-2}\binom{n+m-2}{n-2}$

Suy ra số cặp đường thỏa yc là:

$P=\binom{n+m-2}{n-1}^{2}-\binom{n+m-2}{m-2}\binom{n+m-2}{n-2}$

 

PS: ...hình như lủng củng quá, hic.


Bài viết đã được chỉnh sửa nội dung bởi dottoantap: 08-10-2019 - 12:52

++++++++++++++++++++++++++++

Everything is impossible until you do it.

“Ai không làm gì thì mới không bao giờ sai”. Cứ làm đi, đừng sợ sai, trừ khi cái sai đó là cái sai gây tai hoạ cho người khác.





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

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