uniolympiads Ελληνικά

IMC 2024, Day 1, Problem 4

Let gg and hh be two distinct elements of a group GG, and let nn be a positive integer. Consider a sequence w=(w1,w2,… )w = (w_1, w_2, \dots) which is not eventually periodic and where each wiw_i is either gg or hh. Denote by HH the subgroup of GG generated by all elements of the form wkwk+1…wk+n−1w_k w_{k+1} \dots w_{k+n-1} with k≥1k \ge 1. Prove that HH does not depend on the choice of the sequence ww (but may depend on nn).

Original from the official PDFLet g and h be two distinct elements of a group G, and let n be a positive integer. Consider a sequence w = (w 1 , w 2 , . . .) which is not eventually periodic and where each w i is either g or h. Denote by H the subgroup of G generated by all elements of the form w k w k+1 . . . w k+n−1 with k ≥ 1. Prove that H does not depend on the choice of the sequence w (but may depend on n).

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Ivan Mitrofanov, Saarland University)

Solution. Let XmX_m denote the subset of GG of products of the form g1…gmg_1 \dots g_m, where each gig_i is either gg or hh.

Lemma. For all j=1,2,…,nj = 1, 2, \dots, n and for all a,b∈Xja, b \in X_j the ratio a−1ba^{-1}b is contained in HH.

Proof. Induction in jj.

We start with the base case j=1j = 1. By the pigeonhole principle, there exist k<ℓk < \ell for which the sequences (wk+1,…,wk+n−1)(w_{k+1}, \dots, w_{k+n-1}) and (wℓ+1,…,wℓ+n−1)(w_{\ell+1}, \dots, w_{\ell+n-1}) coincide. If wk+m=wℓ+mw_{k+m} = w_{\ell+m} for all positive integer mm, then the sequence ww is eventually periodic with period ℓ−k\ell - k. Thus, there exists m>0m > 0 for which wk+m≠wℓ+mw_{k+m} \neq w_{\ell+m}. We have m⩾nm \geqslant n, so wk+m−i=wℓ+m−iw_{k+m-i} = w_{\ell+m-i} for i=1,2,…,n−1i = 1, 2, \dots, n-1. Therefore, since the products x=wk+m−n+1…wk+mx = w_{k+m-n+1} \dots w_{k+m} and y=wℓ+m−n+1…wℓ+my = w_{\ell+m-n+1} \dots w_{\ell+m} both are elements of HH, the subgroup HH contains their ratios x−1yx^{-1}y and y−1xy^{-1}x. These ratios are equal to g−1hg^{-1}h and h−1gh^{-1}g (in some order), that finishes the proof for j=1j = 1.

Induction step from j−1j - 1 to jj, 2⩽j⩽n2 \leqslant j \leqslant n. We say that an element a∈Xja \in X_j is a gg-element, correspondingly an hh-element, if it can be represented as a=ga1a = ga_1, correspondingly a=ha1a = ha_1, where a1∈Xj−1a_1 \in X_{j-1}. The ratio of two gg-elements, or of two hh-elements, is a ratio of two elements of Xj−1X_{j-1}, thus, it is in HH by the induction hypothesis. Since the property a−1b∈Ha^{-1}b \in H is an equivalence relation on pairs (a,b)(a, b), it suffices to find a gg-element and hh-element whose ratio is in HH.

Define k,ℓ,mk, \ell, m, as in the base case. The subgroup HH contains the products

v=wk+m−n+j…wk+mwk+m+1…wk+m+j−1,u=wℓ+m−n+j…wℓ+mwℓ+m+1…wℓ+m+j−1.\begin{aligned} v &= w_{k+m-n+j} \dots w_{k+m}w_{k+m+1} \dots w_{k+m+j-1}, \\ u &= w_{\ell+m-n+j} \dots w_{\ell+m}w_{\ell+m+1} \dots w_{\ell+m+j-1}. \end{aligned}

Their ratio u−1vu^{-1}v is a ratio of gg-element and an hh-element in XjX_j, since {wk+m,wℓ+m}={g,h}\{w_{k+m}, w_{\ell+m}\} = \{g, h\} and wk+m−i=wℓ+m−iw_{k+m-i} = w_{\ell+m-i} for all i=1,2,…,n−ji = 1, 2, \dots, n-j.

The Lemma for j=nj = n yields that HH is the subgroup of GG generated by XnX_n, and this description does not depend on ww.

Transcribed from the official solutions, pages 4–5. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?