Question

\[\text{ The function } f(n) \text{ is defined for all positive integers } \\ n \text{ and takes on non-negative integral values } \\ \text{ Also, for all } m, n \\ f(m+n)-f(m)-f(n)=0 \text{ or } 1 \\ f(2)=0, f(3)>0, \text{ and } f(9999)=3333. \\ \text{ Determine } f(1982).\]

Answer 1

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwip3YzIuqLJAhWKlh4KHUR3AcAQFggdMAA&url=http%3A%2F%2Fdb.math.ust.hk%2Fnotes_download%2Felementary%2Falgebra%2Fae_A9.pdf&usg=AFQjCNHv-dnZdBdd7dU00Pozi526wMFH6g

got this question from here

Answer 2

under harder problems number 8
last page

Answer 3

@AlexandervonHumboldt2 can you please tell me what integral value means?

Answer 4

if you know

Answer 5

sorry @freckles , never heard of such term.

Answer 6

its k

Answer 7

sounds like it is just an integer

Answer 8

I guess I will assume it is an integer until I run into problems :p

Answer 9

hmmm... well I know since f(2)=0
we have
\[f(2-n)+f(n)=0 \text{ or } -1 \]

Answer 10

and if I used f(2)=0 again...
like replace n with 2 I get
\[f(2-2)+f(2)=0 \text{ or } -1 \\ f(0)+f(2)=0 \text{ or } -1 \\ \text{ and this means } f(0)+0=0 \text{ or } -1 \text{ so we have} f(0)=0 \text{ or } -1 \]

Answer 11

shuldn't it be 0 or +1?

Answer 12

well I had multiplied both sides by -1 earlier

Answer 13

I didn't show that but I could show you what I did

Answer 14

oh okay

Answer 15

\[f(m+n)-f(m)-f(n)=0 \text{ or } 1 \\ \text{ replace } m+n=2 \text{ and so } m=2-n \\ f(2)-f(2-n)-f(n)=0 \text{ or } 1 \\ -f(2-n)-f(n)=0 \text{ or } 1 \]
and then I multiplied both sides by -1

Answer 16

getting that one equation I had above

Answer 17

f(1) will be 0

Answer 18

I got 0 or -1/2 for f(1)

Answer 19

\[f(2-n)+f(n) =0 \text{or } -1 \\ \text{ replace } n \text{ with } 1 \\ \\ f(1)+f(1)=0 \text{ or } -1 \\ f(1)=0 \text{ or } \frac{-1}{2} \\ \]

Answer 20

but it says that the function is defined for all positive integers n and takes NON NEGATIVE values so f(1) can't be -1/2

Answer 21

oh I thought that meant we couldn't plug in negative integers

Answer 22

I didn't know it meant we couldn't have negative outputs

Answer 23

so if that is the case then f(0) is also 0

Answer 24

though I guess we couldn't use that really because the input ended up being 0 instead of positive integer

Answer 25

that was above when I replaced n with 2

Answer 26

so f(3)=1

Answer 27

oh my

Answer 28

I wonder if this is fibnooci sequence

Answer 29

we know that the function will give positive value
we can prove that n can't be negative
\[f(3-1)-f(3)-f(-1)=0or1\]\[0-ve-f(-1)=0or1\]to make LHS 1 or 0 -f(-1) has to be positive so f(-1) has to be negative and this can't happen
so we can't have negative n
hmm is this special case or general

Answer 30

definitely not Fibonacci sequence I don't think the 9999th term is 3333

Answer 31

and I got f(3)=1 by the following:
\[f(2+1)-f(2)-f(1)=0 \text{ or } 1 \\ f(3)-0-0=0 \text{ or } 1 \\ f(3)=1 \text{ since } f(3)>0\]

Answer 32

yes

Answer 33

\[f(2+2)-f(2)-f(2)=0 \text{ or } 1 \\ f(4)=0 \text{ or } 1 \]
we can't determine f(4) yet

Answer 34

actually I think I just determine it was 1

Answer 35

watch this...
\[f(3+1)-f(3)-f(1)=0 \text{ or } 1 \\ f(4)-1-0=0 \text{ or } 1 \\ f(4)=1 \text{ or } 2 \]

Answer 36

yes :)

Answer 37

\[f(4)=(1 \text{ or } 2 ) \text{ and } (1 \text{ or } 0)=1\]

Answer 38

that f(9999)=3333 seems interesting...

Answer 39

tricky and confusing..nice question

Answer 40

yeah @Kainui kinda brought up functional equations and I said I was going to do my own research
thought it would be nice to post this question since it did look tricky and fun

Answer 41

maybe we can try to use that cauchy equation thing on page 8

Answer 42

but we have a problem for the or 1 part

Answer 43

\[\text{ if } f(m+n)-f(m)-f(n)=0 \text{ then } f(m+n)=f(m)+f(n) \\ \text{ then } f(x)=cx \text{ where } c \text{ is a constant }\]

Answer 44

\[\text{ if } f(m+n)-f(m)-f(n)=1 \text{ then } f(m+n)=f(m)+f(n)+1 \\ \text{ and if } f(x)=cx+b \\ \text{ then we have } \\ c(m+n)+b=cm+b+cn+b+1 \\ c(m+n)+b=c(m+n)+2b+1 \\ b=2b+1 \\ -b=1 \\ b=-1 \]
so I guess f(x)=cx-1 ...if I did that right

Answer 45

\[f(2)=0 \\ \text{ so } f(x)=cx \text{ or } f(x)=cx-1 \\ \text{ if } f(x)=cx \text{ then } f(2)=2c=0 \implies c=0 \text{ so } f(x)=0 \\ \text{ or we could have } \\ f(x)=cx-1 \text{ then } f(2)=2c-1=0 \implies c=\frac{1}{2} \\ \text{ and so } f(x)=\frac{1}{2}x-1\]

Answer 46

now f(3)>0
\[\text{ but we got } f(3)=1 \text{ and neither one fits }\]

Answer 47

but maybe for some values we have f(x)=0
while for other values we have f(x)=cx-1
but I solved f(3)=c(3)-1 for c and got c=2/3
and this does not work for f(9999)=3333

Answer 48

maybe f(x)=cx-1 isn't the most general form for f(m+n)=f(m)+f(n)+1
that could be another possibility

Answer 49

f(5) will be 2

Answer 50

shuld we find values like this or do some other approach

Answer 51

I was trying another approach

Answer 52

any approach you can think of

Answer 53

how did you get f(5)=2?

Answer 54

\[f(4+1)-f(4)-f(1)=0or1\]\[f(5)-1=0or1\]
\[f(2+3)-f(2)-f(3)=0or1\]\[f(5)-2=0or1\]
If the 1st eq has value 0 then f(5) will bw 1
and if this happens the 2nd equation will become -1
so f(5)=1 is rejected
now we have only 1 option left in 1st eq
so f(5)-1=1 so f(5)=2

Answer 55

but f(2)=0 and f(3)=1
so -f(2)-f(3)=-0-1=-1 not -2

Answer 56

): sry i made a mistake out there

Answer 57

don't be sad

Answer 58

I did find a answer. I don't know how much I like it.

Answer 59

http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln821.html

https://books.google.com/books?id=okx0d9jdM8oC&pg=PA144&lpg=PA144&dq=f(m%2Bn)-f(m)-f(n)%3D0+or+1+f(2)%3D0+f(9999)%3D3333&source=bl&ots=ZzeuD3JYXc&sig=w9iQWXkv97DpyGpKSMxfmCtJB1A&hl=en&sa=X&ved=0ahUKEwiskYiY0aLJAhVLmR4KHWoNBDcQ6AEIODAF

Answer 60

I guess the integral part of the question was to be a big hint

Answer 61

it looks like I could of half used cauchy if I used the right condition...
\[f(x)=cx \\ f(9999)=c \cdot 9999 \\ 3333=c \cdot 9999 \\ c=\frac{1}{3} \\ \text{ so } f(x)=\frac{1}{3} x\]
and then I guess we were suppose to observe a pattern and say hey let's take the integer part of that answer

Answer 62

yea

Answer 63

\[f(x)=\text{integer part of } (\frac{1}{3} x)\]

Answer 64

thank you imqwerty for putting much effort into this problem with me

Answer 65

haha :D no problem

Answer 66

I'm still looking at this, I have several ideas to share however this morning has been busy, I went out to eat breakfast and planning a winter vacation with a friend in Europe so I haven't been able to chip in yet!

Answer 67

I used @freckles trick of changing m=2 and go this form, also I changed that 0 or 1 into a function r(n) just for my own purposes it's not really anything too special. So I start from here:

\[f(k+2)-f(k)=r(k)\]
From here I telescope over this sum keeping in mind that k either goes over only even or only odd numbers depending on where I start from: (If you have questions or doubts I can try to derive this, but it sort of makes more sense to me to just write it out as this)

\[f(n) - f(a) = \sum_{k=0}^{(n-a-2)/2} r(2k+a)\]

So I try plugging in:

\[f(1982) = \sum_{k=0}^{989} r(2k+2)\]

since r(n) is either 0 or 1, the best my method here does so far is puts a bound on f(1982) somewhere between 1 and 990. What remains to solve for is the general form for just the even terms of r(n). In a way though, that seems like most of the problem, all I've done is just rewrite it a little bit. Hmmm...