| [ QuizWit ] in KIDS 글 쓴 이(By): guest (poin) 날 짜 (Date): 1998년01월08일(목) 03시53분33초 ROK 제 목(Title): (문제) 쌈빡한 수열은 하나다. 여기에 첨 들어와 봅니다. 재미있는곳이군요. 저도 그래서 문제 하나 내 볼랍니다. 많은 성원 부탁 드립니다. 먼저 용어를 몇개 정의해야 합니다. 정의................................................ 유한수열을 생각해 봅시다. (물론 수열이니까 각 원소에는 순서가 있겠죠? 첫때수 ,둘째수,....) 1. 좋은 수열. 좋은 수열이란 각 원소가 음이 아닌 정수이고 그 수열의 합이 그수열의 길이(원소의 갯수)보다 1이 작은 유한수열을 말한다. 예) 1 1 1 1 1 1 0 ......좋은수열이다. 1 2 3 0 0 0 0 0 0 0 0 0 1..........좋은 수열이 아니다. 1 0 2 3 0 0 0 .......좋은 수열이다. 2. 쌈빡한 수열. 쌈빡한 수열이란 좋은 수열 중에서 다음 조건을 만족하는수열이다. 조건. 수열의 첫자리가 양수이다. 수열의 둘째자리까지의 합(첫자리+둘째자리)가 2보다 크다. 수열의 세째자리까지의 합이 3보다 크다. 수열의 네째자리까지의 합이 4보다 크다. . . . 수열의 마지막에서 둘째자리까지는 위와같이 그 합이 그 자리수보다 크다. 그리고 마지막 자리는 0이다.(이건 좋은 수열이므로 당연히 그러하다) 3. 쉬프트. 유한수열 갑이 있다 수열(갑)에 있는 각원소들이 자리 이동을 하는데... 첫째수가 둘째 자리로... 둘째수가 세째 자리로... 세째수가 네째 자리로... .... 그리고 마지막수가 첫째 자리로 이동해서 만들어 지는 수열을 수열 (갑)의 쉬프트라 부르자. 그리고 쉬프트를 두번 이상 반복 한것도 쉬프라고 부르자. (쉬프트) (다시말해 쉬프트란 주어진 수열을 적당히 돌리는거다) 4. 궤도 어떤 수열 (갑)이 있을때 (갑)을 쉬프트 하여 만들어지는 수열은 (갑)을 포함 총 n개이다.( (갑)의 길이가 n 일때) 바로 이 n 개의 수열을 수열 (갑)의 궤도 라 부르자. 저의는 이상이다. 정의 그럼 문제를 낸다. ................................................................ (문제) 좋은 수열 (갑)이 있다. 그러면 수열 (갑)의 궤도에는 쌈빡한 수열이 단 한개 존재함을 보여라. ................................................................... 여러분들은 아마 이문제를 알것이다. n*n 격자도로의 한 꼭지점에서 그 대각에 존재하는 꼭지점까지 도로를 따라 최단거리로 가되 그 대각선을 넘지 않으며 가는 길잡이 수를 구하는문제. 그리고 많은 사람이 그 답은 전체 길잡이 수의 1/(n+1) 이고 그 풀이는 대각선에 대한 대칭을 절묘하게 이용한다는 사실을 알것이다. 하지만 그 풀이는 1/(n+1) 이라는 숫자이 필연성을 전혀 보여주지 못한다. 의 위에 낸 쌈빡한 ㅍ수열이 유일함을 증명하는 문제는... 1/(n+1)이라는 숫자의 필연성을 보여주는 아름다운 풀이에 대한 힌트이다. ........................................................................ 처음 글을 쓰다 보니 서투르기도 하고 해서 존대말 쓰는걸 어느순간 부턴가 까묵고 반말을 쓰게 돼 부렀다. 널리 양해 바라며... 앞으로도 여기에 글을 좀 올려볼까 한다카는 말을 하고 싶다. 이곳 많은 고수들의 지도편달을 바라마지 않는다. |