문제
카드 순서 바꾸기
숫자 카드 아홉 장이 5, 3, 2, 4, 6, 8, 7, 9, 1 순서로 놓여 있습니다. 한 번 바꾼다는 것은 카드 두 장이 자리를 맞바꾸는 것입니다. 두 카드가 이웃할 필요는 없습니다. 순서대로 만드는 가장 적은 횟수를 구합니다.
사고력 · 초6-2 바꾸기와 뒤집기
내 답
조심 제자리 아닌 카드마다 한 번씩일 것 같지만 고리 하나는 길이보다 한 번 적게 듭니다.
풀이 과정
전략 그림 그리기 — 자리마다 거기 놓인 카드가 가야 할 자리로 화살표를 하나씩 그려 보면 엉킨 것이 단번에 풀립니다. 화살표를 따라가면 밖으로 새어 나가는 법이 없고 반드시 제자리로 돌아와 고리를 이루므로, 아홉 장의 카드는 서로 간섭하지 않는 몇 개의 고리로 갈라집니다. 이 그림은 두 가지 일을 한꺼번에 해 줍니다. 먼저 더 쉬운 문제로 줄여서 카드 2장짜리 고리, 그다음 3장짜리 고리를 손으로 해 보면 k장짜리 고리에는 정확히 k-1번이 든다는 것이 보이고, 그러면 몇 번이면 충분한지가 나옵니다. 다음으로 한 번 바꿀 때 고리의 개수가 어떻게 변하는지 지켜보면 더 적은 횟수로는 안 되는 이유가 나오는데, 이는 바꾸기 순서를 아무리 많이 보여 줘도 결코 얻을 수 없는 것입니다.
1STEP 1
자리에 번호를 매기고 이미 제자리인 카드 찾기
이미 제자리인 카드는 4와 7입니다.
카드와 자리 번호를 맞대어 보는 일은 카드 한 장에 눈길 한 번이면 끝납니다. 뒤죽박죽으로 보이던 줄이 사실은 아홉 번의 간단한 확인일 뿐입니다.
4.OA.C.5Make A Systematic List2STEP 2
자리마다 그 카드가 가야 할 자리로 화살표 그리기
자리마다 갈 자리로 화살표를 그립니다.
1 → 5, 2 → 3, 3 → 2, 4 → 4, 5 → 6, 6 → 8, 7 → 7, 8 → 9, 9 → 1
카드를 어떻게 늘어놓든 자리마다 나가는 화살표 하나, 들어오는 화살표 하나가 됩니다. 바로 이것 때문에 화살표는 어디론가 사라지지 못하고 고리를 이룰 수밖에 없습니다.
4.OA.C.5Draw A Diagram3STEP 3
화살표를 따라가면 네 개의 고리가 생김
화살표를 따라가면 고리 네 개가 생깁니다.
(1 5 6 8 9), (2 3), (4), (7)
화살표를 손가락으로 짚어 가다 출발한 곳으로 돌아오는 일은 초등학생도 그냥 할 수 있고, 고리의 크기를 더해 9가 나오는지 보는 것이 빠뜨린 것이 없는지 확인하는 검산이 됩니다.
4.OA.C.5Draw A Diagram4STEP 4
더 쉬운 고리부터: 고리 하나에 몇 번이 드는가
고리 하나는 길이보다 한 번 적게 듭니다.
k장짜리 고리 → k-1번
카드 아홉 장을 놓고 따지는 것보다 가장 작은 고리 두 개를 손으로 해 보는 편이 빠릅니다. 거기서 드러나는 '한 번 바꾸면 카드 한 장이 은퇴한다'는 규칙은 눈으로 직접 볼 수 있어서 믿기도 쉽습니다.
4.OA.C.5Solve An Easier Related Problem카드 k장으로 된 고리를 정렬하는 데는 정확히 k 빼기 1번의 맞바꿈이 든다.
왜?
맞바꿀 때마다 카드 하나가 제자리에 들어가고 고리가 하나 짧아지므로, 카드와 맞바꿈이 하나를 남기고 대응된다.
🧱일대일 대응여기 있는 것 하나가 저기 있는 것 하나와 딱 짝지어지면 두 무리의 크기는 같다.
왜?
전체 작업은 따로 떨어진 고리들을 차례로 정렬하는 것이므로, 전체 비용은 고리별 비용을 더한 것이다.
🧱전체는 부분의 합겹침도 빈틈도 없이 조각내면 그 조각들을 다시 더해 전체가 된다.
5STEP 5
네 고리에 드는 횟수를 모두 더하기
네 고리를 더하면 5번입니다.
4 + 1 + 0 + 0 = 5 그리고 9 - 4 = 5
고리별로 더한 값과 카드 수에서 고리 수를 뺀 값이 똑같이 5로 나오니, 계산이 맞았는지 공짜로 검산한 셈입니다.
4.OA.A.3Look For A Pattern6STEP 6
5번이면 정말 되는지 보이기
실제로 다섯 번에 정렬됩니다.
한 번 바꿀 때마다 줄 전체를 다시 적어 두면 한 줄씩 눈으로 확인할 수 있어서, 남의 말을 믿을 필요가 없어집니다.
4.OA.C.5Make A Systematic List7STEP 7
4번으로는 결코 안 되는 이유 보이기
네 번으로는 모자랍니다.
9 - 4 = 5
고리를 세는 것이 이 풀이에서 가장 정직한 부분입니다. 바꾸기 목록을 보여 주는 것으로는 '그만큼이면 된다'까지밖에 못 가지만, 한 번에 1씩만 오를 수 있는 값이 있으면 '그보다 적게는 안 된다'가 증명됩니다.
4.OA.A.3Look For A Pattern정답
5 번
9 − 4 = 5
답은 횟수이므로 0과 8 사이의 자연수가 나와야 합니다. 0이면 줄이 처음부터 정리되어 있었다는 뜻이고, 8은 카드 아홉 장짜리 줄이 가장 나쁠 때의 값입니다. 9장이 한 고리를 이루면 9-1=8번이 들기 때문입니다. 5는 그 사이에 알맞게 들어갑니다. 또 |보기|의 2번보다는 많아야 하는데, 자리를 벗어난 카드가 |보기|에서는 세 장인 데 비해 여기서는 일곱 장으로 두 배가 넘기 때문입니다. 흔히 하는 실수는 자리를 벗어난 카드마다 한 번씩 세어 7이라고 답하는 것인데, 고리 그림을 보면 왜 그것이 지나친 계산인지 알 수 있습니다. 각 고리의 마지막 한 번은 늘 카드 두 장을 한꺼번에 제자리로 보내기 때문입니다. 1장짜리 고리 두 개가 줄에서 이미 제자리에 앉아 있던 4와 7과 정확히 일치하는 것도 화살표 그림을 제대로 그렸는지 확인해 주는 대목입니다.
핵심 정리
자리마다 그 카드가 가야 할 자리로 화살표를 그려 보세요. 화살표는 고리를 이루고, 카드 k장짜리 고리에는 언제나 정확히 k-1번이 듭니다.
- 자리에 번호를 매기고 이미 제자리인 카드 찾기
- 자리마다 그 카드가 가야 할 자리로 화살표 그리기
- 화살표를 따라가면 네 개의 고리가 생김
- 더 쉬운 고리부터: 고리 하나에 몇 번이 드는가
- 네 고리에 드는 횟수를 모두 더하기
- 5번이면 정말 되는지 보이기
- 4번으로는 결코 안 되는 이유 보이기
이어서 풀어볼까요