조합[불변량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에 대해 불변임을 보여주는..

2021.11.07