Maths Olympiad Prep

Library / /18 of 37

Combinatorics Difficulty 6.8 National olympiad Find the answer

Let SS be a set, S=35|S|=35. A set FF of mappings from SS to itself is called to be satisfying property P(k)P(k), if for any x,ySx,y\in S, there exist f1,,fkFf_1, \cdots, f_k \in F (not necessarily different), such that fk(fk1((f1(x))))=fk(fk1((f1(y))))f_k(f_{k-1}(\cdots (f_1(x))))=f_k(f_{k-1}(\cdots (f_1(y)))).
Find the least positive integer mm, such that if FF satisfies property P(2019)P(2019), then it also satisfies property P(m)P(m).

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let S S be a set with S=35 |S| = 35 . A set F F of mappings from S S to itself is said to satisfy property P(k) P(k) if for any x,yS x, y \in S , there exist f1,f2,,fkF f_1, f_2, \ldots, f_k \in F (not necessarily different) such that fk(fk1((f1(x))))=fk(fk1((f1(y)))) f_k(f_{k-1}(\cdots (f_1(x)) \cdots )) = f_k(f_{k-1}(\cdots (f_1(y)) \cdots )) .

We aim to find the least positive integer m m such that if F F satisfies property P(2019) P(2019) , then it also satisfies property P(m) P(m) .

To determine this, consider a minimal length sequence of mappings fk,fk1,,f1 f_k, f_{k-1}, \ldots, f_1 such that fk(fk1((f1(x))))=fk(fk1((f1(y)))) f_k(f_{k-1}(\cdots (f_1(x)) \cdots )) = f_k(f_{k-1}(\cdots (f_1(y)) \cdots )) for fixed x,yS x, y \in S . Denote gi(x)=fi(fi1((f1(x)))) g_i(x) = f_i(f_{i-1}(\cdots (f_1(x)) \cdots )) , with g0(x)=x g_0(x) = x .

Let Ai A_i be the unordered pair (gi(x),gi(y)) (g_i(x), g_i(y)) . The key claim is that A0,A1,,Ak A_0, A_1, \ldots, A_k are all distinct, and Ak A_k is the only pair consisting of two equal elements. If there exist two equal pairs Ai A_i and Aj A_j (where i<j i < j ), we can use the functions fk,fk1,,fj+1,fi,fi1,,f1 f_k, f_{k-1}, \ldots, f_{j+1}, f_i, f_{i-1}, \ldots, f_1 instead to obtain equal final values, contradicting the assumption that fk,fk1,,f1 f_k, f_{k-1}, \ldots, f_1 is a minimal length sequence.

Hence, the maximum length of the sequence is at most the number of unordered pairs of distinct elements, which is exactly (352) \binom{35}{2} .

To construct such a sequence, let S={0,1,,34} S = \{0, 1, \ldots, 34\} and define two mappings f(x) f(x) and g(x) g(x) as follows:
f(x)=(x+1)(mod35), f(x) = (x + 1) \pmod{35},
g(0)=1,g(x)=x for all 1x34. g(0) = 1, \quad g(x) = x \text{ for all } 1 \leq x \leq 34.

Using these functions on (x,y)=(1,18) (x, y) = (1, 18) , we apply f f 34 times to turn (1,18) (1, 18) into (0,17) (0, 17) , then apply g g to turn it into (1,17) (1, 17) . Repeating this process another 16 times yields (1,1) (1, 1) after 35×17=595=(352) 35 \times 17 = 595 = \binom{35}{2} functions.

Thus, the least positive integer m m such that if F F satisfies property P(2019) P(2019) , then it also satisfies property P(m) P(m) is (352) \binom{35}{2} .

The answer is: 595\boxed{595}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.