KMO 금메달 수학 조합 p 216 문제 327번
아래의 그림과 같이 1의 간격으로 16개의 점이 배열 되어 있다.
. . . .
. . . .
. . . .
. . . .
증가하는 경로란 연속하는 점들의 거리가 점점 늘어나는 서로 다른 점들의 배열이다.
m을 증가하는 경로안의 점들의 개수의 최댓값이라 하고 r은 정확히 m개의 점으로 구성
된 증가하는 경로의 개수라 한다. mr 을 구하시요?
<문제풀이 >:
두 점 사이의 가능한 길이를 증가하는 순으로 나열하면 다음과 같다.
1 , 루트2 , 2 , 루트5 , 루트8 , 3 , 루트 10 , 루트13 , 루트18
즉, 점들의 최댓값 m = 10이고 , r 의 개수를 구하기 위해서는 거꾸로 해보는 것이 좋다.
각각의 점에 번호를 1 부터 16 까지 붙이면 다음과 같다.
1. 2 . 3. 4 .
5. 6 . 7. 8 .
9. 10 . 11 . 12 .
13. 14 . 15 . 16 .
1부터 거꾸로 시작한다면 다음과 같다.
1 - 16 - 2 - 15 - 3 - 9 - 7 - 5 - 10 - (6 , 11 , 14)
1 - 16 - 5 - 12 - 9 - 3 - 10 - 2 - 7 - (6 , 8 ,11)
즉, r = 4 * 6 = 24 이므로 mr = 10 * 24 = 240 이다.
<문제해설 및 보충설명>:
4 * 4 격자점 안에서, 가장가까운 거리에있는 점들 사이의 거리에서 가장 먼 거리에있는 점들 사이의 거리 까지 증가하는 거리의 순서 데로 나열하여 최대한으로 많은 점들을 지나게 배열하여 조건에 맞는 값을 구하는 문제이다.
증가하는 경로란 연속하는 점들의 거리가 점점 늘어나는 서로 다른 점들의 배열이다.
서로 다른 점들의 배열이기 때문에 같은 점을 두번 지날수 없다.
m 이 증가하는 경로안의 점들의 개수의 최댓값 인데 작은값부터 제일 큰값 까지 연결해보면 지나간 모든 점들의 개수 이다.
그림을 그려보면 이해하기가 쉽다. 점들의 최댓값 m = 10이다.
r 은 정확히 m개의 점으로 구성 된 증가하는 경로의 개수라 했으니,
무슨 말인지 살펴보자.
4 * 4, 16개의 격자점 안에서 10 개의 점으로 구성 된 증가하는 경로의 개수 가 r 이다.
왜냐하면 거꾸로 감소하는 경로로 찿기가 수월하기 때문이다.
루트18, 루트13 , 루트 10 , 3 , 루트8, 루트5 , 2 , 루트2 , 1 순서로 그려보면 찿기가 쉬워진다.
문제에서 요구 하는데로, 1 부터 루트18 까지 증가하는 순서데로 찾아보세요.
중간에서 막히게 됩니다. 그러나 거꾸로 찾아서, 즉 왼쪽위 에서 오른쪽아래 까지 대각선을 연결하면 누구나 찾을수 있습니다.
수학을 처음시작할때 시행착오를 통해서 할수밖에 없고, 도중에 자꾸 실수가 반복되고, 더이상 진전이 어려울수도 있습니다.
도중에 포기 하면, 한것 까지만 경험을 통하여 이해하게 됩니다.
끝까지 포기하지 않고, 끈질기게 문제를 해결할려고 노력하는 아이들이 나중에, 창의력 사고력 문제해결력 자기주도학습 능력등이 수학을 통해서 길러져, 다른 여타과목 도 잘할수있고 유능한 인재가 되는 인물로 자라나게 되는 경우를 자주 볼수 있습니다.
스스로의 방법을 찾아 자기나름 데로의 방식으로 문제를 해결하는 게, 가장 훌륭한 공부하는 방법인데 ,시간이 많이 걸리고, 또한 더 이해하기 쉽고 더좋은 방법도 있으니까 친구들과 토의도 해보고, 문제를 바꾸어 어려운 문제를 쉽게 풀수있게 변형하여 "이렇게도 풀수있구나" "다음엔 어떻게 해야지 " 이런 생각들이 떠오를때 공부의 깊이와 폭이 넓혀지게 되고 더 복잡하고 어려운 문제를 풀수있게 되고 공부가 재미 있게 되지 않을까요?
이런 아이로 자라게 할려면, 부모나 선생은 기다려 주어야 싹이 트게 됩니다.
몇년 공부하다 치울것도 아니고, 평생공부가 필요한 아이들에겐 ,지치지 않고 좋아서 재미있어서 더 도전하고 싶어서 ,스스로 찾아서 능동적으로 앞으로 나아갈때 창의력도 생기고 호기심이 발동하여 탐구하다 보면 예상치못한 좋은 결과를 얻을수 있게 되겠지요.
다시 문제로 돌아가서, 두 점 사이의 가능한 길이를 감소하는 순으로 연결하면 시작점을 찾게되고 , 다시 거꾸로 증가하는 순으로 나열하면 우리가 구하는 답을 찾을수 있다.
1부터 거꾸로 시작한다면 다음과 같다.
1 - 16 - 2 - 15 - 3 - 9 - 7 - 5 - 10 - (6 , 11 , 14)
시작점은 6, 11 ,14 에서 출발하여 10 -5-7-9-3-15-2-16-1 에서 끝나면,
연속하는 점들의 거리가 점점 늘어나는 서로 다른 점들의 배열 ,증가하는 경로를 구할수 있게된다.
(6 , 11 , 14)- 10-5-7-9-3-15-2-16-1
1 - 16 - 5 - 12 - 9 - 3 - 10 - 2 - 7 - (6 , 8 ,11)
시작점은 6 ,8 ,11 에서 출발하여 7-2-10-3-9-12-5-16-1 에서 끝나면 증가하는 또다른 경로를 구할수 있다.
(6 , 8 ,11) - 7-2-10-3-9-12-5-16-1
r은 정확히 10개의 점으로 구성 된 증가하는 경로의 개수다.
시작점이 (6 , 11 , 14), (6 , 8 ,11) 6개 있고 끝점은 모두 점1 이다.
대칭성에 의해서 끝점은 점1, 점4, 점13, 점16 이 될수 있다.
시작점 6개 끝점 4개 가 있으니 곱하면 모두 24가지 증가하는 경로의 개수 가 있다.
즉, r = 4 * 6 = 24 이므로 mr = 10 * 24 = 240 이다.
궁금하거나 의문나는점이 있으면 연락해 주세요!
010-3549-5206 으로
감사합니다.
4 * 4 격자점 안에서, 가장가까운 거리에있는 점들 사이의 거리에서 가장 먼 거리에있는 점들 사이의 거리 까지 증가하는 거리의 순서 데로 나열하여 최대한으로 많은 점들을 지나게 배열하여 조건에 맞는 값을 구하는 문제이다.
증가하는 경로란 연속하는 점들의 거리가 점점 늘어나는 서로 다른 점들의 배열이다.
서로 다른 점들의 배열이기 때문에 같은 점을 두번 지날수 없다.
m 이 증가하는 경로안의 점들의 개수의 최댓값 인데 작은값부터 제일 큰값 까지 연결해보면 지나간 모든 점들의 개수 이다.
그림을 그려보면 이해하기가 쉽다. 점들의 최댓값 m = 10이다.
무슨 말인지 살펴보자.
4 * 4, 16개의 격자점 안에서 10 개의 점으로 구성 된 증가하는 경로의 개수 가 r 이다.
그림을 그려보면 이해하기 쉬운데,
r 의 개수를 구하기 위해서는 거꾸로 해보는 것이 좋다.왜냐하면 거꾸로 감소하는 경로로 찿기가 수월하기 때문이다.
루트18, 루트13 , 루트 10 , 3 , 루트8, 루트5 , 2 , 루트2 , 1 순서로 그려보면 찿기가 쉬워진다.
문제에서 요구 하는데로, 1 부터 루트18 까지 증가하는 순서데로 찾아보세요.
중간에서 막히게 됩니다. 그러나 거꾸로 찾아서, 즉 왼쪽위 에서 오른쪽아래 까지 대각선을 연결하면 누구나 찾을수 있습니다.
수학을 처음시작할때 시행착오를 통해서 할수밖에 없고, 도중에 자꾸 실수가 반복되고, 더이상 진전이 어려울수도 있습니다.
도중에 포기 하면, 한것 까지만 경험을 통하여 이해하게 됩니다.
끝까지 포기하지 않고, 끈질기게 문제를 해결할려고 노력하는 아이들이 나중에, 창의력 사고력 문제해결력 자기주도학습 능력등이 수학을 통해서 길러져, 다른 여타과목 도 잘할수있고 유능한 인재가 되는 인물로 자라나게 되는 경우를 자주 볼수 있습니다.
스스로의 방법을 찾아 자기나름 데로의 방식으로 문제를 해결하는 게, 가장 훌륭한 공부하는 방법인데 ,시간이 많이 걸리고, 또한 더 이해하기 쉽고 더좋은 방법도 있으니까 친구들과 토의도 해보고, 문제를 바꾸어 어려운 문제를 쉽게 풀수있게 변형하여 "이렇게도 풀수있구나" "다음엔 어떻게 해야지 " 이런 생각들이 떠오를때 공부의 깊이와 폭이 넓혀지게 되고 더 복잡하고 어려운 문제를 풀수있게 되고 공부가 재미 있게 되지 않을까요?
이런 아이로 자라게 할려면, 부모나 선생은 기다려 주어야 싹이 트게 됩니다.
몇년 공부하다 치울것도 아니고, 평생공부가 필요한 아이들에겐 ,지치지 않고 좋아서 재미있어서 더 도전하고 싶어서 ,스스로 찾아서 능동적으로 앞으로 나아갈때 창의력도 생기고 호기심이 발동하여 탐구하다 보면 예상치못한 좋은 결과를 얻을수 있게 되겠지요.
다시 문제로 돌아가서, 두 점 사이의 가능한 길이를 감소하는 순으로 연결하면 시작점을 찾게되고 , 다시 거꾸로 증가하는 순으로 나열하면 우리가 구하는 답을 찾을수 있다.
1부터 거꾸로 시작한다면 다음과 같다.
1 - 16 - 2 - 15 - 3 - 9 - 7 - 5 - 10 - (6 , 11 , 14)
시작점은 6, 11 ,14 에서 출발하여 10 -5-7-9-3-15-2-16-1 에서 끝나면,
연속하는 점들의 거리가 점점 늘어나는 서로 다른 점들의 배열 ,증가하는 경로를 구할수 있게된다.
(6 , 11 , 14)- 10-5-7-9-3-15-2-16-1
1 - 16 - 5 - 12 - 9 - 3 - 10 - 2 - 7 - (6 , 8 ,11)
시작점은 6 ,8 ,11 에서 출발하여 7-2-10-3-9-12-5-16-1 에서 끝나면 증가하는 또다른 경로를 구할수 있다.
(6 , 8 ,11) - 7-2-10-3-9-12-5-16-1
r은 정확히 10개의 점으로 구성 된 증가하는 경로의 개수다.
시작점이 (6 , 11 , 14), (6 , 8 ,11) 6개 있고 끝점은 모두 점1 이다.
대칭성에 의해서 끝점은 점1, 점4, 점13, 점16 이 될수 있다.
시작점 6개 끝점 4개 가 있으니 곱하면 모두 24가지 증가하는 경로의 개수 가 있다.
즉, r = 4 * 6 = 24 이므로 mr = 10 * 24 = 240 이다.
궁금하거나 의문나는점이 있으면 연락해 주세요!
010-3549-5206 으로
감사합니다.
댓글 없음:
댓글 쓰기