폴리매스

수학적 귀납법으로 접근하자. 즉, node의 개수 n에 대해, n<=k-1일때 문제의 명제가 성립한다고 가정하자. 이때, k=2^r x t라고 하자.(t는 홀수)

이제, node 2^r, node 2^r x 2, node 2^r x 3, ... , node 2^r x t에 대해, 각 node를 제외한 모든 node에 불이 들어오게 하는것이 귀납적 가정에 의해 가능하다. 이때 각 node 2^r x b를 제외한 모든 전구를 키게 하는 버튼의 조합을 A_b​​​​​​라고 하자. 만약 A₁, A₂, ..., A_t중 운좋게 모든 운좋가 다 켜지는 경우가 있다면, 명제가 자동으로 성립한다. 만약 모든 경우에 개해 각각 node 2^r, node 2^r x 2, ... , node 2^r x t가 불이 안들어온다면, A_1, A_2, ... A_t를 모두 mod 2에서 더한 조합을 누르면, t가 홀수이기 때문에 

어라 홀짝성 안맞네... 이 방법은 k 짝수때만 되는걸로.

홀수는 살짝 생각을 해봐야겠군요.

정리:

귀납적으로 n<=k-1일때 명제가 성립한다 가정. 이제 node k개인 그래프 G에 대헤, 각 node 1, 2, ..., k에 대해 각 node i를 제외한 모든 node에 불이 들어오게 버튼을 누를 수 있음. 만약 이렇게 버튼을 눌렀는데 아다리가 잘 맞아서 node i도 같이 눌린다면 즉시 귀납적으로 명제가 성립.

(가정 A) 이제, 위의 시행에서 각 노드 i에 대해 i가 눌리지 않았다고 가정. 이러면 각각 node i를 제외하고 모두 불이 들어오게 누르는 버튼 조합, node j를 제외하고 불이 들어오게 하는 버튼 조합을 합치면 임의의 node i, j에 불이 들어오게 할 수 있음. 따라서 k가 짝수인 경우는 자명하게 명제가 성립. K가 홀수인 경우, 각 node의 degree합이 짝수이므로 어떤 node i는 degree가 짝수, 즉 그 node를 누르면 홀수개의 node에 불이 들어옴. 이때 이제 남은 불 안켜진 node는 짝수개이고, 이는 위의 property로 인해 성립. 즉, 가정 A가 거짓, 즉 어떤 node i를 잘 고르면, node i를 제외하고 불이 모두 켜지게 했을 때 i도 슬쩍 꼽껴서 같이 켜진다.

따라서 귀납적으로 문제의 명제가 성립. QED