Problem
Fewest swaps to sort number cards
Nine cards read 5, 3, 2, 4, 6, 8, 7, 9, 1 from the left. One move swaps any two cards. They need not be next to each other. Find the fewest swaps to sort them.
Reasoning · Grade 6-2 Swapping and Flipping
Your answer
Watch out One swap per misplaced card overcounts: a ring costs one less than its length.
How to solve
Strategy Draw a Diagram — The tangle becomes simple the moment you draw an arrow from each place to the place where the card sitting there belongs. Follow the arrows and they never wander off -- they always come back and close into rings, so the nine cards fall apart into a few separate rings that never interfere with each other. That picture does two jobs at once. First, an easier related problem -- a ring of just 2 cards, then a ring of 3 -- shows that a ring of k cards costs exactly k-1 swaps, which tells me how many swaps are enough. Second, watching what a single swap does to the number of rings gives the reason no shorter way exists, which an exhibited sequence of swaps could never give on its own.
1STEP 1
Number the places and see which cards are already home
Already home are the 4 and the 7.
Matching a card against its place number is one glance per card, so a row that looks like a mess is really just nine easy yes-or-no checks.
4.OA.C.5Make A Systematic List2STEP 2
Draw an arrow from each place to the place its card belongs in
Draw an arrow from each place to its target.
1 → 5, 2 → 3, 3 → 2, 4 → 4, 5 → 6, 6 → 8, 7 → 7, 8 → 9, 9 → 1
One arrow out and one arrow in at every place is exactly the picture you get from any rearrangement of a set of cards, and it is what forces the arrows to close into rings instead of trailing off.
4.OA.C.5Draw A Diagram3STEP 3
Follow the arrows -- they close into four rings
The arrows close into four rings.
(1 5 6 8 9), (2 3), (4), (7)
Walking a chain of arrows and coming back to the start is something a fourth grader can just do with a finger, and the sizes adding to 9 is the built-in check that nothing was missed.
4.OA.C.5Draw A Diagram4STEP 4
An easier ring first: how many swaps does one ring cost?
A ring costs one less than its length.
ring of k → k-1 swaps
Trying the two smallest rings by hand is quicker than reasoning about nine cards, and the rule it reveals -- one swap retires one card -- is easy to believe because you can watch it happen.
4.OA.C.5Solve An Easier Related ProblemA ring of k cards costs exactly k minus one swaps to sort.
Why?
Each swap puts exactly one card into its home and shortens the ring by one, so cards and swaps match up with one card left over.
🧱One-to-one correspondenceIf each thing here pairs with exactly one thing there, the two groups are the same size.
Why?
The whole job is its separate rings sorted one after another, so the total cost is the ring costs added together.
🧱Whole is the sum of its partsBreak a thing into pieces with no gaps or overlaps and the pieces add back to the whole.
5STEP 5
Add up what the four rings cost
The four rings total 5 swaps.
4 + 1 + 0 + 0 = 5 and 9 - 4 = 5
Two different routes to the same 5 -- ring by ring, and cards minus rings -- is a free check on the arithmetic.
4.OA.A.3Look For A Pattern6STEP 6
Show that 5 swaps really work
Five swaps really sort them.
Writing the row out after every single swap makes the claim checkable one line at a time, with no trust required.
4.OA.C.5Make A Systematic List7STEP 7
Show that 4 swaps could never be enough
Four swaps cannot suffice.
9 - 4 = 5
Counting rings is the honest part of the argument: an exhibited list of swaps only ever proves that many are enough, while a quantity that can climb by at most 1 per move is what proves fewer are impossible.
4.OA.A.3Look For A PatternAnswer
5 swaps
9 − 4 = 5
The answer is a count of moves, so a whole number between 0 and 8 is what to expect: 0 would mean the row was already sorted, and 8 is the worst any nine-card row can be (one single ring of 9, costing 9-1=8). Getting 5 sits sensibly inside that range, and it should be more than the Example's 2 because there are more than twice as many cards out of place -- seven cards need moving here against three in the Example. A common wrong answer is 7, one swap per misplaced card; the ring picture shows why that overcounts, since the last swap in each ring always fixes two cards at once. The two rings of one, the 4 and the 7, are exactly the two cards the row shows already sitting in their own places, which is a direct check that the arrow diagram was drawn correctly.
Takeaway
Draw an arrow from each place to where its card belongs -- the arrows close into rings, and a ring of k cards always costs exactly k-1 swaps.
- Number the places and see which cards are already home
- Draw an arrow from each place to the place its card belongs in
- Follow the arrows -- they close into four rings
- An easier ring first: how many swaps does one ring cost?
- Add up what the four rings cost
- Show that 5 swaps really work
- Show that 4 swaps could never be enough