4
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ The number of truncations of the representation of $s$ is more than the whole size of the group, therefore there must be repetitions (two truncations that are equal). $\endgroup$
    – orole
    Feb 2, 2018 at 18:50
  • $\begingroup$ @orole Could you please elaborate? I understand the pigeonhole problem in regards to say balls and cells weren't one cell must have at least two balls but not in this context... $\endgroup$ Feb 2, 2018 at 19:31
  • $\begingroup$ Cells: The number of elements of the group, all the elements there are ($|G|$). Balls: The number of truncations (assumed to be $r>|G|$) of the shortest representation of $s$, which are in particular elements of the group, i.e. 'fall in the cells'. $\endgroup$
    – orole
    Feb 2, 2018 at 19:59
  • $\begingroup$ The cyclic-groups tag is inappropriate so I removed it. $\endgroup$
    – Shaun
    Feb 4, 2018 at 15:48

1 Answer 1

1
$\begingroup$

$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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .