Chủ đề này có 1 trả lời

[nhungvienkimcuong]

Xét một lưới ô vuông cỡ $p\times q$ trên mặt phẳng tọa độ chứ các điểm $\left \{ \left ( x,y \right )\in \mathbb{N}^2|x\leq p,y\leq q \right \}$.Một đường đi sẽ có mỗi bước đi theo $\text{vecto}\ (0,1)$ hoặc $(1,0)$.Tính số đường đi từ $(0,0)$ đến $(p,q)$ mà không vượt lên trên đường chéo $qx-py=0$

Spoiler

đáp số hình như là $\frac{1}{p+q}\begin{pmatrix} p+q\\p \end{pmatrix}$ thì phải =))

Spoiler

hình vẽ minh họa:  abc.pdf   25.89K   127 Số lần tải

Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 23-12-2016 - 18:14

[redfox]

Nếu $\left ( p;q \right )=1$ thì đúng vậy.

Xét dãy các bước đi là $\vec{v}_1,\vec{v}_2,...,\vec{v}_{p+q}$ và các điểm nguyên trên đường đi trừ $\left ( p,q \right )$ là $A_1,A_2,...,A_{p+q}$.

Với đường đi bất kì và số $1< k\leq p+q$, ta hoán vị các bước đi thành $\vec{v}_k,\vec{v}_{k+1},...,\vec{v}_{p+q},\vec{v}_1,\vec{v}_2,...,\vec{v}_{k-1}$ và hoán vị tên các điểm nguyên một cách tương tự, ta được một đường đi mới. Làm như vậy ta được $p+q$ đường đi khác nhau (vì $\left ( p;q \right )=1$). Trên đường đi đó, xét các đường thẳng đi lần lượt qua các điểm $A_1,A_2,...,A_{p+q}$ và song song với $qx-py=0$. Vì $\left ( p;q \right )=1$ nên các đường thẳng đó phân biệt, xét đường thẳng nằm cao nhất (tức là đường thẳng $qx-py+k=0$ có $k$ lớn nhất) đi qua $A_i$. Ta để ý sau khi hoán vị các bước đi và tên các điểm, đường thẳng đi qua $A_i$ vẫn nằm cao nhất. Vậy trong $p+q$ đường đi đó, chỉ có một đường đi thỏa mãn đề bài là đường đi có điểm $\left ( 0,0 \right )$ có tên là $A_i$. Ta có $\frac{1}{p+q} \binom{p}{p+q}$ bộ $p+q$ đường đi nên có $\frac{1}{p+q} \binom{p}{p+q}$ đường đi thỏa mãn đề bài.

Có lời giải trong TH $\left ( p;q \right )\neq 1$ không?