교토대 2020-5(문과, 이과 공통)

 

 

 

 

 

가로 4칸, 세로 4칸의 4 $\times$ 4의 보드판을 1, 2, 3, 4의 네 숫자들로 채우자. 이 보드판의 가로를 '행', 세로를 '열'이라고 할 때, 모든 행 또는 열에 1, 2, 3, 4 가 정확히 한 번씩 들어가도록 하는 방법의 경우의 수를 구하시오.

 

 

 

 

 

 

생각해보기

 

 

개인적으로 아주 반가운 문제이다. 스도쿠를 좋아하는 필자 입장에서 이 문제는 4$\times 4$ 스도쿠의 가짓수를 묻는 것과 비슷해서인데... (물론 주어진 상황만 비슷할 뿐 실제 스도쿠의 가짓수랑은 차이가 크다.) 

기쁜 마음은 제쳐두고, 이 문제는 숫자들이 한 번 씩만 들어간다는 조건을 사용하면 마치 수형도를 이용하는 풀이와 비슷하게 풀 수 있다.

 

 

 

 

 

 

 

풀이

 

 

보드판의 1행에 <1234>가 쓰여져 있다고 가정해보자. 이때, <1234>와 같은 열에 같은 숫자가 겹치지 않도록 배열하는 방법은 $$<2143> \quad <2341> \quad <2413> \quad <3142> \quad <3412> \quad <3421> \quad <4123> \quad <4312> \quad <4321> $$

9가지가 있다. 따라서 보드판의 2행, 3행, 4행에는 이 9가지 배열 중 서로 겹치지 않는 3개의 배열을 나열해야 한다. 서로 겹치지 않는 3개의 배열은 아래의 4가지 밖에 없다.

 

$$ ① <2143>\quad <3412>\quad <4321>$$

$$ ② <2143> \quad<3421>\quad <4312>$$

$$ ③ <2341> \quad<3412> \quad<4123>$$

$$ ④ <2413> \quad<3142> \quad<4321>$$

 

①, ②, ③, ④의 각 경우에 2, 3, 4행을 채우는 방법이 $3!=6$개가 있으므로 총 $4 \times 6 = 24$가지가 있다. 그리고 처음 1행에 숫자를 배열하는 경우의 수가 $4!=24$개 이므로, 구하고자하는 전체 경우의 수는 $24 \times 24 = 576$ 개 이다.