| [ QuizWit ] in KIDS 글 쓴 이(By): guest (poin) 날 짜 (Date): 1998년01월09일(금) 09시40분47초 ROK 제 목(Title): (문제) 배짱좋은 극장 (문제) 어떤 극장에서 영화를 상영한다. 입장료는 5000원이다. 2n명의 사람들이 매표소에 줄을 서 있다. 이들 중 n명은 5000원짜리 하나만 달랑 들고 왔고... 나머지 n명은 만원 짜리 한장만 달랑 들고 왔다. 그런데 극장매표소에는 돈이 한푼도 없다. 완전 배짱이다. 그래서 이 극장에선 어떤 사람에게 받은 5000원을 만원짜리 내는사람에게 거슬러주어야 한다. 줄서있는 사람들은 매표소직원과만 상대하지 서로는 일체의 거래를 하지 않는다. 그리고 극장에선 줄서 있는 차례대로만 표를 판다. 그럼 이 2n명의 사람이 임의로 줄을 섯을때 극장이 2n자의 표를 무사히(거스름돈이 없어서 표를 못파는일 없이) 팔아치울수 있는 확률은? 다음에 제시하는 문제는 위 문제오 동일한 문제이닫. (유사문제) 사장이 n페이지짜리 문서를 손으로 쓰고 있다. 사장은 한 페이지를 쓸때 마다 그 페이지를 비서의 책상위에 놓는데... 차례차례 포개어 놓는다. 그리고 이 비서는 그 문서를 즉시 즉시 타이핑 하는게 아니라... 그저 내키는대로 지 하고 싶을때 하기도 한다. 다만 사장이 쌓이놓은 문서중 제일 윗장부터 한다. 그리고 타자를 친 페이지는 그옆에 차례로 포개어서 쌓는다. 이때 사장도 글을 다 쓰고 비서도 타이핑을 다 했을때 비서가 쌓아놓은 문서의 페이지 배열의 가짓수는? (유사문제) n*n 격자도로에서 한꼭지점에서 다른 꼭지점으로 도로를 따라 최단거리로 갈때 그 대각선은 넘지 않고 (대각선위의점을 지나는것은 괜잖다.) 갈수 있는 길잡이수의 갰ㄱ수는 몇개인가? .............................................................. 이 문제들은 리플렉션 을 이용하는 기발하고도 유명한 풀이가 있다. 그리고 많이들 알것이다. 근데 이 문제를 끄집어내는 이유는 이 문제가 쌈빡한 수열 문제를 이용해서도 풀수가 있기 때문이다. 실은 바로 그 풀이를 소개하기 위해 쌈빡한 수열문제를 먼저 낸 것이다. 자...그럼 쌈빡한 수열을 이용해서 이 문제를 어떻게 공략할것인가? ............................................................. 음...나도 별명 하나 만들어야겠네요. 히히 자격있나요? 포인(poin)이 씀. |