Gia?i to'an vui: 2

Oke,
Vấn đề này không đơn giản lắm, tôi chưa nghĩ cụ thể, nhưng bạn có thể giải đại loại thế này:


Đặt D(x,y,z,v) là số đường đi cần tìm trong trường hợp điểm cuối là (x,y,z,v).

Dễ thấy rằng D(N,0,0,0)=D(0,N,0,0)=D(0,0,N,0)=D(0,0,0,N)=1.

Chúng ta hãy xét "bước đi đầu tiên": Nếu là đi theo trục x, thì ta còn phải đi từ điểm (1,0,0,0) đến (x,y,z,v). Vậy trong trường hợp này ta có D(x-1,y,z,v). Tưong tự như vậy ta xét cho tất cả các hướng đi khác. Tóm lại ta có:
D(x,y,z,v)=D(x-1,y,z,v)+D(x,y-1,z,v)+D(x,y,z-1,v)+D(x,y,z,v-1).


Như vậy ta có một cái gọi là công thức truy hồi (recurent formula), dựa vào đây bạn có thể tìm ra D(x,y,z,v) trong trường hợp điểm cuối "khá gần" với điểm gốc. Tất nhiên tôi nghĩ tính toán vẫn còn khá phức tạp. Bạn cũng có thể nhận xét thêm rằng nếu bạn đảo chỗ các x,y,z,v cho nhau thì đáp số vẫn không thay đổi (nói cách khác D(x,y,z,v)=D(z,x,v,u)=...) để đơn giản hoá việc tính toán.
Được hoangmanhquang sửa chữa / chuyển vào 04:36 ngày 08/12/2004

Cám ơn bác nhiều, để tui thử tính toan xem sao .
Husky

mình nghĩ là (16!)/(4!3!5!4!)

Trông đáp số mới nghif ra cách gia?i gọn. Thật tệ. Ma? bấc Shinichi đaf có cách gia?i sao không up lên luôn?

mình nghĩ đơn giản thế này: chia thành 4 nhóm 1,2,3,4. Số đường đi từ (0,0,0,0) đến (4,3,5,4) tương ứng với số cách chọn 4 thằng nhóm 1, 3 thằng nhóm 2, 5 thằng nhóm 3, 4 thằng nhóm 4. Có 16 thằng nên sẽ thấy có 16! cách lấy, tuy nhiên ứng với 1 cách chọn có 4!3!5!4! cách như vậy(hoán vị các thằng nhóm 1, hoán vị các thằng nhóm 2,...) nên số cách chọn khác nhau sẽ là 16!/(4!3!5!4!).
Có thể dễ dàng tổng quát bài toán này

ca''m o*n ca''c ba''c ra^''t nhie^`u /
Husky

Hôm trước mới gặp, giờ giới thiệu luôn cho bác nào chưa biết hướng tổng quát sau:
D(0,0)=1
D(x,y)=aD(x-1,y)+bD(x,y-1)
Tìm công thức của D(x,y) ?
Tất nhiên là sau đó có thể tổng quát lên thành n chiều

Các bác cứ làm phức tạp vấn đề quá.
Tôi sẽ trình bày cách tính D(x, y, z, t) của tôi
Rõ ràng, 1 đường đi chính là 1 dãy bao gồm x+y+z+t bước
(các bác sẽ thấy rõ nếu "chiếu" đường đi lên các trục toạ độ)
Ký hiệu X là bước đi theo trục x.
Tương tự Y, Z, T.
Vậy 1 đưòng đi có thể biểu diễn như sau
X X X X Y Y T Z Z T X Z Y........
bao gồm x phần tử X, y phần tử Y, z phần tử Z, t phần tử t.
Vậy ta tính số đường đi như sau :
Chọn trước vị trí cho x phần tử X có C(x+y+z+t, x) lựa chọn.
Tiếp theo chọn vị trí cho y phần tử Y có C(y+z+t, y) lựa chọn .
Tiếp theo chọn vị trí cho z phần tử Z có C(z+t, z) lựa chọn.
Cuối cùng chọn vị trí cho t phần tử T có 1 cách chọn, hihi.
Vậy đáp số là
D(x, y, z, t) = C(x+y+z+t, x)*C(y+z+t, y)*C(z+t, z)
Trong đó C(n,k) là tổ hợp chập k của n phần tử.
Xong
Các bạn có thể mở rộng công thức này cho không gian n chiều.

đáp số vẫn là (x+y+z+t)!(x!y!z!t!) thôi mà Nhìn công thức này cảm giác đẹp hơn, bạn nghĩ thế không?

Mình nghĩ chứng minh cái của heroes bằng cách trên. Tính ra C(x+y+z+t, x)*C(y+z+t, y)*C(z+t, z) rồi suy ra công thức của Heroes. Vì vậy nếu làm như trên khác nào chứng minh lại cái mình đã đã biết và ứng dụng.