자연계열 2교시 1번

왜냐하면, 한 단위 가로 또는 세로 방향으로만 갈 때는 총 8번의 이동이 필요하지만, 한 단위 대각선 방향으로 갈 때는 가로와 세로 방향을 한 번만에 간 효과가 있기 때문이다. 위의 관계식을 만족시키는 $\displaystyle (x,y,z)$의 조합 및 그에 따른 경로의 비용 및 소요 시간은 다음 표와 같다.

$\displaystyle \begin{array}{c|c|c|c|c}\text{조합}&x=y&z&\text{비용 (원)}&\text{소요 시간 (시간)}\\\hline\mathrm I&0&4&4\times2400=9600&4\times0.5=2\\\mathrm {II}&1&3&(2\times1000)+(3\times2400)=9200&(2\times1)+(3\times0.5)=3.5\\\mathrm {III}&2&2&(4\times1000)+(2\times2400)=8800&(4\times1)+(2\times0.5)=5\\\mathrm {IV}&3&1&(6\times1000)+(1\times2400)=8400&(6\times1)+(1\times0.5)=6.5\\\mathrm V&4&0&8\times1000=8000&8\times1=8\end{array}$

따라서, 9000원 이하 비용과 7시간 이내 소요 시간 조건을 만족시키는 조합은 III과 IV이다.

조합 III에 따른 경로는 아래와 같은 $\displaystyle 6(={}_{4}\mathrm{C}_{2})$가지 종류가 있을 수 있다. 따라서, 총 30(=18+12)가지 경로가 있다.

조합 III에 따른 경로

$\displaystyle \dfrac{4!}{2!2!}\times3=6\times3=18$

$\displaystyle (2\times2)\times3=4\times3=12$

조합 IV에 따른 경로는 아래와 같은 $\displaystyle 4(={}_{4}\mathrm{C}_{1})$가지 종류가 있을 수 있다. 따라서, 총 64(=40+24)가지 경로가 있다.

조합 IV에 따른 경로

$\displaystyle \dfrac{6!}{3!3!}\times2=20\times2=40$

$\displaystyle \left(2\times\dfrac{4!}{2!2!}\right)\times2=12\times2=24$

따라서, 총 94(=30+64)가지의 경로가 있다.