I was looking at the Putnam 2016 competition and saw question A5, as stated:
Suppose that $G$ is a finite group generated by the two elements $g$ and $h$, where the order of $g$ is odd. Show that every element of G can be written in the form $g^{m_1}h^{n_1}g^{m_2}h^{n_2}...g^{m_r}h^{n_r}$ with $1\le{r}\le{|G|}$ and $m_1,n_1,m_2,n_2,...,m_r,n_r\in{(-1,1)}$.
Now I can prove the existence that every element of G can be written in this form however I struggle with showing that $1\le{r}\le{|G|}$. Following the Putnam solution on http://kskedlaya.org/putnam-archive/2016s.pdf I can follow the whole proof, apart from the part 'since $r>|G|$ by hypothesis, by the pigeonhole principle there must exist indices $0\le{i}<j\le{r-1}$ such that $s_i=s_j$.' I don't understand how the logic follows from the pigeonhole principle and would be very grateful to anyone who could show me why. Thank you
$s_0,s_1,...s_{r-1}\in G$. Since the LHS has $r$ elements but the RHS has only $|G|<r$, two elements on the left must be the same.