Stop exactly at 10
Tonight's idea
A cart sits at rest at 0 on a track. Once a second you choose a push: forwards (\(+1\)), none (\(0\)) or backwards (\(-1\)). The push changes the speed, then the cart rolls by its new speed.
New speed = old speed + push. New position = old position + new speed.
You want the cart parked at 10 (position 10, speed 0) in as few seconds as you can. Choosing actions over time to reach a goal at the least cost is called optimal control. Here the cost is time.
Tonight's trick: write the list of speeds, one per second. A list is allowed when it starts with \(1\), \(0\) or \(-1\) and ends with 0, and each speed differs from the one before by at most 1. The cart ends at the sum of the list.
A computer can simply try every plan: 7 seconds allow \(3^7 = 2187\) plans, and exactly 3 park the cart at 10. Cutting time into steps and searching is a standard computer method for control problems. The cart is a model: real pushes and real time are not whole numbers.
Watch one: push forwards all the way
The greedy plan is to push forwards every second. After 4 seconds the cart is at 10, but it is moving at speed 4. Brake as hard as the rules allow and it still rolls on:
| second | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| push | \(+1\) | \(+1\) | \(+1\) | \(+1\) | \(-1\) | \(-1\) | \(-1\) | \(-1\) |
| speed | \(1\) | \(2\) | \(3\) | \(4\) | \(3\) | \(2\) | \(1\) | \(0\) |
| position | \(1\) | \(3\) | \(6\) | \(10\) | \(13\) | \(15\) | \(16\) | \(16\) |
The cart parks at 16, not 10. Losing speed 4 takes 4 seconds, and in those seconds it rolls \(3 + 2 + 1 + 0 = 6\) further. To park at 10 you must start braking before you get there. In the picture each square is one step along the track: 10 blue squares while speeding up, 6 orange while braking.
Your turn
- Find an allowed list of 7 speeds that adds up to 10. Write the push for each second, and check the cart's position second by second.
- Now show that 6 seconds are not enough. (a) Explain why the speed in second \(k\) is at most \(k\). (b) In a 6-second plan the last speed is 0. Explain why the speed in second \(k\) is also at most \(6 - k\). (c) Write the largest speed each second can have, and add them up. (d) Why can no plan of 5 seconds or fewer work either?
- Find the fastest plan that parks the cart at 9, and the fastest that parks it at 16. For each, explain why one second fewer is impossible.
- (a) Find the fastest plan that parks the cart at 12, and say why nothing is faster. (b) How many seconds does 13 need? Give a speed list. (c) Fill in the farthest place the cart can be parked in 2, 3, 4, 5, 6, 7 and 8 seconds. What do you notice about the answers for 2, 4, 6 and 8 seconds?
Stretch: square targets
Let \(n\) be a whole number, 1 or more. Show that parking the cart at \(n^2\) takes exactly \(2n\) seconds. You need two things: a list of \(2n\) speeds that adds up to \(n^2\), and a reason why \(2n - 1\) seconds can never be enough. Check your argument on \(n = 1\).
Answers
- One answer: speeds \(1, 2, 2, 2, 2, 1, 0\), from pushes \(+1, +1, 0, 0, 0, -1, -1\). Positions: \(1, 3, 5, 7, 9, 10, 10\). There are exactly two other answers, \(1, 2, 3, 2, 1, 1, 0\) and \(1, 1, 2, 3, 2, 1, 0\). These are the 3 plans the computer found.
- (a) The cart starts at rest and each push adds at most 1, so after \(k\) pushes the speed is at most \(k\). (b) Each push takes away at most 1. After second \(k\) there are \(6 - k\) pushes left, and they must bring the speed down to 0, so it cannot be more than \(6 - k\). (c) The limits are \(1, 2, 3, 2, 1, 0\) (the smaller of \(k\) and \(6 - k\)), which add up to 9. So a 6-second plan parks the cart at 9 or less, never at 10. (d) A shorter plan could be stretched to 6 seconds by waiting at 0 first (pushes of 0 at the start change nothing). So if 5 seconds or fewer worked, 6 would work too.
- For 9: the list \(1, 2, 3, 2, 1, 0\), which takes 6 seconds. In 5 seconds the limits are \(1, 2, 2, 1, 0\), which add up to only 6. For 16: the list \(1, 2, 3, 4, 3, 2, 1, 0\) from the worked example, 8 seconds. In 7 seconds the limits are \(1, 2, 3, 3, 2, 1, 0\), which add up to only 12. So the greedy plan was not the fastest way to 10, but it is the fastest way to 16.
- (a) The list \(1, 2, 3, 3, 2, 1, 0\) adds up to 12 and takes 7 seconds. Six seconds reach at most 9. (b) 13 needs 8 seconds, because 7 seconds reach at most 12. One list is \(1, 2, 3, 3, 2, 1, 1, 0\). (c) Adding the limits gives 1, 2, 4, 6, 9, 12, 16 for 2 to 8 seconds, and the list of limits is itself an allowed list, so the cart really gets that far. The even times, 2, 4, 6 and 8 seconds, give 1, 4, 9, 16: the square numbers.
Stretch. The list \(1, 2, \ldots, n-1, n, n-1, \ldots, 2, 1, 0\) has \(2n\) entries and is allowed. Its sum is \((1 + 2 + \cdots + n) + (1 + 2 + \cdots + (n-1)) = \tfrac{n(n+1)}{2} + \tfrac{n(n-1)}{2} = n^2\). With \(2n - 1\) seconds, the speed in second \(k\) is at most \(k\) and at most \(2n - 1 - k\), so the limits are \(1, 2, \ldots, n-1, n-1, \ldots, 2, 1, 0\). They add up to \(n(n-1) = n^2 - n\), which is less than \(n^2\). Fewer seconds are no better, since a shorter plan can wait at 0 first. For \(n = 1\): the list \(1, 0\) parks at 1 in 2 seconds, and a 1-second plan must have speed 0, so it goes nowhere. The winning plan is to push as hard as you can for the first half and brake as hard as you can for the second. Engineers call a plan like that bang-bang control.