That's it?

Algebra Level 4

Given a function f f for which f ( x ) = f ( 398 x ) = f ( 2158 x ) = f ( 3214 x ) f(x) = f(398 - x) = f(2158 - x) = f(3214 - x) holds for all real x x , what is the largest number of different values that can appear in the list f ( 0 ) , f ( 1 ) , f ( 2 ) , , f ( 999 ) ? f(0),f(1),f(2),\ldots,f(999)?


The answer is 177.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Siddharth Bhatt
Jun 6, 2015

f ( 2158 x ) = f ( x ) = f ( 3214 ( 2158 x ) ) = f ( 1056 + x ) f ( 398 x ) = f ( x ) = f ( 2158 ( 398 x ) ) = f ( 1760 + x ) \begin{aligned}f(2158 - x) = f(x) &= f(3214 - (2158 - x)) &= f(1056 + x)\\ f(398 - x) = f(x) &= f(2158 - (398 - x)) &= f(1760 + x)\end{aligned} Since g c d ( 1056 , 1760 ) = 352 \mathrm{gcd}(1056, 1760) = 352 we can conclude that (by the Euclidean algorithm)

f ( x ) = f ( 352 + x ) f(x) = f(352 + x) So we need only to consider one period f ( 0 ) , f ( 1 ) , . . . f ( 351 ) f(0), f(1), ... f(351) , which can have at most 352 352 distinct values which determine the value of f ( x ) f(x) at all other integers.

But we also know that f ( x ) = f ( 46 x ) = f ( 398 x ) f(x) = f(46 - x) = f(398 - x) , so the values x = 24 , 25 , . . . 46 x = 24, 25, ... 46 and x = 200 , 201 , . . . 351 x = 200, 201, ... 351 are repeated. This gives a total of

352 ( 46 24 + 1 ) ( 351 200 + 1 ) = 177 352 - (46 - 24 + 1) - (351 - 200 + 1) = \boxed{ 177 } distinct values.

can you give some clarity in the last part ??? 200 to 351 ... why is that repeated ??

S Pedro - 4 years, 5 months ago

Why f(x) = f(46-x)?

Vibhav Aggarwal - 3 years, 10 months ago
Maxence Seymat
Jan 8, 2020

I'll try to give a somewhat general solution here. Let a < b < c a<b<c be distinct positive integers and f f be a function defined on integers such that for every integer x x , f ( x ) = f ( a x ) = f ( b x ) = f ( c x ) f(x)=f(a-x)=f(b-x)=f(c-x) . We would like to know the cardinal of the image of f f .

For every integer x x , f ( x ) = f ( b x ) = f ( a b + x ) f(x)=f(b-x)=f(a-b+x) and likewise f ( x ) = f ( b c + x ) = f ( c a + x ) f(x)=f(b-c+x)=f(c-a+x) . Therefore, we can add or substract a b , b c , c a a-b,b-c,c-a to x x without changing its image through f f .

Let d = g c d ( a b , b c , c a ) d=\mathrm{gcd}(a-b,b-c,c-a) and e = a m o d d = b m o d d = c m o d d e=a\bmod d=b\bmod d=c\bmod d . For every relative integer k k , it follows that f ( x ) = f ( k d + x ) = f ( e + k d x ) f(x)=f(kd+x)=f(e+kd-x) and f f is periodic. Let f 1 { f ( x ) } f^{-1}\{f(x)\} the set of all inverse images of f ( x ) f(x) . f 1 { f ( x ) } f^{-1}\{f(x)\} contains therefore x , e x , d + x , e + d x , x,e-x,d+x,e+d-x,\dots

Assuming the cardinal of the image set of f f is maximal, and e d e\leq d for x = ( e + 1 ) / 2 , , ( e + d ) / 2 x=\left\lfloor(e+1)/2\right\rfloor,\dots,\left\lfloor(e+d)/2\right\rfloor we have distinct (disjoint) f 1 { f ( x ) } f^{-1}\{f(x)\} (look at x , e x , d + x , e + d x x,e-x,d+x,e+d-x , other values won't interfere). Therefore, in this case, the total number of (disjoint) sets f 1 { f ( x ) } f^{-1}\{f(x)\} is ( e + d ) / 2 ( e + 1 ) / 2 + 1 \boxed{\left\lfloor(e+d)/2\right\rfloor-\left\lfloor(e+1)/2\right\rfloor+1} .

Plugging in a = 398 , b = 2158 , c = 3214 a=398,b=2158,c=3214 yields d = 352 , e = 46 d=352,e=46 and therefore there are 177 \boxed{177} different values for f ( x ) f(x) with x = 0 , , 999 x=0,\dots,999 ( 1000 d 1000\geq d ).

Not easy to write down formally though.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...