Given a positive integer , determine all functions from the first positive integers to the positive integers, satisfying the following two conditions:
Solution
If is odd, the required functions are the constant function along with the functions ,
notice that if . If is even, is to be removed from the list, by (2). All these functions plainly satisfy the conditions in the statement.
Labelling the positive integers in the list increasingly, , the problem amounts to determining all lists of positive integers such that and for no subset of the first positive integers. Notice that , by , and , by . With reference again to , notice further that if , then the other are all 1, and if , then so are the other . If is even, rules out the latter case.
Leaving aside the trivial cases and , let . To rule out , assume, if possible, this is the case, and notice that
are pairwise distinct integers, so at least two are congruent modulo . Since , the first two cannot be congruent modulo , and rules out the remaining cases.