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
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)$.
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.
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.
26.11.2019 13:30
Is this an example for $\binom{35}{2}$? Can you please explain?
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
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$.
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.
26.11.2019 14:39
Just to clean up the solution outlined by WypHxr
26.11.2019 15:11
prtQ wrote: Just to clean up the solution outlined by WypHxr
Wow, nice!
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$.