- Practice
- About 13 min
- 5 practice questions
Counting steps: which step, how many steps, and when the machine stops
Answer the three step-counting questions that follow every machine: what a given step looks like, in which step an arrangement appears, and how many steps the machine needs.
If something looks wrong, please tell us.
Once you know the rule of a machine, the exam usually asks one of three things: what the arrangement is at a named step, in which step a given arrangement appears, or how many steps the machine takes to finish. The first needs careful writing, the second needs a rule about the first appearance, and the third has a neat shortcut. This lesson uses a machine you have already met.
The machine
At each step, the item that should come next in the final order moves to its place from the left. In Step I the smallest number moves to the first place, in Step II the second smallest moves to the second place, and so on. The items that are not moving keep their relative order and slide along.
Worked example 1: ascending numbers
Input: 48 15 72 30 63. The final order is 15, 30, 48, 63, 72.
| Step | Arrangement |
|---|---|
| Input | 48 15 72 30 63 |
| I | 15 48 72 30 63 |
| II | 15 30 48 72 63 |
| III | 15 30 48 72 63 |
| IV | 15 30 48 63 72 |
Look at Step III. The number 48 is already in the third place, so nothing changes, but Step III still counts. The machine finishes at Step IV. If a question asks 'in which step does the arrangement 15 30 48 72 63 first appear', the answer is Step II, because Step III only repeats it. Always give the first step.
A shortcut for the number of steps
After each step, look at the items still waiting to be placed. The machine stops as soon as those waiting items are already in the right order among themselves. In the example, the waiting items after Step II are 48 72 63, which are not in order (72 is before 63). After Step III the waiting items are 72 63, still not in order. After Step IV only 72 is waiting, so the machine is finished.
The machine stops when the items still waiting are already in order. A step in which nothing moves still counts as a step.
Worked example 2: stopping early
Input: 12 20 35 18 40. Step I: 12 is already first, so the line is unchanged. The waiting items 20 35 18 40 are not in order. Step II: 18 moves to the second place, giving 12 18 20 35 40. The waiting items 20 35 40 are in order, so the machine stops at Step II.
Worked example 3: words, then descending numbers
Alphabetical machine, input: tea oil jam fig. Step I: fig moves to the front, giving fig tea oil jam. Step II: jam moves to second place, giving fig jam tea oil. Step III: oil moves to third place, giving fig jam oil tea, which is complete. The machine takes 3 steps.
Now a descending machine, which brings the largest number to the front first. Input: 18 42 7 35 26.
| Step | Arrangement |
|---|---|
| Input | 18 42 7 35 26 |
| I | 42 18 7 35 26 |
| II | 42 35 18 7 26 |
| III | 42 35 26 18 7 |
The line 42 35 26 18 7 first appears in Step III.
Question types and how to answer them
- What is Step k? Write every step in order; do not jump ahead.
- In which step does X appear? Give the first step at which it appears.
- How many steps? Use the waiting-items check, or write steps until the line stops changing for good.
- Which item is in the third place at Step II? Write the step in full and read off the place.
Key takeaways. Write each step in full. A step with no change still counts. Report the first step at which an arrangement appears. The machine stops when the remaining items are in order.
Check your understanding
-
1. Ascending machine (smallest to the left first). Input: 36 14 50 22 45. What is Step II?
- 14 22 36 50 45
- 14 36 50 22 45
- 14 22 50 36 45
- 14 22 36 45 50
Show answer
Answer: A. Step I: 14 moves to the front, giving 14 36 50 22 45. Step II: 22 moves to second place, giving 14 22 36 50 45.
-
2. Ascending machine (smallest to the left first). Input: 36 14 50 22 45. How many steps does it take to finish?
- 3
- 4
- 5
- 2
Show answer
Answer: B. Step III leaves 14 22 36 50 45 unchanged because 36 is already in third place. Step IV moves 45 to fourth place, giving 14 22 36 45 50. So the machine takes 4 steps.
-
3. Ascending machine. Input: 8 15 31 22 40. How many steps does it take?
- 2
- 4
- 3
- 5
Show answer
Answer: C. Steps I and II change nothing, since 8 and 15 are already in place. Step III moves 22 to third place, giving 8 15 22 31 40, which is complete. So there are 3 steps.
-
4. Alphabetical machine (first in the dictionary goes to the front first). Input: tea oil jam fig. What is Step II?
- fig tea oil jam
- fig jam oil tea
- jam fig tea oil
- fig jam tea oil
Show answer
Answer: D. Step I: fig moves to the front, giving fig tea oil jam. Step II: jam moves to second place, giving fig jam tea oil.
-
5. Descending machine (largest to the left first). Input: 18 42 7 35 26. In which step does the line 42 35 26 18 7 first appear?
- Step I
- Step III
- Step II
- Step IV
Show answer
Answer: B. Step I: 42 18 7 35 26. Step II: 42 35 18 7 26. Step III: 42 35 26 18 7. This is the first step at which the line appears.
Sign in to keep track of the lessons you finish.