브레인스토머의 설계 의도와 한계

두 번째로 큰 값이 두 번 나오는 지수 배정

원안. 1<a<b<c1<a<b<c, c/a=64c/a=64이다. log⁡2a,log⁡2b,log⁡2c\log_2a,\log_2b,\log_2c를 지수 p,q,rp,q,r에 하나씩 배정한 apbqcra^p b^q c^r의 서로 다른 값 가운데 가장 큰 것이 MM, 두 번째로 큰 것이 NN이다. NN을 주는 배정이 두 가지일 때 M/NM/N을 구한다.

처음 조사할 것을 고르는 이유. 둘째 값이 무엇인지는 아직 모르지만, 그보다 큰 값은 MM 하나뿐이다. 그러므로 배정을 조금 바꾸어 곱을 키울 수 있다면 어디까지 커져야 하는지 알고 있다. 이때 두 밑의 지수만 맞바꾸면 나머지 인자는 비에서 없어진다. 이웃한 밑 u<vu<v에 지수 s>ts>t가 이 순서로 붙어 있다면 맞바꾼 뒤의 곱은 (v/u)s−t>1(v/u)^{s-t}>1배가 된다. 뒤집힌 이웃이 없어질 때까지 바꾸면 세 지수가 증가하는 유일한 배정에 이른다. 이것이 MM의 배정이다.

두 번째라는 정보가 줄이는 범위. NN에서 뒤집힌 이웃을 한 번 바꿨는데도 여전히 최댓값에 이르지 못했다면 NN과 MM 사이에 또 다른 값이 생긴다. 따라서 NN의 배정은 MM에서 이웃 지수를 딱 한 번 바꿔 얻는 두 배정 중 하나다. NN을 주는 배정이 둘이므로 바로 이 둘의 곱이 같아야 한다. 여섯 값을 계산해 나열하거나, 같은 값을 주는 배정이 있는지 모든 쌍에서 조사할 필요가 없다.

이제 비교할 양. M/NM/N을 물었으므로 두 번의 맞바꿈에서 각각 잃은 배수를 그대로 비교할 수 있다. s=log⁡2(b/a)s=\log_2(b/a), t=log⁡2(c/b)t=\log_2(c/b)라 하면 두 배수는

(b/a)log⁡2b−log⁡2a=2s2,(c/b)log⁡2c−log⁡2b=2t2.(b/a)^{\log_2b-\log_2a}=2^{s^2},\qquad (c/b)^{\log_2c-\log_2b}=2^{t^2}.

s,t>0s,t>0이므로 s=ts=t이다. 앞에서는 c/a=64c/a=64로부터 두 비의 곱만 알 수 있었으나, 이제 s+t=6s+t=6을 적용하면 s=t=3s=t=3이다. 따라서 M/N=29=512M/N=2^9=512이다. aa 자체를 정하지 않고도 b/a=c/b=8b/a=c/b=8을 택하면 두 배정이 실제로 같은 둘째 값을 준다.

다른 길. 모든 곱에 처음부터 밑이 22인 로그를 취할 수도 있다. A,B,CA,B,C를 원래 밑의 로그라 하면, 증가하는 배정의 로그값에서 다른 배정의 로그값을 뺀 것은 각 자리에 원래 있던 수와 새로 온 수의 차의 제곱을 합한 뒤 22로 나눈 값이다. 전개하면 같은 세 수의 제곱합이 양쪽에 나타나므로 확인된다. 바뀐 자리는 적어도 둘이고 두 수 차의 최소는 min⁡(B−A,C−B)\min(B-A,C-B)이다. 따라서 가장 작은 양의 손실은 가장 가까운 두 수만 서로 바꿀 때 생긴다. 이 풀이에서는 조사 대상을 고르는 근거가 거듭제곱의 비에서 제곱거리의 최솟값으로 바뀐다.

조건과 한계. a=2,c=128a=2,c=128을 그대로 두어도 b=4b=4면 M/N=2M/N=2이고 b=16b=16이면 M/N=512M/N=512이다. 두 배정이 같은 둘째 값을 준다는 단서가 실제 결론을 가른다. 배정 순서만 가리는 앞부분은 임의의 증가하는 세 지수에서도 성립한다. 지수가 밑의 로그라는 단원 성질은 두 손실이 각각 2s22^{s^2}, 2t22^{t^2}이어서 같아진 손실이 곧 같은 두 밑의 비를 뜻한다는 뒷부분에 집중되어 있다. 밑이 셋뿐이어서 여섯 값을 전개하는 풀이도 가능하다. 이미 재배열 부등식을 아는 학생이 앞부분을 빠르게 인식할 여지도 있다.

작성 원문