폴리매스

(1)11x11의 체스판에 대해, 다음 시행을 생각한다: 몇 개의 칸으로 이루어진 직사각형의 영역을 하나 택하여, 그 영역을 흰색 혹은 검은색으로 칠한다. 모든 칸이 하얗게 칠해져있는 상태에서, 다음 3가지 조건을 만족하는 상태로 바꾸기 위해 필요한 시행의 횟수의 최솟값을 구하여라.

1) 가장 좌상단에 있는 칸은 검은 색으로 칠해져있다.

2) 검은색으로 칠해진 칸과 변을 공유하는 칸은 모두 흰색으로 칠해져있다.

3) 흰색으로 칠해진 칸과 변을 공유하는 칸은 모두 검은색으로 칠해져있다.

(2)위 문제를 nxn의 체스판으로 바꾸고, 위 세 조건을 만족하기 위해 필요한 시행 횟수의 최솟값을 n에 관해서 나타내어라.