| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1998년01월09일(금) 00시12분05초 ROK 제 목(Title): Re: (문제) 쌈빡한 수열은 하나다. 우선... 정리 1(UNIQUENESS) 쌈박한 수열은 많아야 1개 존재한다. 증명: 좋은 수열 (갑)의 궤도 상의 한 쌈빡한 수열을 a1, a2, a3, ..., an 이라고 하자. 표기상의 편의를 위해 sum[i,j] = ai + ... + aj 라고 하자. 이 수열은 쌈빡하므로 sum[1,n] = n-1 이고, sum[1,k] >= k 이다. (k<n 일때) 쉽게 sum[k+1,n] = sum[1,n] - sum[1,k] =< n-1-k < n-k 임을 보일 수 있다. 만약 위의 쌈빡한 순열을 p 번 shift한 순열 b1, b2, ..., bn 이 있다고 하자. (물론 0 < p < n 이다.) 이 순열이 쌈빡하다면, 쌈빡한 순열의 성질에 의해, sum_b[1,k] >= k 이다. (sum_b[i,j] = bi + ... + bj) 하지만 sum_b[1, p] = sum[n-p+1, n] < n-(n-p) = p 이므로 sum_b[1,p] >= p 라는 가정에 어긋난다. 따라서 sum_b[1,p] 는 쌈빡하지 않다. 이는 가정에 어긋나므로 모순이다. 즉, 쌈빡한 수열은 궤도상에 많아야 하나이다. -QED- 정리 2(EXISTENCE) 쌈빡한 수열은 적어도 하나 존재한다. -- 에공... 풀다 자꾸 제자리를 맴도네요.. 누구 푸신분?? -- 박.. |