Let $n$ and $k$ be positive integers. A function $f : \{1, 2, 3, 4, \dots , kn - 1, kn\} \to \{1, \cdots , 5\}$ is good if $f(j + k) - f(j)$ is multiple of $k$ for every $j = 1, 2. \cdots , kn - k$. (a) Prove that, if $k = 2$, then the number of good functions is a perfect square for every positive integer $n$. (b) Prove that, if $k = 3$, then the number of good functions is a perfect cube for every positive integer $n$.
Problem
Source: Rio de Janeiro Mathematical Olympiad 2018, Level 4, #3
Tags: function, combinatorics
Math5000
17.11.2019 22:50
Generalization My solution: a) Let be $ k = 2 $. We will have to $ f (j + 2) -f (j) $ is a multiple of 2 for $ j \in \{1, ..., kn - k \} $. Thus, module $ 2 $, we have $ f (j + 2) \equiv f (j) $. But at the same time, we will also have $ f (j) \equiv f (j-2) $. That way we will have $ f (2n) \equiv f (2 (n-1)) \equiv f (2 (n-2)) \equiv ... \equiv f (2) $ $ f (2n-1) \equiv f (2n-3) \equiv ... \equiv f (1) $ So just choose one parity for $ f (2x) $ and one for $ f (2x-1) $. If $ f (2x) $ is even then $ f (2x) \in \{2,4,4\}.$ In that case we will have $ 2 ^ n $ possibilities. (which is the same value when $ f (2x-1) $ is even, since the number of pairs from $ 1 $ to $ 2n $ is the same as odd) If $ f (2x) $ is odd, then $ f (2x) \in \{1, 3, 5 \} $. In that case we will have $ 3 ^ n $ possibilities. (which is the same value for when $ f (2x-1) $ is odd). To calculate the number of functions, simply calculate the number of cases where $ f (2x) $ is even (among which $ f (2x-1) $ can be even or odd) and add up to the number of cases in that $ f (2x) $ is odd. Thus, the total number of functions for $ k = 2 $ is $ 2 ^ n \cdot (3 ^ n + 2 ^ n) + 3 ^ n \cdot (2 ^ n + 3 ^ n) = (3 ^ n + 2 ^ n) ^ 2 $, in fact a perfect square. b) The reasoning is pretty much the same. The only difference is that instead of considering the cases where $ f (2x) $ and $ f (2x-1) $ are odd or even, we will consider cases where $ f (3x) $, $ f (3x- 1) $ and $ f (3x-2) $ are congruent to $ 0 $, $ 1 $, or $ 2 $ module three. So, using the fact that there are $ n $ numbers in the domain for every possible remainder by three, then just separate the mismatch set by leftovers: $ \{1, 2, 3, 4, 5 \} = \{1, 4 \} \cup \{2, 5 \} \cup \{3 \} $ so that to calculate the number of functions we would have to choose one module for $ f (3x) $, another for $ f (3x-1) $ and one for $ f (3x-2) $, where that each module can correspond to $ 1 ^ n $, $ 2 ^ n $ or $ 2 ^ n $ possibilities. Thus, the total number of functions would be $ (1 ^ n + 2 ^ n + 2 ^ n) (1 ^ n + 2 ^ n + 2 ^ n) (1 ^ n + 2 ^ n + 2 ^ n) $ $ = (1 ^ n + 2 ^ {n + 1}) ^ 3 $ in fact a perfect cube.