문제는 여기: https://arca.live/b/math/49429148
--------------------------------------------------------------------------------------------------------------
이 테이블을 변형해 보자.
다음 둘 중 한 가지 연산을 할 수 있다.
1) 가장 윗 줄이나 아랫줄에 속하지 않은 칸의 값을 2만큼 증가시키고, 그 윗칸과 아랫칸의 값을 1 감소시킨다.
2) 가장 윗 줄이나 아랫줄에 속하지 않은 칸의 값을 2만큼 감소시키고, 그 윗칸과 아랫칸의 값을 1 증가시킨다.
이 변환을 반복했더니, 그 테이블에 1부터 100까지 수가 한 번씩 나타났다. 즉, 원래의 표가 재배열된 형태였다.
이때, 재배열된 표로 가능한 것은 원래의 표만이 가능함을 보여라.
--------------------------------------------------------------------------------------------------------------
각 연산은 하나의 열(column) 내부에서만 작용한다.
이제 일반화돤 열 C_0 = [ a, a + b, a + 2b, ..., a + mb ] 에 대해 생각해보자.
이 열의 i 번째 항, 즉 a + ib 에 대해 (1) 의 연산을 적용한 횟수를 n_i 라 하자. (2)의 연산을 적용하는 것은 (1)의 연산을 -1회 적용하는 것으로 간주한다.
연산을 적용한 이후의 열을 C = [ c_0, c_1, ..., c_m ] 이라 하자.
예컨대 n_x = d 이고 다른 항에는 연산을 적용하지 않은 경우 (즉 ∀i≠x n_i = 0 인 경우),
c_(x-1) = a + (x-1)b - d
c_x = a + xb + 2d
c_(x+1) = a + (x+1)b - d
이제 각 항의 제곱의 합을 구해보자.
(c_(x-1))^2 + (c_x)^2 + (c_(x+1))^2 = ( a + (x-1)b )^2 + ( a + xb )^2 + ( a + (x+1)b )^2 + 6 d^2
즉 d ≠ 0 일 때 제곱의 합은 항상 원래의 열에서보다 크다.
이제 2개 이상의 항에 연산이 적용되는 경우에도 항상 제곱의 합이 커진다는 것을 증명해보자.
c_0 = a - n_1
c_1 = a + b + 2n_1 - n2
c_2 = a + 2b - n_1 + 2n_2 - n_3
c_3 = a + 3b - n_2 + 2n_3 - n_4
...
c_(m-2) = a + (m-2)b - n_(m-3) + 2n(m-2) - n_(m-1)
c_(m-1) = a + (m-1)b - n_(m-2) + 2n_(m-1)
c_m = a + mb - n_(m-1)
그러면
(c_1)^2 + (c_2)^2 + ... + (c_m)^2
= ( a^2 + (a+b)^2 + ... + (a + mb)^2 ) + ( (n_1)^2 + (2n_1 - n2)^2 + (-n_1 + 2n_2 - n_3)^2 + ... + (n_(m_1))^2 )
따라서 C 의 각 항의 제곱의 합은 항상 C_0 의 각 항의 제곱의 합보다 크거나 같으며
제곱의 합이 같아지기 위한 조건은 n_1 = n_2 = ... = n_(m-1) = 0 이다.
그런데 문제에서 테이블에 재배열된 숫자는 원래의 테이블에서와 같다고 했으므로, 각 항의 제곱의 합 역시 같다.
따라서 테이블의 모든 열에서 n_1 = n_2 = ... = n_8 = 0
