수학 질문&답변분류: 이산수학경로의 개수 문제
신용이 회원 1 년 전에 질문함

$p,q$가 서로소인 자연수일 때, 좌표평면에서 원점 $O(0,0)$에서 출발하여 $\rightarrow$ 또는 $\uparrow$로 1칸씩 가는 동점이 직선 $\displaystyle y=\frac{q}{p}x$의 아랫 부분을 지나지 않고 점 $P(p,q)$까지 가는 경로의 개수를 구하라.

2 답변
박진원 회원 1 년 전에 답변함

예를 들어 다음과 문제를 먼저 생각해보면 풀 수 있을 것 같은데요. 아래 격자점을 지나서 가는 최단거리의 수는?

Rendered by QuickLaTeX.com

수학교육과 조교 회원 1 년 전에 답변함

오른쪽으로 가는 것을 $a$, 위쪽으로 가는 것을 $b$라고 하면 가로가 $p$칸, 세로가 $q$칸이므로 임의의 경로는

$p$개의 $a$와 $q$개의 $b$의 순서쌍으로 표현할 수 있다.

$\mu_1 = (a_1,a_2,\cdots,a_{p+q})$를 $O$에서 $P$로 가는 임의의 경로라고 하면 $a_i$의 값은 $a$ 혹은 $b$이다.

이제 $a_i$들을 하나씩 움직여 다음과 같이 $p+q$개의 순서쌍을 만든다.

$\begin{array}{l}
\mu_1 = (a_1,a_2,\cdots,a_{p+q})\\
\mu_2 = (a_2,a_3,\cdots,a_{p+q},a_1)\\
\mu_3 = (a_3,a_4,\cdots,a_1,a_2)\\
\qquad \;\; \vdots\\
\mu_{p+q} = (a_{p+q},a_1,\cdots,a_{p+q-1})
\end{array}$

이 $p+q$개의 순서쌍은 $O$에서 $P$로 가는 서로 다른 경로임을 보이자.

$p$개의 $a$와 $q$개의 $b$로 이루어진 것은 변하지 않으므로 $O$에서 $P$로 가는 경로임은 자명하다.

$\mu_i = \mu_j\; (i \neq j )$라 가정하면

각 좌표는 서로 같아야 하고 $a$와 $b$의 개수는 짝수가 된다. 이것은 $p$와 $q$가 서로소라는 것에 모순.

따라서 $\mu_i$들은 서로 다른 경로이다.

이제 아래 그림과 같이 각 $a_i$방향으로 움직인 점마다 기울기가 $\frac{q}{p}$인 직선을 그리고 각각 $\ell_i$라고 하자.

Rendered by QuickLaTeX.com

$\ell_i = \ell_j,\;(i \neq j)$라 가정하면

$$\frac{a_i \text{에서 } a_j \text{까지의 세로 거리}}{a_i \text{에서 } a_j \text{까지의 가로 거리}}=\frac{q}{p}$$
$a_i \text{에서 } a_j \text{까지의 세로 거리} < q$, $a_i \text{에서 } a_j \text{까지의 가로 거리} < p$이고 이것은 $p$와 $q$가 서로소 라는 것에 모순이다.

따라서 $\ell_i$들은 서로 다른 직선이고 경로 $\mu_1, \mu_2, \cdots , \mu_{p+q}$에서 점$O$와 $P$를 잇는 대각선은 각각 직선$\ell_{p+q}, \ell_1, \cdots, \ell_{p+q-1}$와 순서대로 일치하게 된다.

직선 $\displaystyle y=\frac{q}{p}x$의 아랫 부분을 지나지 않는 경로는 대각선과 $\ell_i$들 중 가장 오른쪽에 있는 직선이 일치하는 경우 한가지 밖에 없다.

따라서 주어진 조건을 만족하는 경로의 개수는 $p+q$개 중에 하나만 존재하고
$$\frac{1}{p+q} \binom{p+q}{p}$$이다.

기호목록

  • 악센트
  • 그리스(소)
  • 그리스(대)
  • 이항관계
  • 이항연산
  • 큰연산자
  • 짝맞춤
  • 화살표
  • 기타기호
  • 함수목록
  • 폰트
  • 기본문법

\not\equiv $\not\equiv$
아래 연산자는 위와 같이 \not을 붙임으로써
부정형이 될 수 있습니다.

간격
$|\!|$ \! $-\frac{3}{18}$글자
$|\,|$ \, $\frac{3}{18}$글자
$|\:|$ \: $\frac{4}{18}$글자
$|\;|$ \; $\frac{5}{18}$글자
$|\quad|$ \quad 한글자
$|\qquad|$ \qquad 두글자

분수
\frac{}{}

조합
\binom{}{}

루트
\sqrt{}

진하게
\boldsymbol{}
\pmb{}

디스플레이스타일
\displaystyle

줄바꿈
\\

array환경
$\text{\begin{array}{cc}}$
a&b\\
c&d
$\text{\end{array}}$

짝맞춤기호
\left, \right이 함께 사용됨.
한쪽을 생략하려면 \right.
과 같이 '.'을 붙임.
내용물에 따라 길이가 자동 조절
예)
\left( \frac{2}{3} \right)
$\left( \frac{2}{3} \right)$

\$안에 텍스트 쓰기
\text{}