| [ QuizWit ] in KIDS 글 쓴 이(By): guest (guest) 날 짜 (Date): 1998년01월07일(수) 09시39분29초 ROK 제 목(Title): [풀이] 가장 큰 정사각형 A|----E--|B 전에 여기다 썼듯이, 일반성을 잃지 않고 왼쪽과 같이 최대 정사각형이 | | 있는 경우 변 AB는 한 개의 덮개로 덮이지 않고 두 개의 덮개로 덮여야 | F 한다고 가정할 수 있습니다. | | C|-------|D 그림에 표시되어 있는 E는 타이핑 실수가 아니라 거기에 있는 한 점을 나타낸 것입니다. 만일 어떤 덮개가 꼭지점 B를 덮고, 또한 점 E를 덮는다고 합시다. 이때 이 덮개는 변 BD를 얼마나 덮을 수 있을까요? 최대 BF까지 덮을 수 있다고 가정합시다. BE의 길이를 x라 하면 BF의 길이 f(x)는 x의 함수이고, 이 함수는 쉽게 계산이 됩니다: x<=1이면 f(x)=x(1-sqrt(x^2-1)), x>=1이면 x=f(x)(1-sqrt(f(x)^2-1)). 후자의 경우는 f(x)를 x에 대해 풀어야 하는데, 그 결과가 상당히 복잡합니다. 어쨌든 간에...... 매우 당연한 것이고 아마 계산을 한참 해 보면 계산도 되겠지만, f(x)는 감소함수입니다. G가 G^4-G^2-1=0을 만족하는 유일한 양수라고 합시다. (이게 바로 1.272...입니다.) 가정에 의해, 선분 AB를 덮는 두 덮개 중 하나는 A를 덮고, 다른 하나는 B를 덮고, 이들은 선분 AB상의 어떤 점 E를 함께 덮습니다. AE의 길이를 s, BE의 길이를 t라 합시다. s+t=a가 됩니다. 그러면 A를 덮은 덮개는 AC를 최대 f(s)만큼, B를 덮은 덮개는 BD를 최대 f(t)만큼 덮을 수 있습니다. AC의 나머지 a-f(s), BD의 나머지 a-f(t)는 제 삼의 덮개가 덮어야 합니다. 그건 그렇고, f(G-1)=G라는 것을 쉽게 계산에 의해 확인할 수 있습니다. 우리의 목표는 a=G가 가능한 최대값이라는 것을 보이는 것이므로, a>G라고 하고 모순을 끌어내겠습니다. 두 가지 가능성이 있습니다: s,t 둘 다 1 미만인 경우와, 둘 중 하나는 1 이상인 경우입니다(둘 다 1 이상이면 a=s+t는 2 이상이 되는데 그럴 수는 없죠). 여기서는 s,t 둘 다 1 미만인 경우만 다루겠습니다. 나머지 경우도 비슷하게 될 거라고 짐작합니다. s=a-t>a-1>G-1이고 f가 감소함수이므로, f(s)<f(G-1)=G<a. 즉, A를 덮는 커버는 꼭지점 C까지는 덮지 못합니다. s와 t는 대칭적이므로 역시 B를 덮는 덮개도 D를 못 덮습니다. 따라서 제 삼의 덮개는 변 CD를 전부 덮을 수 있어야 합니다. 이제 g(x)=(a^2-a*x*sqrt(a^2+x^2-1))/(a^2+x^2)라고 놓으면, 그림을 하나 그리고 닮은 삼각형과 피타고라스의 정리와 g가 감소함수라는 것을 이용하면, a^2<=g(a-f(s))^2+g(a-f(t))^2가 성립해야 함을 알 수 있습니다. (와, 엄청난 비약이다!) 자, 이제 위의 부등식에서 우변의 최대값을 생각해 봅시다. 파라미터는 s와 t지만 이들은 s+t=a라는 조건을 만족합니다. 그리고 s,t<1이어야 합니다. 우변은 s와 t에 대해 대칭입니다. 이 우변의 식은 무지무지 구질구질합니다만, 미분을 하건 어떻게 하건 간에 우변의 최대값은 s=1,t=a-1, 또는 s=a-1,t=1, 또는 s=t일 때 얻어져야 할 것입니다. 계산이 귀찮군요. 흑흑. 근데 그림을 그려보시면 s=t일때야말로 사실은 최소값이죠. 그러므로 주어진 부등식은 a^2<g(a-f(a-1))^2+g(a-f(1))^2. f(1)=1이므로 g(a-f(1))^2=g(a-1)^2. 한편, a>G 이므로 a-1>G-1 -> f(a-1)<f(G-1)=G<a이므로 a-f(a-1)>0 다시 g가 감소함수이므로, g(a-f(a-1))<g(0)=1 (그냥 간단히 계산됨). 결국 주어진 부등식은 a^2-1<g(a-1)^2. 한편, 우리는 G^2-1=g(G-1)^2가 된다는 것을 간단한 계산에 의해 확인할 수 있습니다. 따라서, a>G이면, g()의 감소성 때문에, a-1>G-1 ->g(a-1)<g(G-1)^2=G^2-1<a^2-1, 이건 모순이죠. 결국 최소한 s,t<1인 때에는 a>G이면 모순이 나온다는 것을 보일 수 있었습니다. 이 과정에서 구렁이 담 넘듯이 넘어간 것에는 다음 것들이 있습니다: 1) f,g는 진짜로 감소함수인가? 2) g(a-f(s))^2+g(a-f(t))^2가 s+t=a, 0<s,t<1이라는 조건 하에 어디에서 최대최소값을, 어디에서 극대극소값을 갖는가. 이 두 가지는 물론 계산을 열나게 하면 증명이 쉽게 될 것입니다. 물론 s<1이고 t>=1인 경우를 계산하지 않았지만 이 경우도 어떻게 되겠지요 뭐... 하여튼 이 문제의 경우 중요한 점은 덮개가 비교적 간단하게 생겨먹은 덕택에 최대 정사각형의 내부에서 무슨 일이 일어나는지에 별로 신경을 쓰지 않고도 둘레의 변들이 어떻게 덮이는가만 신경쓰면 문제가 풀린다는 것입니다. 물론 이것도 제대로 된 증명이라기 보단 스케치 정도입니다. 식을 이용하지 않고 어떻게 닮은 삼각형 등을 적당히 써서 할 방법이 있으면 좋겠군요. |