Fun Functions!

[Kalkewl8ter]

A polynomial f(x)=y with integer coefficients passes through points (3, 9) and (8, k). Find the largest possible value of k if k<9.

[kedaman]

humm, i don't think there is a largest possible value

[bugzpodder]

if k<9 there is probably a largest value, and its probably 4

[kedaman]

yeah, i think i misread it :S

[bugzpodder]

i am just speculating about (8,4) what do you think kedaman

[SilverSprite]

(k-9)/(8-3) = (k-9)/5

To be integer k is 4. Hehe , assume its linear, I miscalculated on the contest.

[Kalkewl8ter]

Don't listen to Sprite and assume it's linear; there's actually a way to do the question and get 4.

[kedaman]

there's probably something terribly wrong with my proof trough induction, that theres no integer constants a0 to an that gives a k between 9 and 4, but i could be wrong as well

p(n):
9 = a0 + a1*3^1 + .. + an*3^n
4 < a0 + a1*8^1 + .. + an*8^n
9 > a0 + a1*8^1 + .. + an*8^n

prove p(1) is false:
9 = a0 + a1*3
4 < a0 + a1*8
9 > a0 + a1*8

4 < 9-a1*3 + a1*8
9 > 9-a1*3 + a1*8

4-9 < a1*5
9-9 > a1*5

-1 < a1
0 > a1
there's no integer a1 between 0 and -1.

prove p(n)=>p(n+1) is false:

9 = a0*3^0 + a1*3^1 + .. + an*3^n + a(n+1)*3^(n+1)
4 < a0*8^0 + a1*8^1 + .. + an*8^n + a(n+1)*8^(n+1)
9 > a0*8^0 + a1*8^1 + .. + an*8^n + a(n+1)*8^(n+1)

9- a(n+1)*3^(n+1) = a0*3^0 + a1*3^1 + .. + an*3^n
4- a(n+1)*8^(n+1) < a0*8^0 + a1*8^1 + .. + an*8^n
9- a(n+1)*8^(n+1) > a0*8^0 + a1*8^1 + .. + an*8^n

- a(n+1)*3^(n+1) = - 9 + a0*3^0 + a1*3^1 + .. + an*3^n
- a(n+1) = (- 9 + a0*3^0 + a1*3^1 + .. + an*3^n )/3^(n+1)

4 + (- 9 + a0*3^0 + a1*3^1 + .. + an*3^n )(8/3)^(n+1) < a0*8^0 + a1*8^1 + .. + an*8^n
9 + (- 9 + a0*3^0 + a1*3^1 + .. + an*3^n )(8/3)^(n+1) > a0*8^0 + a1*8^1 + .. + an*8^n

and the assumption p(n) could be written as

4 < 4 + (- 9 + a0*3^0 + a1*3^1 + .. + an*3^n )(8/3)^(n+1) < a0*8^0 + a1*8^1 + .. + an*8^n
9 > 9 + (- 9 + a0*3^0 + a1*3^1 + .. + an*3^n )(8/3)^(n+1) > a0*8^0 + a1*8^1 + .. + an*8^n

0<(- 9 + a0*3^0 + a1*3^1 + .. + an*3^n )(8/3)^(n+1)<0, obviously not true

[bugzpodder]

ok let a general function with integer coeeficients:

f(x)=a0x^n+a1x^(n-1)+...+an
f(3)=a0*3^n+a1*3^(n-1)+...+an
f(8)=a0*8^n+a1*3^(n-1)+...+an

notice that 8^k-3^k is divisible by 5 (hint mod 5) so f(8)-f(3) is divisible by 5. go from there

[Kalkewl8ter]

Induction...interesting...but why would you try to prove that it can't be less than 4 or greater than 9, unless you were fairly sure that it would work already, which, on a 30-minute math contest you wouldn't be?

[kedaman]

it wouldn't have to be 4, its just that 4 and 9 gave these
4-9 < a1*5
9-9 > a1*5

[kedaman]

Originally posted by bugzpodder
notice that 8^k-3^k is divisible by 5 (hint mod 5) so f(8)-f(3) is divisible by 5. go from there [/B]

aah, took me a while to get what you were on, if the terms in the polynom are divisible with 5 then it wouldn't be possible to have k less than 5 from 9