Problem B5
Find all continuously differentiable functions f : R → R such that for every
rational number q ,
the number f(q) is rational and has the same denominator as q . (The denominator
of a rational
number q is the unique positive integer b such that q = a/b for some integer a
with gcd (a, b) = 1.
Note: gcd means greatest common divisor .)
Solution : There is an integer c such that either f(x) = c + x for all x
or f(x) = c - x for all x.
Let r be any rational number and 
in lowest
terms . By hypothesis, for each integer n = 2,
3,... , there are integers 
and
such that
(For 
is obviously in
lowest terms .) It follows that
But this means that f'(r) is an integer for each rational
number r. Since f'(x) is continuous, it
follows that f'(r) is a constant, and hence f'(x) is constant for all real x .
Thus, f(x) is a linear
function: f(x) = c + bx. By hypothesis, f(0) must be an integer, and
must be 
,
where a is
relatively prime to n. Hence c is an integer, and
is in lowest terms. That means b is
relatively
prime to n for every positive integer n. That is possible only if b = ±1.
Problem B6
Let n and k be positive integers. Say that a permutation
of 
is
k-limited if 
for all i. Prove that the number of k-limited permutations of
is odd if and only if n = 0
or n = 1 (mod 2k + 1).
Solution: Let N(k, n) be the number of k-limited permutations of
. We break the
proof into a series of cases.
Case 1: n ≤ k + 1. In this case, the full set
of permutations of
is k-limited. The
number of such permutations is therefore n!, which is odd if n = 1 and even
otherwise.
Case 2: k + 2 ≤ n ≤ 2k. In this case positions k and k + 1 can be mapped to any
element
of without violating the condition of
k-limitedness. Let
be the permutation that
inter changes k and k + 1 and leaves all other elements fixed. Then we can pair
up the k-limited
permutations as follows: 
. This pairing
shows that the number of such permutations is
even.
Case 3: n = 2k+1. For each permutation of
, consider the transpose 
,
defined
by
It is obvious that is
k-limited if
is and that
.
Hence if we match the k-limited
permutation with
, we will have a number of pairs, together
with a number of symmetric
permutations characterized by
. The parity of the complete set of k-limited
permutations
will therefore be the same as the parity of the number of symmetric k-limited
permutations.
Observe that position k + 1 must be left fixed by any symmetric permutation.
Now for each subset 
consider a k-limited
symmetric permu-
tation that maps D to
a subset 
of {k + 1, ... , 2k + 1 }, that is, 
,
j = 1, 2, ... , r, and maps all the remaining elements of {1, 2, ... , k} to
elements of {1, 2, ... , k }. If
the ordered sets D and D' are fixed and one such permutation exists, we can find
all such k-limited
symmetric permutations by taking an arbitrary permutation
of {1, 2, ... , k} \
D and defining
, j = 1, 2, ... , r, and
) for 
.
The number of such permu-
tations is therefore (k - r)!, which is an even number if 0 ≤ r ≤ k - 2. Now if
r = k - 1, there is
one and only one k-limited symmetric permutation
that maps a set D
consisting of r elements
in {1, 2, ... , k} to a subset D' of { k + 2, ... , 2k }, namely
Hence the total number of k-limited symmetric permutations
of 
is odd.
We have now shown that for 1 ≤ n ≤ 2k + 1, the number of k-limited permutations
is odd if
n ≡ 1 or n ≡ 2k + 1 ≡ 0 mod 2k + 1 and even otherwise.
Case 4: n > 2k+1. We complete the proof by showing that N(k, n+2k+1) has the
same parity as
N(k, n). First, we count the k-limited permutations of {1, 2, ... , n, n+1, ...
, n+2k+1} that leave
the subset {n+1, ... , n+2k+1} invariant. Such a permutation
can obviously be identified with
a pair 
, where
is a k-limited
permutation of {1, 2, ... , n} and
a k-limited permutation
of { n + 1, ... , n + 2k + 1}. The number of such permutations is therefore N(k,
n)N(k, 2k + 1).
Since N(k, 2k + 1) is odd, this number has the same parity as N(k, n). Thus, it
remains only
to prove that the number of k-limited permutations of {1, 2, ... , n + 2k + 1}
that do not leave
{n + 1, ... , n + 2k + 1} invariant is even.
Now we observe that
is k-limited and leaves a given set D invariant if and only if its inverse
has these two properties . Thus, we can match
a k-limited permutation
that does not leave
{n + 1, ... , n + 2k + 1} invariant with its inverse
, and that gives us a certain number of
pairs,
plus a certain number of permutations that are matched with themselves, namely
those of order
1 or 2, which consist of products of disjoint 2-cycles (trivially, in the case
of the unique element
of order 1, which is the identity permutation). What we need to show, then, is
that there is an
even number of k-limited permutations of order 1 or 2 that do not leave {n
+ 1, ... , n + 2k + 1}
invariant. We note in passing that order 1 does not actually occur here, since
only the identity has
that order, and it leaves every set invariant.
Suppose is such a
permutation. The fact that the set {n + 1, ... , n + 2k + 1} is not left
invariant means that at least one of its elements p maps to some p' with p' ≤ n.
Since is of
order 2, it follows that p' maps to p. Since
is k-limited, we must
have n + 1 ≤ p ≤ n + k. Let
D be the subset of {n + 1, ... , n + k} that
maps into {1, ... , n
}, say 
maps to
. By hypothesis, r ≥ 1.
Further, let 
be the subset of {n + 1, ... ,
n + k} that
maps into {n + k +
1, ... , n + 2k + 1}, say
. By hypothesis s ≤
k - 1. Since
is a product
of disjoint 2-cycles, the only elements among {n + k + 1, ... , n + 2k + 1} that
map outside this set
are those in the set E'. Thus, at most k - 1 of the k + 1 elements {n + k
+ 1, ... , n + 2k + 1} are
mapped outside of this set.
It follows that there are k + 1 - s ≥ 2 elements in this last set that
maps to points within
the set. These can be permuted in (k + 1 - s)! ways, and this is an even number.
In any finite
group, the number of elements of order 1 or 2 has the same parity as the group
itself , since all other
elements can be paired with their inverses. For each choice of the values of
(p) with p ≤ n+k, as
above, there are k+1-s elements in { n+k+1, ... , n+2k+1} that are not of the
form (p) for any
p ≤ n + k. The permutation
can permute these
elements in any way and still remain k-limited.
Since the number of permutations of order 1 or 2 of those k + 1 - s elements has
the same parity
as (k + 1 - s)!. That means that it is even. Hence, for each fixed choice of
(p), p ≤ n + k, the
number of possible choices of
(q), for q > n + k
under which
will be a k-limited
permutation of
order 2 not leaving {n + 1, ... , n + 2k + 1} invariant is even.
But then the total number of k-limited permutations of order 2 that do not leave
{ n+1, ... , n+
2k + 1} invariant is a sum of even numbers, and hence even.
The result is now proved.
