Maths Olympiad Prep

Library / /7 of 13

Algebra Difficulty 6.3 National olympiad Find the answer

Find all the functions f:ZZf: \mathbb{Z} \rightarrow \mathbb{Z} such that f(4x+3y)=f(3x+y)+f(x+2y)f(4x+3y)=f(3x+y)+f(x+2y) for all integers xx and yy.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Putting x=0x=0 in the original equation f(4x+3y)=f(3x+y)+f(x+2y)f(4x+3y)=f(3x+y)+f(x+2y) we get f(3y)=f(y)+f(2y)f(3y)=f(y)+f(2y) Next, for y=2xy=-2x we have f(2x)=f(x)+f(3x)=f(x)+f(x)+f(2x)f(-2x)=f(x)+f(-3x)=f(x)+f(-x)+f(-2x) (in view of the previous equation). It follows that f(x)=f(x)f(-x)=-f(x) Now, let x=2zv,y=3vzx=2z-v, y=3v-z in the original equation. Then f(5z+5v)=f(5z)+f(5v)f(5z+5v)=f(5z)+f(5v) for all z,vZz, v \in \mathbb{Z}. It follows immediately that f(5t)=tf(5)f(5t)=tf(5) for tZt \in \mathbb{Z}, or f(x)=ax5f(x)=\frac{ax}{5} for any xx divisible by 5, where f(5)=af(5)=a. Further, we claim that f(x)=bxf(x)=bx where b=f(1)b=f(1), for all xx not divisible by 5. In view of the previous equation, it suffices to prove the claim for x>0x>0. We use induction in kk where x=5k+r,kZ,0<r<5x=5k+r, k \in \mathbb{Z}, 0<r<5. For x=1x=1 the claim is obvious. Putting x=1,y=1x=1, y=-1 in the original equation gives f(1)=f(2)+f(1)f(1)=f(2)+f(-1) whence f(2)=f(1)f(1)=2f(1)=2bf(2)=f(1)-f(-1)=2f(1)=2b. Then f(3)=f(1)+f(2)=3bf(3)=f(1)+f(2)=3b by the previous equation. Finally, with x=1,y=0x=1, y=0 we get f(4)=f(3)+f(1)=3b+b=4bf(4)=f(3)+f(1)=3b+b=4b. Thus the induction base is verified. Now suppose the claim is true for x<5kx<5k. We have f(5k+1)=f(4(2k2)+3(3k))=f(3(2k2)+(3k))+f((2k2)+2(3k))=f(5k3)+f(4)=(5k3)b+4b=(5k+1)b;f(5k+2)=f(4(2k1)+3(2k))=f(3(2k1)+(2k))+f((2k1)+2(2k))=f(5k1)+f(3)=(5k1)b+3b=(5k+2)b;f(5k+3)=f(42k+3(1k))=f(32k+(1k))+f(2k+2(1k))=f(5k+1)+f(2)=(5k+1)b+2b=(5k+3)b;f(5k+4)=f(4(2k+1)+3(k))=f(3(2k+1)+(k))+f((2k+1)+2(k))=f(5k+3)+f(1)=(5k+3)b+b=(5k+4)bf(5k+1)=f(4(2k-2)+3(3-k))=f(3(2k-2)+(3-k))+f((2k-2)+2(3-k))=f(5k-3)+f(4)=(5k-3)b+4b=(5k+1)b; f(5k+2)=f(4(2k-1)+3(2-k))=f(3(2k-1)+(2-k))+f((2k-1)+2(2-k))=f(5k-1)+f(3)=(5k-1)b+3b=(5k+2)b; f(5k+3)=f(4\cdot 2k+3(1-k))=f(3\cdot 2k+(1-k))+f(2k+2(1-k))=f(5k+1)+f(2)=(5k+1)b+2b=(5k+3)b; f(5k+4)=f(4(2k+1)+3(-k))=f(3(2k+1)+(-k))+f((2k+1)+2(-k))=f(5k+3)+f(1)=(5k+3)b+b=(5k+4)b. Thus the claim is proved. It remains to check that the function f(x)=ax5f(x)=\frac{ax}{5} for xx divisible by 5, f(x)=bxf(x)=bx for xx not divisible by 5 satisfies the original equation. It is sufficient to note that 5 either divides all the numbers 4x+3y,3x+y,x+2y4x+3y, 3x+y, x+2y or does not divide any of these numbers.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.