Let $S$ be a set, $|S|=35$. A set $F$ of mappings from $S$ to itself is called to be satisfying property $P(k)$, if for any $x,y\in S$, there exist $f_1, \cdots, f_k \in F$ (not necessarily different), such that $f_k(f_{k-1}(\cdots (f_1(x))))=f_k(f_{k-1}(\cdots (f_1(y))))$. Find the least positive integer $m$, such that if $F$ satisfies property $P(2019)$, then it also satisfies property $P(m)$.
Problem
Source: 2020 CMO P3
Tags: combinatorics
liekkas
26.11.2019 09:21
Correct version and better formulation of the problem: Let $S$ be a set, $|S|=35$. A set $F$ of mappings from $S$ to itself is called to be satisfying property $P(k)$, if for any $x,y\in S$, there exist $f_1, \cdots, f_k \in F$ (not necessarily different), such that $f_k(f_{k-1}(\cdots (f_1(x))))=f_k(f_{k-1}(\cdots (f_1(y))))$. Find the least positive integer $m$, such that if $F$ satisfies property $P(2019)$, then it also satisfies property $P(m)$.
WypHxr
26.11.2019 13:18
Let us consider $X=\{(x,y): x, y\in S, x\neq y \}$, we link $(x,y)$ and $(x_1, y_1)$ if there exists $f \in F$, such that $f(x)=x_1$, $f(y)=y_1$, then any point in $X$ are linked to $(a, a)$, and we can use $2019$ functions to link $(x,y)$ to $(a,a)$, noticed that $m \geq C_{35}^2$ satisfy because $|X|= C_{35}^2$. Now, we need find a example to explain $C_{35}^2$ is Okay.
WypHxr
26.11.2019 13:27
I have a veay clever student but he failed in the National High School Mathematics League Contest(中国的全国高中数学联赛) and missed CMO. This is my student's example: $f=(12\cdots 35)$, it means $f(1)=2$, $f(2)=3$, $\cdots$, $f(34)=35$, $f(35)=1$, \[g(x)=\begin{cases} 2, & x=1 \\ x, & 1<x\leq 35 \end{cases}\]Just use them to iterate.
oolliivveeerr
26.11.2019 13:30
Is this an example for $\binom{35}{2}$? Can you please explain?
oolliivveeerr
26.11.2019 14:20
WypHxr wrote: I have a veay clever student but he failed in the National High School Mathematics League Contest(中国的全国高中数学联赛) and missed CMO. This is my student's example: $f=(12\cdots 35)$, it means $f(1)=2$, $f(2)=3$, $\cdots$, $f(34)=35$, $f(35)=1$, \[g(x)=\begin{cases} 2, & x=1 \\ x, & 1<x\leq 35 \end{cases}\]Just use them to iterate. I see. It takes at least $\binom{35}{2}$ steps to take $2$ and $19$ to the same element. Nice solution. and p.s. sorry for your student
WypHxr
26.11.2019 14:31
oolliivveeerr wrote: Is this an example for $\binom{35}{2}$? Can you please explain? For example, use 35 functions to make $(1,3)$ to $(1,4)$($(1,3), (2,4),\cdots, (34,1), (34,2), (35,3), (1,4)$), then to $(1,5)$, $\cdots$, $(1,19)$, $(2,19)$. We can prove use $35 \cdot 17$ functions can make $(x,y)$ to $(2,19)$. we only need to consider the distance in a circle, some $f$ and one $g$ make the distance $+1$.
WypHxr
26.11.2019 14:33
oolliivveeerr wrote: WypHxr wrote: I have a veay clever student but he failed in the National High School Mathematics League Contest(中国的全国高中数学联赛) and missed CMO. This is my student's example: $f=(12\cdots 35)$, it means $f(1)=2$, $f(2)=3$, $\cdots$, $f(34)=35$, $f(35)=1$, \[g(x)=\begin{cases} 2, & x=1 \\ x, & 1<x\leq 35 \end{cases}\]Just use them to iterate. I see. It takes at least $\binom{35}{2}$ steps to take $2$ and $19$ to the same element. Nice solution. and p.s. sorry for your student Yes, you are right. His handwriting is terrible and I will help him improve his writing.
prtQ
26.11.2019 14:39
Just to clean up the solution outlined by WypHxr
$\binom{35}{2}$
Consider some set $F$, and let $f_k, f_{k-1}, \cdots , f_1$ be a minimal length sequence of mappings in $F$ such that $f_k(f_{k-1}(\cdots (f_1(x)) \cdots )) = f_k(f_{k-1}(\cdots (f_1(y)) \cdots ))$ for fixed $x,y \in S$ (tiebreak arbitrarily). Denote $g_i(x) = f_i(f_{i-1}(\cdots (f_1(x)) \cdots ))$. Notably, $g_0(x) = x$.
Let $A_i$ be the unordered pair $(g_i(x),g_i(y))$. The key claim is that $A_0, A_1, \cdots , A_k$ are all distinct, and that $A_k$ is the only pair that consists of 2 equal elements. The latter part of the claim is obvious. For the former part of the claim, if there exists 2 equal pairs $A_i$ and $A_j$ (note unordered as we can swap $x$ and $y$) where $i < j$, then we can instead use the functions $f_k, f_{k-1}, \cdots, f_{j+1}, f_i, f_{i-1}, \cdots , f_1$ instead to obtain equal final values, contradicting the assumption that $f_k, f_{k-1}, \cdots , 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 $\binom{35}{2}$.
We let $S = \{0,1,\cdots , 34\}$ for convenience.
Define 2 mappings $f(x)$ and $g(x)$ as follows:
$f(x) = (x+1) \pmod {35}$.
$g(0) = 1, g(x) = x \text{ for all } 1 \leq x \leq 34$
We now attempt to use these 2 functions on $(x,y) = (1,18)$.
We use $f$ 34 times on $(1,18)$ to turn it into $(0,17)$, then $g$ to turn it into $(1,17)$. Repeating the above process another 16 times yields $(1,1)$ after $35 \times 17 = 595 = \binom{35}{2}$ functions. To show that this is minimal, we look at how we use the function $g$. We should only always increase or always decrease the quantity $y - x \pmod {35}$ (decreasing being $17 \rightarrow 16 \rightarrow \cdots \rightarrow 0$ and increasing being $17 \rightarrow 18 \rightarrow \cdots \rightarrow 34 \rightarrow 0$, and consecutive uses of $g$ to decrease this quantity requires 34 uses of $f$ to bring the pair back to 0 (similarly for increasing the quantity). It happens that decreasing $y - x \pmod {35}$ uses less functions.
Hence $m = \binom{35}{2}$ and we are done.
WypHxr
26.11.2019 15:11
prtQ wrote: Just to clean up the solution outlined by WypHxr
$\binom{35}{2}$
Consider some set $F$, and let $f_k, f_{k-1}, \cdots , f_1$ be a minimal length sequence of mappings in $F$ such that $f_k(f_{k-1}(\cdots (f_1(x)) \cdots )) = f_k(f_{k-1}(\cdots (f_1(y)) \cdots ))$ for fixed $x,y \in S$ (tiebreak arbitrarily). Denote $g_i(x) = f_i(f_{i-1}(\cdots (f_1(x)) \cdots ))$. Notably, $g_0(x) = x$.
Let $A_i$ be the unordered pair $(g_i(x),g_i(y))$. The key claim is that $A_0, A_1, \cdots , A_k$ are all distinct, and that $A_k$ is the only pair that consists of 2 equal elements. The latter part of the claim is obvious. For the former part of the claim, if there exists 2 equal pairs $A_i$ and $A_j$ (note unordered as we can swap $x$ and $y$) where $i < j$, then we can instead use the functions $f_k, f_{k-1}, \cdots, f_{j+1}, f_i, f_{i-1}, \cdots , f_1$ instead to obtain equal final values, contradicting the assumption that $f_k, f_{k-1}, \cdots , 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 $\binom{35}{2}$.
We let $S = \{0,1,\cdots , 34\}$ for convenience.
Define 2 mappings $f(x)$ and $g(x)$ as follows:
$f(x) = (x+1) \pmod {35}$.
$g(0) = 1, g(x) = x \text{ for all } 1 \leq x \leq 34$
We now attempt to use these 2 functions on $(x,y) = (1,18)$.
We use $f$ 34 times on $(1,18)$ to turn it into $(0,17)$, then $g$ to turn it into $(1,17)$. Repeating the above process another 16 times yields $(1,1)$ after $35 \times 17 = 595 = \binom{35}{2}$ functions. To show that this is minimal, we look at how we use the function $g$. We should only always increase or always decrease the quantity $y - x \pmod {35}$ (decreasing being $17 \rightarrow 16 \rightarrow \cdots \rightarrow 0$ and increasing being $17 \rightarrow 18 \rightarrow \cdots \rightarrow 34 \rightarrow 0$, and consecutive uses of $g$ to decrease this quantity requires 34 uses of $f$ to bring the pair back to 0 (similarly for increasing the quantity). It happens that decreasing $y - x \pmod {35}$ uses less functions.
Hence $m = \binom{35}{2}$ and we are done.
Wow, nice!
mathaddiction
21.08.2021 05:54
The answer is $\binom{35}{2}=595$. We first show $m\leq 595$. Indeed, for each $(x,y)\in S^2$ define $\delta(x,y)$ to be the minimum number such that there exists $f_1,...,f_{\delta(x,y)}$ with $$f_{\delta(x,y)}(...f_1(x))...)=f_{\delta(x,y)}(...f_1(y))...)$$Let $(x_1,y_1)\in S^2$ be the point such that $\delta(x_1,y_1)=m$ is maximized, now it is easy to see that $$\delta(f_i(...f_1(x)...),f_i(...f_1(y)...)=m-i$$Therefore, each $(f_i(...f_1(x)...),f_i(f_1(y)...))$ are distinct elements in $S^2$, hence $$m\leq |S^2|=\binom{35}{2}=595$$ On the other hand, define $$g(x)=\begin{cases}x&\text{ if }x\neq 1,2\\1&\text{ if }x=1,2\end{cases}$$and $$h(x)=x-1$$it is easy to see that $m\geq 595$.