I think it is a difficult problem. Maybe I am wrong, of course. We need to use two nice results from $n$-valued logic. Definition. Function $f:S^k\to S$ is called essential if it depends on at least 2 arguments. Lemma 1. Suppose $f(x_1,..,x_k)$ is an essential function, $f$ takes $l\geq 3$ values. Let $x_1$ be its essential argument. Then there are three points \[(a,a_2,a_3,...,a_k),\] \[(b,a_2,a_3,...,a_k),\] \[(a,c_2,c_3,...,c_k),\] such that $f$ takes three different values on these points. Proof. Try to do it without exterior help. Lemma 2. Suppose $f(x_1,...,x_k)$ is an essential function, $f$ takes at least $l\geq 3$ values. Then there are $k$ subsets $G_i\subset S$ ($i=1,2,...,k$) s.t. $|G_i|\leq l-1$ and $f$ takes at least $l$ values on $G_1\times G_2\times...\times G_k$. Proof. Using Lemma 1. Theorem. The assertion of the problem is correct. Proof. It is an immediate conclusion from Lemma 2. Hmm... I think you see that the initial problem is solved now. Right? I propose to mathlinkers send the proofs of Lemma 1 and Lemma 2 here. They are quite easy. P.S. The condition $n\geq 3$ is very important for Lemma 1 and Lemma 2. P.P.S. Please, correct my definitions ($n$-valued logic and essential function). I don't know how all these notions sounds in english.

I have another solution. May be it is wrong, or it is similar to Myth's solution, I don't know. We will prove it by induction on $ k $. The case $ k = 1 $ is trivial. Suppose now that $ k \geqslant 2 $. Suppose that we have a function $ f : S^{k} \rightarrow S $, satisfying the conditions of the problem. Then there are two cases: 1) There exist $ a_{2},a_{3}, \ldots , a_{k} \in S $, such that the function $ \varphi : S \rightarrow S $, given as $ \varphi (a):= f(a,a_{2},a_{3}, \ldots ,a_{k}) $, is one-to-one, and hence bijective. Take now some $ b_{2},b_{3}, \ldots ,b_{k} \in S $, such that $ b_{2} \neq a_{2}, \ b_{3} \neq a_{3}, \ \ldots , \ b_{k} \neq a_{k} $. Then if we take some $ b \in S $, then for every $ a \in S, a \neq b $ we have that the sequences $ (a,a_{2}, \ldots , a_{k}) $ and $ (b,b_{2}, \ldots , b_{k}) $ differ in all of elements, therefore $ x:= f(b,b_{2},b_{3}, \ldots ,b_{k}) \neq f(a,a_{2}, \ldots , a_{k}) = \varphi (a) $, so $ x \neq \varphi (a) $ for every $ a \neq b $, therefore $ x = \varphi (b) $. Therefore $ (b_{2},\ldots ,b_{k}) $ satisfies also that $ f(b,b_{2}, \ldots , b_{k}) = \varphi (b) $. Doing this step one more time, we can reach every sequence $ c_{2}, c_{3}, \ldots , c_{k} $ ( I mean , for arbitrary sequence $ c_{2}, \ldots , c_{k} \in S $, we can find , because of $ S $ has at least $ 3 $ elements, a sequence $ b_{2}, \ldots , b_{k} $, such that $ a_{i} \neq b_{i} \neq c_{i} $ for every $ 2 \leqslant i \leqslant k $). So we get that for every $ (c_{1},c_{2}, \ldots, c_{k}) \in S^{k} $, that $ f(c_{1},c_{2}, \ldots , c_{k}) = \varphi(c_{1}) $. 2) For every $ a_{2},a_{3}, \ldots , a_{k} \in S $, there exist distinct $ \alpha(a_{2},a_{3}, \ldots , a_{k}) $, $ \beta(a_{2},a_{3}, \ldots, a_{k}) \in S $, such that $ f(\alpha,a_{2},a_{3}, \ldots ,a_{k}) = f(\beta,a_{2},a_{3}, \ldots ,a_{k}) $. Then for every such $ a_{2},a_{3}, \ldots , a_{k} \in S $ make an arbitrary choice of such $ \alpha , \beta $, and define $ g: S^{k-1} \rightarrow S $ by $ g(a_{2},a_{3}, \ldots , a_{k}) := f(\alpha,a_{2},a_{3}, \ldots ,a_{k}) = f(\beta,a_{2},a_{3}, \ldots ,a_{k}) $. Then I claim that $ g: S^{k-1} \rightarrow S $ satisfies the conditions of the problem. Indeed, if $ (a_{2},a_{3}, \ldots , a_{k}) , (b_{2},b_{3}, \ldots , b_{k}) \in S^{k-1} $, such that they differ in all of elements, then if $ a',a'' = \alpha,\beta(a_{2}, \ldots, a_{k}) $ and $ b',b''= \alpha,\beta(b_{2}, \ldots, b_{k}) $, then or $ a' \neq b' $ , or $ a' \neq b'' $. Without loss of generality, assume that $ a' \neq b' $. Then $ (a',a_{2},\ldots, a_{k}), (b',b_{2}, \ldots, b_{k}) \in S^{k} $ differ in all of elements, therefore $ g(a_{2},\ldots,a_{k}) = f(a',a_{2},\ldots, a_{k}) \neq f(b',b_{2}, \ldots, b_{k}) = g(b_{2},\ldots, b_{k}) $. Therefore $ g: S^{k-1} \rightarrow S $ satisfies the conditions of the problem, so by induction, without loss of generality, we can assume that $ g(a_{2}, \ldots, a_{k}) = \varphi(a_{2}) $, for some $ \varphi : S \rightarrow S $. Of course then the map $ \varphi $ must be bijective (the argument is similar as before for $ g $ satisfying the conditions of the problem). So we get that for every $ a_{2},a_{3}, \ldots, a_{k} \in S $ that taking $ \alpha,\beta(a_{2},a_{3},\ldots,a_{k}) $ we have that $ f(\alpha,a_{2}, \ldots,a_{k}) = f(\beta,a_{2}, \ldots,a_{k}) = \varphi(a_{2}) $. Now I claim that for every $ (b_{1},b_{2}, \ldots, b_{k}) \in S^{k} $ we have that $ f(b_{1},b_{2}, \ldots, b_{k}) = \varphi(b_{2}) $. Indeed, if it is not so, then assume that there exists $ (b_{1},b_{2}, \ldots, b_{k}) \in S^{k} $, such that $ f(b_{1},b_{2}, \ldots, b_{k}) = c \neq \varphi(b_{2}) $, then take $ b_{2}' \in S $ such that $ \varphi(b_{2}') = c $, and then of course $ b_{2}' \neq b_{2} $. Take now arbitrary $ b_{3}', \ldots, b_{k}' \in S $, such that $ b_{3}' \neq b_{3}, \ldots , b_{k}' \neq b_{k} $. Take also $ \alpha,\beta = \alpha,\beta(b_{2}',b_{3}', \ldots, b_{k}') $. Then if $ b_{1} = \alpha $, take $ b_{1}' = \beta $, otherwise take $ b_{1}'=\alpha $. At we end we have found a sequence $ (b_{1}',b_{2}', \ldots,b_{k}') \in S^{k} $, which differs from the sequence $ (b_{1},b_{2}, \ldots ,b_{k}) $ at each element and $ f(b_{1},b_{2}, \ldots ,b_{k}) = c = \varphi(b_{2}') = f(b_{1}',b_{2}', \ldots, b_{k}') $ and we come to contradiction. I hope it is correct .

Leva1980 wrote: 2) For every $ a_{2},a_{3}, \ldots , a_{k} \in S $, there exist distinct $ \alpha(a_{2},a_{3}, \ldots , a_{k}) $, $ \beta(a_{2},a_{3}, \ldots, a_{k}) \in S $, such that $ f(\alpha,a_{2},a_{3}, \ldots ,a_{k}) = f(\beta,a_{2},a_{3}, \ldots ,a_{k}) $. I prefer the following more direct finish: for fixed $A=(a_2,\ldots,a_k)\in S^{k-1}$ let $\alpha(A),\beta(A)$ be two such indices, and fix some $A_0\in S^{k-1}$. Clearly there exist $A_1,A_2,\ldots,A_{n-1}\in S^{k-1}$ such that no two distinct $A_i,A_j$ share any elements (e.g. take $A_i \equiv A_0 + i \pmod{n}$), so $f(x,A_0),f(\alpha(A_1),A_1),\ldots,f(\alpha(A_{n-1}),A_{n-1})$ are pairwise distinct for any $x\in S$. In particular, $f(x,A_0)$ must be constant; because $A_0$ was arbitrary, $f$ must be independent of its first coordinate $a_1$ (and we can "induct" to finish the problem, or just use the same reasoning for other coordinates). There are certainly other ways to prove this as well. In fact, for fixed $A_0$, we only need $f(\alpha,A_0) = f(\beta,A_0)$ to prove that $f(x,A_0)$ is independent of $x$: suppose for contradiction there exists $j\in S$ with $f(j,A_0) \ne f(\alpha,A_0)$. Then $j\ne \alpha,\beta$, so $f(j+1,A_0+1),f(j+2,A_0+2),\ldots,f(j+n-1,A_0+n-1)$ (coordinates taken mod $n$) must be $n-1$ pairwise distinct numbers in $S$, none equal to $f(\alpha,A_0)=f(\beta,A_0)$ or $f(j,A_0)$, contradicting $|S|=n$. One can also induct on $n\ge3$ for the original problem statement, but the base case $n=3$ still seems to require something like the above argument. (Note that Myth's Lemma 2 similarly follows from an easy induction on $l\ge3$, and Lemma 1, its base case, has a similar flavor to $n=3$ here.)

I think an induction is the easiest way to prove the problem, because once we have decided to use induction the mere induction step motivates and spurs us step after step in a straightforward manner. It can be done in two phases: first when n=3, induction with respect to $k,\, k\geq 1$, and second when $k$ is fixed, induction with respect to $n$. Both induction steps involve a routine technique, the second one is easier, so we will consider only the first one. Let the statement be true for $n=3,\,k,\, k \geq 1$, we will prove it for $n=3,\, k+1$. Assuming the requirements are fulfilled for $n=3,\,k+1$ let us set up three functions $f_{\ell}(\mathbf{x})=f(x_1+\ell ,\mathbf{x}),\, \ell=0,1,2$ , where $\mathbf{x}=(x_1,x_2,\ldots,x_k) $ and $x_1+\ell$ means $x_1+\ell \mod (3)$. Then applying induction on $f_{\ell}$ we conclude that $f_{\ell}(\mathbf{x})= f_{\ell}(x_{i_{\ell}}),\, \ell=0,1,2 $. It is easy to see that $f_{\ell}(x_{i_{\ell}})$ takes exactly three values and is a bijection. Obviously $i_0=i_1=i_2$ because if for example $i_0\neq i_1$ we can take two values $x_{i_0}^{(0)}, x_{i_1}^{(0)}$ respectively of $x_{i_0},x_{i_1}$ such that $f_0(x_{i_0}^{(0)})=f_1(x_{i_1}^{(0)})$. But if we take two appropriate values of $(x_1, x_2,\ldots, x_{k+1})$ , for which $x_1=x_2, x_1=x_2+1$ resp., non intersecting at any coordinate, and coinciding with $x_{i_0}^{(0)}$ and $x_{i_1}^{(0)}$ respectively at coordinates $i_0$ and $i_1$ we will get a contradiction. The last sentence contains the difference between $n=2$ and $n=3$. When $n=2$ it can not be carried out, because the values of variable $x_1$ are not enough to exploit the above argument (only 0 and 1). If $i_0=i_1=i_2>1$ a similar argument as above yields $f_0\equiv f_1 \equiv f_2$ . Let assume now that $i_0=i_1=i_2=1$ , i.e. $f_{\ell}(\mathbf{x})=f_{\ell}(x_1)$. Again if $f_0\equiv f_1 \equiv f_2$ we are done. Suppose it is not the case and e.g. $f_0(x)=f_1(y)$ for some $ x\neq y$ (remember that $f_{\ell}$ is a bijection). Then $x+0=y+1$ , because otherwise we can construct two pointwise different values of argument of $f$ with equal images. One can consider that $x=y+1$ for those values of $x, y$ for which $f_0(x)=f_1(y), x\neq y$ and if it is true for at least one pair $x,y$ then it is true for all pairs $(y+1,y)$ i.e. $f_0(y+1)=f_1(y),\, y=0,1,2$. This means $f(x_1,x_1,\ldots, x_{k+1})=f(x_1,x_1-1,\ldots,x_{k+1})$. The same arguments hold with respect to $f_0,f_2$ and $f_1,f_2$ , so we can conclude that there are only two alternatives: a) $f_0\equiv f_1 \equiv f_2$. In this case $f(x_1,x_2,\ldots,x_{k+1})=f_0(x_2)$ b) $f_0(y+2)=f_1(y+1)=f_2(y),\,y=0,1,2 \,\Rightarrow \,$ $f(x_1,x_1,x_3, \ldots, x_{k+1})=f(x_1,x_1-1,x_3, \ldots, x_{k+1}) = f(x_1,x_1-2,x_3,\ldots, x_{k+1})$, $\forall x_1,x_3,\ldots,x_{k+1}$ Therefore, in this case, $f(x_1,x_2,\ldots,x_{k+1})=\psi(x_1)$.