Recall that in a prior post I asked Is there an NFA for  { ay : y ≠ 1000 } with substantially less than 1000 states. I will now show that any NFA for this set requires 999 states, so essntially 1000. The proof uses Ramsey Theory. I will tell you the little bit of Ramsey Theory that you need. NO- the above is false. There is an NFA with 60 states.  I have a complete exposition her