| [ QuizWit ] in KIDS 글 쓴 이(By): guest (guest) <211.212.225.172> 날 짜 (Date): 2002년 7월 18일 목요일 오전 12시 04분 25초 제 목(Title): Re: [펌] 좀 어렵네요... 1에서 n까지의 솟수의 갯수는 아닙니다. 너무 띄엄띄엄하거든요. m이 문제의 최소값이라면, m개 중에 두개를 뽑는 방법의 갯수가 m(m-1)/2니까 이 숫자는 최소한 n-1 이상이어야 합니다. 즉, 대충 말해 f(n)을 n에 대한 문제의 m 값이라고 하면 f(n)은 sqrt(2*(n-1))보다 큽니다. 사실은 위의 어림셈이 너무 느슨한 것이라는 것은 대강 자명하죠. 위의 결과는 f(n)이 C*n^(1/2)보다 크다는 (C는 어떤 상수, 구체적으로는 이 경우 sqrt(2)) 것을 말해줍니다만, 이 지수 1/2은 지나치게 느슨한 값입니다. (그럼에도 불구하고 이것으로 숫수의 갯수는 아니라는 것은 분명해집니다.) 한편 문제의 지수는 1 이내여야 한다는 것도 쉽게 알 수 있습니다. 임의의 양수 r에 대해 f(n)은 asymptotic하게는 r*n보다 작기 때문입니다. (이것을 확인하기 위해서는 k를 하나 고른 뒤에, 1 간격으로 k개의 숫자를 1, 2, 3, 4, ..., k까지 배열하고, 그 다음부터 2k, 3k, ... 이런 식으로 k 간격으로 숫자들을 배열하면 됩니다. 끝에 가서는 다시 1 간격으로 숫자를 늘어놓으면 되죠. 낭비가 심하지만, 어쨌든 k 간격으로 충분히 길게 늘어놓을 수 있기 때문에 궁극적으로는 밀도를 원하는 만큼 낮출 수 있습니다.) 그래서, 1/2와 1 사이에서 대체 어디일까요? 저의 `아님말고 가설'에 의하면 임의의 1보다 작은 양수 r과 임의의 상수 C에 대해 f(n)은 asymptotic하게는 C*n^r보다 크지 않을까 짐작합니다. 아니면 말고요. :) |