Class Photos - Proof

Claim: If a valid arrangement exists, the sorted arrangement works. Proof by exchange: Suppose we have a valid arrangement but the front row is not sorted. There exist positions $i < j$ with $front[i] > front[j]$. Since the arrangement is valid: $back[i] > front[i]$ and $back[j] > front[j]$. Swap front[i] and front[j]:

• New pair at i: back[i] vs front[j]. Since $back[i] > front[i] > front[j]$, valid.
• New pair at j: back[j] vs front[i]. We need $back[j] > front[i]$. If $back[j] > front[i]$, swap works. Otherwise, original arrangement was invalid. By similar argument, sorting back row also maintains validity.