To Park or Not to Park

Pari Ford took the lead on this activity for the 2012 Circle on the Road festival.

AUDIENCE: Teachers (middle school teachers in particular)

PLANNING ABSTRACT:
Who would have thought parking your car could be expressed as an algebraic function?!? We are going to take a look at a problem that deals with parking cars in a one-way parking lot. Each driver in a line of cars will choose which parking spot they prefer to park in. The list of preferred parking spots is called a parking sequence. When they come to their desired parking spot, if it is open they can park there, if it is not open, they will park in the next open spot. Not all parking sequences result in all cars ending in a parking spot. There are many arrangements that do result in all cars in a parking spot. We will work to find how many of these sequences exist. We will also consider the scenario where we have a round-a-bout parking lot. You’ll never think of parking your car in the same way!

PUBLIC ABSTRACT: 
Who would have thought parking your car could be expressed as an algebraic function?!? We are going to take a look at a problem that deals with parking cars in a one-way parking lot. Each driver in a line of cars will choose which parking spot they prefer to park in. The list of preferred parking spots is called a parking sequence. When they come to their desired parking spot, if it is open they can park there, if it is not open, they will park in the next open spot. Not all parking sequences result in all cars ending in a parking spot. There are many arrangements that do result in all cars in a parking spot. We will work to find how many of these sequences exist. We will also consider the scenario where we have a round-a-bout parking lot. You’ll never think of parking your car in the same way!

APPRENTICES: Emilly M, Gordon Hamilton, Cheryll E. Crowe, Trevor M, Kathleen Lopez, Ina Loobeek, Vinton Geistfeld, Nancy Williams

DISCUSSION:

We have a line of n parking spots on the right side of a one way street. The sequence (p_1, p_2, … , p_n) is the list of preferred parking spots for n cars. p_1 is the first car’s preferred spot, p_2 is the second cars preferred spot, and so on.

As the cars go down the street in increasing order, they park in their preferred spot if it is available. If their preferred spot is already taken, they take the next available spot. They cannot turn around, back up, or go around the block to try again.

A parking sequence is successful if all n cars find a parking spot. (1,1,1,1,1,…,1) and (1,2,3,4,…,n) are both successful parking sequences.

(n,n,1,1,…,1) is not a successful parking sequence. The question is, how many successful parking sequences are there?

After experimenting with several specific examples for the number of cars, develop a conjecture for the number of successful sequences. What are some rules for a parking sequence to be successful or not?

If all cars prefer a different spot, then we have a successful parking sequence. So the number of successful parking sequences is at least n!.

If no cars prefer the first parking spot, then we do not have a successful parking sequence. This leads to an upper bound for the number of successful parking sequences of n^n – (n-1)^n.

You may be able to list all successful parking sequences for n=1, 2, 3, and 4. The answer is quite large for n > 4. Thus, we introduce a new scenario.

Round-a-bout scenario: we have a round-a-bout with (n+1) parking spots on the right side and we label the spots from when you enter the round-a-bout (I.e. culdesac). There are still only n cars and (p_1, p_2, … , p_n) is the list of preferred parking spots for n cars. p_1 is the first car’s preferred spot, p_2 is the second cars preferred spot, and so on.

As the cars go around the round-a-bout in increasing order, they park in their preferred spot if it is available. If their preferred spot is already taken, they take the next available spot and they can go around the circle to park in the next available spot They cannot turn around or back up.

All parking sequences in this scenario are successful; there are (n+1)^n of these parking sequences. How do these parking sequences connect to the original problem?

As my first message to the group (Hi, everyone), let me ask about a sentence fragment. “If all cars prefer a different spot, then we have. Successful parking sequence. So the number of successful parking sequences is at least n!.” The first part appears to want to be read without the period and an “a” inserted.

Now I read this email from the point of view of a high school student, and I’m not sure if that is what I should have done, but that is where my questions come from. My first question would concern the n^n – (n-1)^n upper bound. I see where the n! lower bound is coming from, but not the upper. I personally don’t recall having done basic combinatorics like that until I was in college, so I just don’t know if high school kids can immediately come up with the total number of possible parking sequences. It might be nice to put a line about that. As a side note, when I look at this problem, I assume it would be a lot easier to come up with restrictions to a successful parking sequence versus some magical property that makes them successful. I personally don’t see a quick answer upon first looking at the problem.

For the second half of the problem, perhaps I just don’t see right off why there are n+1 parking spots? It seems like a nuance with the labeling, maybe? This might make the problem too hard, but a fun question to ask could be how many cars can be on the cul de sac at one time that haven’t parked yet? For example, for the parking sequence (n, n-1, …, 2, 1), all the cars would be on the cul de sac and not parked, but for the sequence (1, 2, …, n), the problem is a little trickier. (Assume, of course, some constant speed of one car length per unit time interval.)

So, to sum up my exhaustive email, my concern in the first section is the upper bound that might not be obvious at first glance, and on the second half, I wonder about the seemingly extraneous parking spot.

I look forward to meeting all of you next week, and fyi, I’ll be getting into town a few hours early with the intent of going to the air and space museum. I went to DC with my wife 2 years ago and she hated that part of the trip, so now I want to go solo and nerd out big time!

-Trevor

Attachment
Parking sequences handout.pdf