Home > Olympiad > Balkan Mathematical Olympiad 2012 Problem 4

Balkan Mathematical Olympiad 2012 Problem 4


Let {\mathbb{Z}^+} be the set of positive integers. Find all functions {f:\mathbb{Z}^+ \rightarrow\mathbb{Z}^+} such that the following conditions both hold:

(i) {f(n!)=f(n)!} for every positive integer {n},

(ii) {m-n} divides {f(m)-f(n)} whenever {m} and {n} are different positive integers.

Balkan Mathematical Olympiad 2012 Problem 4

Solution: First we have f(k)=f(k)! for k=1,2, which means that f(1),f(2) \in \{1,2\}. We have a few cases:

Case 1: f(1)=f(2)=1. Then we know that n!-1 | f(n!)-1 and n!-2 | f(n!)-1. This means that f(n!) is odd for every n and therefore f(n)=1 for every n \in \Bbb{Z}^+,

Case 2: f(1)=f(2)=2.  First note that 2 | f(3)-2 so f(3) is even. Then 20 | f(6)-2 which means that necessarily f(6)=2, and furthermore f(3)=2. This means that f(n!)-2 \equiv 2 modulo n!-1,\ n!-2,\ n!-3, and this means that f(n)! is never divisible by 3. Since f(n) is also even it follows that f(n)=2 on \Bbb{Z}_+.

Case 3: f(1)=2,\ f(2)=1. It follows that f(6) has last digit 7 and cannot be a factorial.

Case 4: f(1)=1,\ f(2)=2. For n \geq 3 we have n!-n | f(n)!-f(n) and since the function n \mapsto n!-n is strictly increasing for n \geq 3 we find that f(n) \geq n, and furthermore n |f(n)!, which allows us to deduce from  n!-n | f(n)!-f(n) that n | f(n).

So f(n)=kn with k \in \Bbb{Z}^+. Then k\cdot n!=(kn)!,\ n \geq 3, which can hold only if k=1. In this case we have f(n)=n,\ \forall n \in \Bbb{Z}^+.

Advertisements
Categories: Olympiad Tags:
  1. April 30, 2012 at 9:21 am

    where is the problem?

    • April 30, 2012 at 10:45 am

      Do you mean where is the solution? I haven’t posted it yet.

  2. May 2, 2012 at 1:07 pm

    I didn’t mean that.I’m very sorry Beni because I didn’t read the post carefully.The problem is to find all function f that satisfy the two condition isn’t it?

    • May 2, 2012 at 1:29 pm

      Yes, that is the problem 🙂

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: