Wednesday, July 20, 2011

IMO 2011: a solution to Q5

Your time is over. You only had 4 hours 30 minutes for the 3 problems of the second day. The TRF problem was this one:
Q5: Let \(f\) be a function from the set of integers to the set of positive integers. Suppose that, for any two integers \(m\) and \(n\), the difference \(f(m)-f(n)\) is divisible by \(f(m-n)\). Prove that, for all integers \(m\) and \(n\) with \(f(m)\leq f(n)\), the number \(f(n)\) is divisible by \(f(m)\).

Spoilers: solution

Let's just look at the last sentence what we should prove. The values of \(f(m)\) are positive (i.e. also nonzero: see the first sentence in the formulation of the problem!) integers. We should prove that for any two allowed values of \(f(m),f(n)\), the greater one among the two is a multiple of the smaller one.

Sequence of multiples of their predecessors

So we are asked to prove that if you list all possible values of \(f(m)\) in an ascending order, which will produce a list of positive integers, each new element of the sequence will be a multiple of the previous one. For example, it's conceivable that the allowed values of \(f(m)\) are \(0!,1!,2!,3!,\dots\) and so on.

Setting \(n=0\)

If you set \(n=0\) in the condition, you will learn that \(f(m)-f(0)\) is a multiple of \(f(m)\). It follows that \(f(0)\) itself is a multiple of \(f(m)\). Note that this is already counter-intuitive for most people who were "guessing": for the typical nontrivial functions \(f\), the value \(f(0)\) is actually the largest one, and it is a multiple of any other allowed value of \(f\). "Guessing" people would typically try to set \(f(0)=1\) - or the smallest allowed value - and then they would be led to a wrong belief that there are almost no functions that satisfy the conditions.

Function is even

Moreover, the main condition of the question may be used to see that \(f(0)-f(n)\) is a multiple of \(f(0-n)\) i.e. of \(f(-n)\) which means that \(f(n)\) itself is a multiple of \(f(-n)\) - it is because \(f(0)\) already is. This "being a multiple" relationship holds symmetrically for \(\pm n\) interchanged which implies \(\forall n:\,f(n)=f(-n)\). Recall that the function is positive (nonzero).

A single triple: completing the proof

Now, take 3 values of the argument, namely \(\{m+n,m,n\}\). The main assumption of the problem guarantees that \(f(m+n)-f(m)\) is a multiple of \(f(n)\). Similarly, \(f(m+n)-f(n)\) is a multiple of \(f(m)\). And \(f(m)-f(-n)=f(m)-f(n)\) is a multiple of \(f(m+n)\).

It means that the three values of the function,
\(\{A,B,C\} = \{f(m+n),f(m),f(n)\} \)
satisfy the condition that \(A-B\) is a multiple of \(C\) and all permutations of this statement. If you assume that \(A,B,C\) are three different numbers and you order \(A,B,C\) so that \(A,B\) are the smallest two while \(C\) is the largest one, it is clear that \(A-B\) cannot be a multiple of \(C\) because its absolute value is too small yet nonzero.

It follows that \(A,B,C\) must actually be at most two different numbers. For example, it must be true that \(f(m)=f(n)\) - or any other two entries in the list are equal which would lead to analogous conclusions. If that's true, the main condition still says that \(f(m+n)-f(n)\) is a multiple of \(f(m)=f(n)\) which means that \(f(m+n)\) itself is a multiple of \(f(n)\). We could have chosen \(m+n,n\) arbitrarily so among any pair of possible values of \(f\), the larger value of \(f\) must be a multiple of the smaller one which is what we wanted to prove.

Appendix: Non-constant functions are possible

Just to be sure, it is not true that only a constant function \(f(m)=f(n)\) satisfies the assumption of the problem. A counterexample is a function
\[ f(2k)=PQ,\quad f(2k+1) = Q,\quad \forall k\in {\mathbb Z}\] where \(P,Q\) are positive integers. Then \(f(m)-f(n)\) is a multiple of \(f(m-n)\). It's trivial if both \(m,n\) are even or both are odd because the difference is zero - which is a multiple of anything. If one of them is even and the other is odd, then \(f(m)-f(n) = \pm (P-1)Q\) which is still a multiple of \(Q\).

In fact, it is not hard to create more complicated functions that have many different values; the range of \(f\) can be a set with an arbitrary finite number of elements. For example, you may choose
f(2k+1)&=R,\quad\quad \forall k\in{\mathbb Z}
\end{align}\] For \(m-n=0\) modulo 4, \(f(m)-f(n)\) is zero which is a trivial multiple of \(PQR\). For \(m-n=2\) modulo 4, \(f(m)-f(n)\) is \(\pm(P-1)QR\) which is a multiple of \(f(m-n)=QR\). For \(m-n=1\) modulo 2, i.e. 1 or 3 modulo 4, \(f(m)-f(n)\) is still a multiple of \(f(m-n)=R\).

This template is easily generalized to produce functions whose periodicity is \(2^p\): you just need to know how the alphabet continues after \(P,Q,R\) haha.

The relevant periodicity doesn't have to be a power of two. I promised you that a periodicity \(5\) could be relevant. Just define \(f\) to be \(PQ\) for all multiples of \(5\) and \(Q\) otherwise. It will still work because it is only "hard" for a difference to be a multiple of \(f(m-n)\) if \(f(m-n)=PQ\) which however means that \(m=n\) modulo 5 and then \(f(m)-f(n)=0\).

There are many other generalizations. I am not sure whether I know how to "classify" or "generate" all functions that satisfy the assumption. It seems likely to me that functions that satisfy the condition have to be periodic. One may probably choose a list of "special periodicities" \(n_1,n_2,\dots n_s\) and for each periodicity,
\[ f(m) = \prod_{i=1}^s Q_i^{n_i|m} \] where the exponent equals \(1\) or \(0\) if the condition "\(m\) is a multiple of \(n_i\)" is satisfied or not, respectively. I haven't checked too carefully that all such functions work for any choice of \(n_i,Q_i\) - update: no, they don't, but everything could be OK whenever \(\forall i: n_i| n_{i+1} \) - and I haven't proved that there are no other functions. But it's a likely hint that there is indeed a very large and diverse class of functions that satisfy the condition.

1 comment:

  1. Solution might be very easier if one consider:

    f(m+n)-f(m)=k*f(n) with k=integer
    f(m+n)-f(n)=l*f(m) with l=integer

    Substract these equations and obtain:


    Since f(n)>=f(m) and both f(n) and f(m) are positive integers (1-l)/(1-k) must be greater or equal 1 and integer.
    Therefore we have f(m)|f(n).