2020년 04월 나형 29번

29. 그림과 같이 바둑판 모양의 도로망이 있다. 이 도로망은 정사각형 $R$$R$와 같이 한 변의 길이가 $1$$1$인 정사각형 $9$$9$개로 이루어진 모양이다.

이 도로망을 따라 최단거리로 $A$$A$ 지점에서 출발하여 $B$$B$ 지점을 지나 다시 $A$$A$ 지점까지 돌아올 때, 다음 조건을 만족시키는 경우의 수를 구하시오.

(가) 정사각형 $R$$R$의 네 변을 모두 지나야 한다.

(나) 한 변의 길이가 $1$$1$인 정사각형 중 네 변을 모두 지나게 되는 정사각형은 오직 정사각형 $R$$R$ 뿐이다.

---

i. 생각

• 가로로 진행하는 경우 $a$$a$, 세로로 진행하는 경우 $b$$b$라고 하자.

• 우선 $R$$R$의 네변을 지나기 위해서는 다음 그림에서 점 $C$$C$를 지나면서 왕복해야 한다.

  

• 어떤 경우가 가능할까?

  $A\to C\to B$$A\to C\to B$ 이 경우는 딱히 문제가 없는데,

  $B\to C\to ?\to A$$B\to C\to ?\to A$ 여기서 즉, $C\to A$$C\to A$로 오는 과정에서 정사각형의 네 변을 만나서는 안된다?

• $C\to A$$C\to A$로 오는 경로를 정하기 위해서는 $A\to C$$A\to C$를 알아야 피해갈 수 있다....허....

• $C\to B\to C$$C\to B\to C$는 $2$$2$가지 경우만 가능하다. ($R$$R$의 네 변을 모두 지나야한다.)

• $A\to C$$A\to C$의 경로에 따라 $C\to A$$C\to A$의 경로를 정하자.

  • $A\to C$$A\to C$의 전체 가짓수는 $\frac{4!}{2!2!}=6$$\cfrac{4!}{2!2!}=6$가지. 해볼만 하네...

    • $aabb$$aabb$의 경로를 따를 경우

      $C\to A$$C\to A$의 경우는 $b,a,b,a$$b,a,b,a$의 경로를 따를 때만 네 변을 지난다.

      $\therefore 6-1=5$$\therefore~ 6-1=5$

    • $abab$$abab$의 경우

      $abab,abba,baab,bbaa$$abab,abba,baab,bbaa$

      $6-4=2$$6-4=2$

    • $abba$$abba$의 경우

      $baab,baba,abab$$baab,baba,abab$

      $6-3=3$$6-3=3$

    • $baab$$baab$의 경우

      $abab,abba,baba$$abab,abba,baba$

      $6-3=3$$6-3=3$

    • $baba$$baba$의 경우

      $bbaa,baab,abba,abab$$bbaa,baab,abba, abab$

      $6-4=2$$6-4=2$

    • $bbaa$$bbaa$의 경우

      $abab$$abab$

      $6-1=5$$6-1=5$

    $\therefore 20$$\therefore~ 20$

$\therefore 2\times 20=40$$\therefore~ 2\times 20=40$