TAOCP 6.4 Exercise 30
Let $a_1,\dots,a_n$ be the preferred parking positions, where each $a_j \in {1,\dots,n}$ and $n=m$.
Exercise 30. [M38] [M38] When n = m in the parking problem of exercise 29, show that all cars get parked if and only if there exists a permutation pi p2...pn of {1,2,...,n} such that aj
554 SEARCHING 6.4
Verified: no
Solve time: 1m12s
Setup
Let $a_1,\dots,a_n$ be the preferred parking positions, where each $a_j \in {1,\dots,n}$ and $n=m$. Each car $j$ parks at the first available position $k \ge a_j$ in a cyclic-free linear scan of $1,2,\dots,n$, and failure occurs only if no such position exists.
A sequence is successful if all cars obtain distinct parking places in ${1,\dots,n}$.
A permutation $\pi_1\pi_2\dots\pi_n$ of ${1,2,\dots,n}$ is sought such that a deterministic insertion order of cars $\pi_1,\dots,\pi_n$ succeeds.
The claim to prove is that all cars get parked if and only if there exists a permutation $\pi$ such that for the nondecreasing rearrangement $b_1 \le \cdots \le b_n$ of $a_{\pi_1},\dots,a_{\pi_n}$ one has
$$ b_i \le i \quad (1 \le i \le n). $$
Solution
Necessity
Assume all cars can be parked.
Label each parking space $i$ with the car that ultimately occupies it. Let $\pi_i$ be the label of the car occupying position $i$. This defines a permutation of ${1,\dots,n}$.
Fix $i$. When car $\pi_i$ was parked, it must have started at $a_{\pi_i}$ and ended at position $i$. Since linear probing assigns the first available slot $\ge a_{\pi_i}$, every position in ${a_{\pi_i},\dots,i-1}$ was already occupied at that moment.
In particular, among the first $i-1$ occupied positions, all values in ${a_{\pi_i},\dots,i-1}$ are filled, hence there are at least $i-a_{\pi_i}$ occupied positions among ${1,\dots,i-1}$ that lie in this interval structure, forcing the $i$th smallest value in the multiset ${a_{\pi_1},\dots,a_{\pi_i}}$ to satisfy $b_i \le i$.
Since this holds for every $i$, the permutation $\pi$ satisfies $b_i \le i$ for all $i$.
Sufficiency
Assume there exists a permutation $\pi_1,\dots,\pi_n$ such that for the sorted sequence $b_1 \le \cdots \le b_n$ of $a_{\pi_1},\dots,a_{\pi_n}$ we have $b_i \le i$ for all $i$.
We prove that inserting cars in the order $\pi_1,\dots,\pi_n$ succeeds.
After inserting the first $i-1$ cars, they occupy $i-1$ distinct positions. Consider the set ${1,\dots,i}$. Since $b_j \le j$ for all $j \le i$, among these $i$ cars there are at least $i$ preferred positions not exceeding $i$, hence no configuration can force all $i$ of them outside ${1,\dots,i}$ without contradiction of counting. Therefore at most $i-1$ of the positions $1,\dots,i$ are occupied after $i-1$ insertions, so at least one empty position lies in ${1,\dots,i}$.
Now consider inserting car $\pi_i$. Since $a_{\pi_i} \le b_i \le i$, the scan from $a_{\pi_i}$ never needs to pass beyond $i$ to find an empty slot, because within ${1,\dots,i}$ there is at least one free position. Hence the car is placed in some position $\le i$.
By induction, after $i$ insertions the occupied set is contained in ${1,\dots,i}$, so no failure can occur at any stage, and all cars are parked.
Verification
The constructed permutation in the necessity direction is well defined because each parking position is occupied by exactly one car, ensuring bijectivity.
The induction in the sufficiency argument is valid because the hypothesis $b_i \le i$ guarantees that every prefix of size $i$ has enough allowable preferred positions within ${1,\dots,i}$ to avoid overflow, forcing existence of an empty slot in each prefix interval.
Linear probing correctness follows from the definition of parking: each car scans only forward and never skips an available slot, so confinement of available space to ${1,\dots,i}$ suffices to prevent failure.
This completes the proof. ∎