Let the language $L_n$ have character set $\Sigma=\{a_1, ..., a_n\}$. $L_n$ has exactly those words which contain some character an odd number of times. That is to say, $\forall w\in L_n\exists a\in \Sigma$ such that $a$ occurs in $w$ an odd number of times. Equivalently if $L_n^i$ is the language with each word containing an odd number of $a_i$ then $L_n = L_n^1\cup ...\cup L_n^n$.
I have already produced an NFA that accepts $L_n$ and a DFA of $2^n$ states which does as well.
I now need to prove that this is the smallest DFA accepting this language. I am given the hint to suppose that there is a DFA of $k<2^n$ states which accepts $L_n$, and then show that there are some strings $u,v\in \Sigma^*$ where $u$ contains $a$ and odd number of times, $v$ contains it an even number of times, and the DFA must terminate on both at the same state.
I've been trying to take the $2^n$ as a strong hint, like maybe consider all strings of length $n$, but there are $n^n$ of these. Maybe consider all strings of length $n$ using only characters $a,b$. Since there are $k<2^n$ states, then some two strings like this must be sent to the same state. The rejected strings in this set are those with even numbers of $a$ and $b$ but I have no way of knowing if two such instances of these go to the same state, or if they did, how that would even matter.
Maybe consider all choices of strings where $a_1$ occurs either once or 0 times, and $a_2$ occurs once or 0 times, etc. There are $2^n$ choices of these so some 2 of these must go to the same state. The only string not in the language here is the empty string. Still I'm stuck.