| [ QuizWit ] in KIDS 글 쓴 이(By): guest (poin) 날 짜 (Date): 1998년01월09일(금) 09시13분51초 ROK 제 목(Title): (정답) 쌈빡한 수열. 위에 있는 wiking 게스트님의 답은 정답입니다. (음냐...첨자와 터미놀로지떼메 눈 빠지는줄 알았어요.) 매우 훌륭한 답이라고 생각합니다. wiking님의 답은 a(1)+a(2)+...a(i)- i 를 최소로 하는 i들 중에서 제일 작은 수를 k라 하면, a(k+1) 부터 시작하는 수열이 쌈빡한 수열이다 ...라는 말씀입니다. 그리고 정답이구요. 그리고 저이 증명보다 좀 더 진화된 방법이군요. 저의 증명을 써 보겠읍니다. 사실 1. a a a ... a 0 은 쌈빡하다. b b b 0 c c c c 0 은 쌈빡하다 할때.... (여기서 a들이나 b들이나 c들이 모두 같다는 말은 아니예요.) b b b a a a ... a 0 c c c c 0 도 쌈빡하다. 다시말해 어떤 쌈빡한 수열의 0이 들어있는 자리에 쌈빡한 수열을 끼워 넣으면 그 또한 쌈빡해 진다는 얘기. (증명 생략) 존재성 증명 ( 수열의 길이에 관한 귀납법) ㅅ좋은 수열이 있다. 적당히 쉬프트하여 맨 앞이 수가 0이 아니게 하자. 그 제일 앞의 수부터 차례로 따져서 쌈빡한 수열이 되게 하는 가장 긴 수열을 찾는다. 다시말해 어떤 자리까지의 합이 그 자리수 보다 1이 작게 되는 최초의 곳까지만의 작은 수열을 찾는다. q q q ...q q 0 z z z z... z 위에서 q q q ... q q 0 가 쌈빡한 최초의 수열이다. 그러면 그 합은 q 의 갯수와 같다. 그러므로 그 뒤이 작은 수열...(0 포함) 0 z z z z... z 도 좋은 수열이다.(왜냐 하면 큰 수열의 합은 q의 갯수 + z의 갯수) 여기서 귀납법 가정에 의해 0 z z z z... z 를 잘 쉬프트하면 z z ...z 0 z ...z 이라는 쌈빡한 수열을 얻는다. 그러면 사실1에 의해 z z z...z q q q ...q q 0 z ...z 는 쌈빡하고 이것은 본래수열의 쉬프트이다. (물론 수열의 길이가 2일땐 당연하다) (증명끝) 개념적으로 괜찮죠? 증명이... 물론 wiking님의 해답은 쌈빡한 수열을 찾아내는 방법의 하나를 가르쳐주고 있으니 더욱 훌륭하고요.... 그럼 다음글에서 내는 퀴즈의 힌트로써 쌈빡한 수열의 유일 존재성을 이용해 보세요. |