불변성 원리

Invariance Principle.

어떤 문제에서, 어떤 연산을 아무리 적용해도

1) 변하지 않는 값이 있거나(→불변량, I)

2) 일정한 규칙에 의해 순환하는 값이 있거나,

3) 일정한 규칙(단조증가, ...)에 의해 발산하는 값이 있다

이런 경우에 적용할 수 있다.

특히 이런 불변량은 mod N이 통하는 경우가 많다. 그중에서도 대표적으로 홀짝성(mod 2).

예제를 보자.

1. 탁자 위에 하얀 칩, 검은 칩, 빨간 칩이 각각 a,b,c,개씩 있다. 한 번에 서로 다른 색깔의 칩 두 개를 선택해서, 그 두 개를 버리고 나머지 색깔의 칩 한 개를 어디선가 가져오자.

1 - 1) 칩 하나만 남을 경우, 그 칩의 색깔은 (a,b,c)에 대해 한 가지만 존재함을 보여라.(즉 중간에 어떤 칩을 고르든 상관이 없다)

1 - 2) 이번에는 가져올 때 한 개 대신 두 개를 가져와보자. 즉 칩의 총량은 변하지 않는다. 이때 같은 색의 칩들만 남게 할 수 있는 (a,b,c)는?

1-1을 보면...

칩 두 개를 없애고, 나머지 하나는 늘어난다. 칩의 총량은 하나 줄어든다. 또 뭘 알 수 있을까?

사실 위에서 스포일러를 해버렸지만, (a, b, c) 세 수의 홀짝성은 무조건 변한다. 따라서 한 칩만 남을 경우, 갯수는 (1,0,0)개가 된다.(순서에 신경쓰지 않고)

(a,b,c) 중에는 비둘기집의 원리에 의해 홀짝이 같은 두 수가 존재한다.

만약 세 수 모두 같다면 칩 하나만 남는 것이 불가능하다. (홀홀홀) / (짝짝짝)만 가능하므로...

그렇지 않다면, 반드시 (짝짝홀)이나 (홀홀짝) 만 가능하다. 그러면 세 개중 다른 것(짝짝홀 중 홀, 홀홀짝 중 짝)의 색깔이 반드시 남게 된다.

예)

4	3	2	(짝홀짝)
3	2	3	(홀짝홀)
2	3	2	(짝홀짝)
1	2	3	(홀짝홀)
2	1	2	(짝홀짝)
1	2	1	(홀짝홀)
2	1	0	(짝홀짝)
1	0	1	(홀짝홀)
0	1	0	(짝홀짝)

1-2를 보면...

잘 모르겠다. 이번에는 위와 같은 홀짝 불변량도 적용되지 않고, 일단은 총합이 일정하다는 의미없는 불변량 하나만 보인다.

두 개는 -1이 되고, 하나는 +2가 된다.

이제 조금만 더 생각해보자! 위에서 이미 힌트가 나와있다.

mod 3으로 생각해보면 세 숫자 모두가 -1(+2)가 된다는 걸 알 수 있다! 그러면 마지막에 남는 세 수는 각각 (0,0,x)인데,

세 숫자 중 3으로 나눈 나머지가 같은 두 숫자가 있으면 되겠지.

(나중에)