조합[체스판] 1-1

조합문제를 풀때 등장하는 체스판문제의 예시와 테크닉을 알아보자.

다음의 예시문제를 보도록 하자.

 

#1.다음과 같은 10×10 그래프 G가 있다. G에 포함된 어떤 격자 회로 P가 다음을 만족한다.

P는 점 a를 정확히 한 번 지난다.

P는 a,b가 아닌 각 점을 정확히 10번씩 지난다.

이 때, P는 점 b를 정확히 몇 번 지나는가?

이 판 위 b는 왼쪽 아래 가장자리에, a는 오른쪽 위 가장자리에 존재한다.

이 판의 점을 체스판처럼 검정 흰색을 칠하면(a,b가 있는 자리가 흰색이 되도록) 격자회로 P는 검정점과 흰 점이 교대로 반복된다.

조금만 어떤 회로를 그려서 관찰해볼 경우, P가 지나는 검정점개수=P가 지나는 흰점개수이다.

P가 지나는 검정점개수=50×10

P가 지나는 흰점개수=48×10+1+b를 지나가는 횟수

따라서 P는 점 b를 19번 지난다.

이 문제에서 우리가 알 수 있는 것은 m×m 판에 검정,흰색을 교대로 칠해가면 어떤 회로가 지나는 검정점개수와 흰점개수가 같다는 것이다. 게다가 m이 짝수라면 검정점개수와 흰점개수도 같다는 것을 알 수 있다.

 

 

#2.8×8 체스판에서 8개의 룩이 놓여 있는데, 임의의 두 루크는 서로 공격할 수 없는 위치에 있다. 이때, 검정칸에 있는 루크는 짝수개임을 보여라.

체스판에서 가장 왼쪽 위에 존재하는 칸을 생각하고 그 칸을 기준으로 좌표계를 설정하자.

그리고 가장 왼쪽 위에 존재하는 칸을 검정색이라고 두면 검정색 칸들의 좌표는 (홀수,홀수)나 (짝수,짝수)꼴일 것이고 흰색 칸들의 좌표는 (홀수,짝수)나 (짝수,홀수)꼴일 것이다.

Ri=(xi,yi)

(x1+y1)+.....(x8+y8)≡2(1+2+...+8)≡0(mod 2)

따라서 xi+yi≡1(mod 2)인 i는 짝수개 존재해야 한다.

이번에는 칸들에 색을 칠한 뒤 홀짝성을 비교한 뒤, 룩들의 x,y좌표값들이 모두 서로 다르다는 점을 이용했다.

 

 

 

#3.10×10 체스판에 몇 개의 룩들이 놓여 있는데 임의의 두 루크들은 서로 공격할 수 없는 위치에 있다. 또한 흰색칸에 있는 루크 개수와 검정칸에 있는 루크 개수는 같다. 이 때, 비어 있는 어떤 칸에 루크 한 개를 놓으면 임의의 두 루크는 서로 공격할 수 없음을 보여라.

 

#2에서 나온 결론이 사용된다. 루크가 10개고 흰색에 있는 루크와 검은색에 있는 루크 개수가 같으면 둘 다 5개라고 할 수 있는데 위에서 나온 것처럼 흰색과 검은색 루크 개수중 하나는 짝수개여야 해서 모순이다.

 

 

 

#4.F는 n×n×n 정육면체이고 F의 내부는 단위정육면체 n³개로 분할되어 있다. 그런데 분할된 단위정육면체는 흰색 또는 검정색이다. 또한 각각의 흰색 단위정육면체는 정확히 세 개의 검정색 단위정육면체와 면을 공유하고 각각의 검정색 단위 정육면체는 정확히 세 개의 흰색 정육면체와 면을 공유한다. 이 떄, 가능한 n을 모두 구하여라.

A를 흰색cube의 집합으로, B를 검정색cube의 집합으로 설정한다.

a∈A와 b∈B가 한 면을 공유하면 선분으로 연결하여 d(a)=3,d(b)=3으로 할 수 있다.

A와 B를 연결하는 선분개수를 N이라고 하면, N=3n(A)=3n(B)

n(A)=n(B)가 되고 n(A)+n(B)=n³이라 n이 2의 배수일때 가능하다.

 

이처럼 체스판을 사용하여 X=Y라는 형식으로 식을 세워 문제를 풀거나 홀짝성을 자주 비교한다는 것을 알 수 있다.

 

#5.33마리의 룩이 8×8 체스판 위에 앉아 있다. 서로 싸우고 있지 않은 5마리를 뽑아낼 수 있음을 증명하여라.

1	2	3	4	5	6	7	8
8	1	2	3	4	5	6	7
7	8	1	2	3	4	5	6
6	7	8	1	2	3	4	5
5	6	7	8	1	2	3	4
4	5	6	7	8	1	2	3
3	4	5	6	7	8	1	2
2	3	4	5	6	7	8	1

보이는 것처럼 체스판 위에 숫자를 부여하여 같은 숫자 위에 올려진 룩은 서로 공격할 수 없는 구조를 갖게 한다.

xi=i번에 올라가 있는 룩 개수

x1+x2+...+x8=33 비둘기집의 원리에 의해 xi≥5인 xi가 존재한다.

이 문제는 체스판을 흑백으로 칠하는 것과는 달리 숫자를 부여하여 비둘기집의 원리를 사용하는 것이 눈에 띈다.

+)비둘기집의 원리는 이 글 다음이니 보고 오는 것을 추천한다.