HMMT February, 2020

Solution:
The answer is $2^{n}-n$.

Let $D=\left(d_{i j}\right)$ be the matrix where $d_{i j}$ is $1$ if $i$ is a divisor of $a_{j}$ and $0$ otherwise. For a subset $S$ of $[n]$, let $D_{S}$ be the matrix obtained from $D$ by flipping $(0 \leftrightarrow 1)$ every entry $d_{i j}$ where $j \notin S$. Observe that $S=S_{\pi}$ if and only if $\left(D_{S}\right)_{\pi(i) i}=1$ for all $i$.

To show that $N \leq 2^{n}-n$ we consider two cases. If all the rows of $D$ are distinct, then there exist $n$ different possibilities for $S$ that set a row equal to zero. In this case, there is clearly no $\pi$ so that $S_{\pi}=S$. Thus there are at most $2^{n}-n$ possible $S_{\pi}$. Otherwise, if two rows in $D$ are the same, then choose an $S_{0}$ such that $D_{S_{0}}$ has two zero rows. Then, the $n+1$ sets $S$ that are at most "one element away" from $S_{0}$ are such that $D_{S}$ only has one column with nonzero entries in those two rows. This makes it impossible for $S_{\pi}=S$ as well, so $N \leq 2^{n}-n-1$.

Now we construct $N=2^{n}-n$ by setting $a_{j}=j$. By Hall's marriage theorem, it suffices to prove the following:

Assuming that $D_{S}$ has no completely-zero rows, given a set $I=\left\{i_{1}, i_{2}, \ldots, i_{k}\right\}$ there exist at least $k$ values of $j$ so that there exists an $i \in I$ so that $\left(D_{S}\right)_{i j}=1$. Call such $j$ admissible.

Without loss of generality assume $i_{1}<i_{2}<\cdots<i_{k}$.

Note that if $\left\{d_{i j} \mid i \in I\right\}=\{0,1\}$, then $j$ is admissible. Therefore the $k-1$ numbers $i_{1}, i_{2}, \ldots, i_{k-1}$ are admissible, since for $\alpha<k, i_{\alpha}$ divides $i_{\alpha}$ but $i_{k}$ does not. So we only need to find one more admissible $j$. Assume that $i_{k}$ is not admissible; now it must be the case that all the $i_{\alpha}$ are divisors of $i_{k}$.

At this point we note that the $k=1$ case is easy, since no row of $D_{S}$ is zero. Moreover, if $k=2$, $\left\{\left(D_{S}\right)_{i_{1} i_{1}},\left(D_{S}\right)_{i_{2} i_{1}}\right\}=\{0,1\}$, so in the row with the zero there must be $1$ somewhere, yielding a second admissible column.

In the case where $k \geq 3$, note that $i_{1} \leq i_{k} / 3$. Therefore $i_{k}-i_{1} \notin I$, but $i_{1}$ divides $i_{k}-i_{1}$ and $i_{k}$ does not. Thus we have found the last admissible column. Having exhausted all cases, we are done.