조합[불변량1] 3-1

불변량에는 번쩍이는 아이디어가 필요한 것 같다. 불변량 문제는 보통 어떠한 시행을 계속 진행하여 그 과정에서 변하지 않는 것을 잡는다.(반불변량도 있는데 그것은 나중에 다루도록 하겠다.)

아래의 문제를 보도록 하자.

 

#1.한 번의 시행에서 정수의 순서쌍 (p,q,r)을 (r+5q,3r-5p,2q-3p)으로 바꾼다. (1,3,7)로부터  유한번의 시행 후에 (k,k+1,k+2)가 얻어지는 정수 k가 존재하는가?

문제에서 시행을 할 때에 변하지 않는 것을 찾아야 한다.

(r+5q)+(3r-5p)+(2q-3p)≡p+q+r(mod 3) 시행을 할때 순서쌍 원소들의 합은 mod 3에 대해 불변이다.

1+3+7은 3m+2꼴인데 k+(k+1)+(k+2)은 3m꼴이라 모순

이 문제처럼 mod e에 대해 불변임을 보여주는 것부터 어떠한 구조를 새로 설계하여 불변량을 찾는 경우까지 다양하다고 볼 수 있다.

 

#2.원주 위에 시계방향으로 돌면서 1,2,3,4,5,6이 쓰여져 있다, 다음과 같은 시행을 생각하자.

시행:연속한 세 개의 숫자를 선택하자. 이 숫자들 각각에 1씩 더하거나 아니면 이 숫자들 각각에 1씩 뺀다.

어러한 시행을 잘 해서 원주 위에 있는 모든 숫자가 같게 할 수 있을까?

#1에서 했던 것처럼 mod 3에 대해 보면 할 수 있는게 없음을 알 수 있다.(해보면 안다.)

그렇다면 어떻게 불변량을 잡을 수 있겠는가?

1,2,...,6에 a1,a2,...,a6을 부여한 것

A=a1+a4

B=a2+a5

C=a3+a6

이라 하면 시행을 할때 A,B,C의 값은 변하지 않는다.

시행을 할때 모두 1씩 추가되거나 빠진다.

B-A=일정 인데 초기의 B-A의 값은 2+5-1-4=2이고 후기의 B-A의 값은 0이라 모순

따라서 불가능하다.

 

#3.네 마리의 메뚜기가 정사각형 꼭지점에 하나씩 있다. 1초마다 한 번씩 한 마리의 메뚜기만 다른 한마리를 뛰어넘어 점대칭점으로 옮겨간다.

(1)어떠한 세 마리도 원래 사각형의 변에 평행한 직선 위에 앉게 되는 경우는 없음을 보여라.

(2)어떠한 세 마리도 한 직선 위에 앉게 되는 경우는 없음을 보여라.

 

(1)

WLOG:(0,0) (1,0) (0,1) (1,1) 네 점에 메뚜기가 있다고 하자. 메뚜기가 다른 메뚜기를 뛰어넘을 때 (x,y)->(x',y') 기우성이 유지된다. 그런데 세 마리가 사각형의 변에 평행한 직선 위에 앉으려면 세 메뚜기의 x나 y의 기우성이 다 같아야 해서 모순

 

(2)

일단 어떤 세 마리가 한 직선 위에 앉아있다고 가정하자. (1)에서 했듯이 메뚜기가 다른 메뚜기를 뛰어넘을 때 기우성이 유지된다.

가능한 x,y축의 기우성	짝	짝	홀	홀
	짝	홀	홀	짝
	짝	짝	홀	홀

짝짝짝과 홀홀홀은 있을 수 없고 x,y를 짝홀짝과 홀짝홀을 잘 부여해가며 세워도 mod 2에 대해 기우성이 같은 (x'y') (x,y)쌍이 존재한다. 따라서 모순

 

다음의 문제는 직접 풀어보자.

#4.컴퓨터 화면에 숫자 한 개가 있는데 141이었다. 매 초마다 컴퓨터 화면에 나타난 숫자의 모든 자리의 숫자의 곱을 화면에 나타난 숫자에 더하거나 뺀 결과가 컴퓨터 화면에 나타나고 원래의 숫자는 사라진다. 이 때, 141이 다시 나타날 수 있는가?