Maths Olympiad Prep

Library / /37 of 65

Algebra Difficulty 6.1 National Olympiad Prove it Bulgaria

Problem:

Let mm be a positive integer, A={m,m+1,,m1,m}A=\{-m,-m+1, \ldots, m-1, m\} and f:AAf: A \rightarrow A be a function such that f(f(n))=nf(f(n))=-n for every nAn \in A.

a) Prove that the number mm is even.

b) Find the number of all functions f:AAf: A \rightarrow A with the required property.

Solution

Solution:

a.
Let nAn \in A and On={n,f(n),n,f(n)}O_{n}=\{n, f(n),-n, f(-n)\}. Since f(f(n))=nf(f(n))=-n and f(f(n))=nf(f(-n))=n, it follows easily that if kAk \in A then either Ok=OnO_{k}=O_{n} or OnOk=O_{n} \cap O_{k}=\varnothing. Moreover, we obtain f(n)f(n)f(n) \neq f(-n) for n0n \neq 0.

Further, if f(±n)=±nf( \pm n)= \pm n, then n=f(f(±n))=f(±n)=±n\mp n=f(f( \pm n))=f( \pm n)= \pm n, i.e. n=0n=0. Also, f(±n)=nf( \pm n)=\mp n gives n=f(f(±n))=f(n)\mp n=f(f( \pm n))=f(\mp n) and then n=0n=0. Therefore On=4|O_{n}|=4 for n0n \neq 0 which means that A{0}A \setminus \{0\} splits into disjoint quadruples. In particular, the number mm is even.

b.
Let m=2km=2k and f:AAf: A \rightarrow A be a function with the desired property. Set A+={1,2,,m}A_{+}=\{1,2, \ldots, m\}. We note that f(n)=f(f(f(n)))=f(n)f(-n)=f(f(f(n)))=-f(n) and, in particular, f(0)=0f(0)=0. Hence for n0n \neq 0 either f(n)>0f(n)>0 or f(n)<0f(-n)<0. This means that the quadruple OnO_{n} is uniquely determined by a pair (n,f(n))(n', f(n')) of distinct numbers from A+A_{+}(n,f(n))(n, f(n)) or (f(n),n)(f(-n), n). Therefore ff induces a pairing of A+A_{+} into ordered pairs.

Conversely, any pairing of A+A_{+} into ordered pairs (n,k)(n, k) defines a function with the required properties by setting
f(0)=0,f(n)=k,f(k)=n,f(n)=k,f(k)=n f(0)=0, \quad f(n)=k, \quad f(k)=-n, \quad f(-n)=-k, \quad f(-k)=n
It remains to count the number of the pairings of A+A_{+} into ordered pairs. Ordering all pairs of a given pairing one after another (this can be done in k!k! ways) we obtain a permutation of the numbers 1,2,,m1,2, \ldots, m. This gives classes of "equivalent" permutations of k!k! elements. Therefore the required number is equal to m!k!\frac{m!}{k!}.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.