I have added an example. This is still not tight because it is linear in $b$.

Thank you very much. The first and third question have been solved using your sulution. Also, it can be used to solve question 2. Let $x$ be the number of pairs $(i,j)$ such that $|S_i \cap S_j|\ge (n-1)/2$, then $xn+\left(\binom{n+1}{2}-x\right)\frac {n-3} 2 \ge \frac{{{n^2}(n - 1)(n + 1)}}{{4n}}$. Solving $x$ leads to $x \geqslant \frac{{n(n + 1)}}{{n + 3}}$, namely $x=\Omega(n)$.

I completely understand. This sulution is perfect! It has a really tight bound (in the following sutuation: $p=515,q=508$ and $n=3085$, $a_n$ have already been greater than $2^{13}-1$). $3085 \times 16/3=16453$, just greater than $2^{14}$, amazing!

Yes, I do. I use the simplest way to write a program that spends $O(pqn)$ time to validate the results.

I draw the conclusion by enumerating all of $p,q,n$, but this approch is too awful! I think It can only be used to validate a conclusion, not prove.