| [ QuizWit ] in KIDS 글 쓴 이(By): guest (wiking) 날 짜 (Date): 1998년01월09일(금) 04시55분58초 ROK 제 목(Title): Re: Re^2 (문제) 쌈빡 수열..cdpark,guest(a Let's define a few terminologies. s is the shift operation. S[a](i) = a1 + ... + ai A[a](i) = S[a](i) - i So exitence proof is showing that for a certain k, A[s^k(a)](i) >= 0 for all i less than n. (A) 1. if (A) holds for k = 0, DONE. 2. If not, assume that Amin be the smallest number of {A[a](i)} for i less than n. For values satisfying A[a](i) = Amin, choose the smallest i and call it m (This guaratees that am = 0!! ^^) 3. Now choose n - k = m!! Since S[s^k(a)}(l) = S[a](l-k) + S[a](n) - S[a](n-k), A[s^k(a)](l) = (S[a](l-k)-(l-k)) + n - 1 - (S[a](n-k)-(n-k)) -n = A[a](l-k) - A[a](n-k) - 1 Observing m = n-k > l-k for l < n with definition of m, A[a](l-k) - A[a](n-k) >= 1, or A[s^k(a)](l) >= 0 (l < n). ( for l <= k, trivia ^^) QED |