Problem

Source: Junior Olympiad of Malaysia Shortlist 2015 C3

Tags: function, combinatorics



Let $ n\ge 2 $ be a positive integer and $ S= \{1,2,\cdots ,n\} $. Let two functions $ f:S \rightarrow \{1,-1\} $ and $ g:S \rightarrow S $ satisfy: i) $ f(x)f(y)=f(x+y) , \forall x,y \in S $ ii) $ f(g(x))=f(x) , \forall x \in S $ iii) $f(x+n)=f(x) ,\forall x \in S$ iv) $ g $ is bijective. Find the number of pair of such functions $ (f,g)$ for every $n$.