| Posted on Wednesday, 06 July, 2005 - 02:40 pm: |
The following is the discussion about the 2003 BMO2 Question 3, which was:
Let f :
-> be a permutation of the set
of all positive
integers.(i) Show that there is an arithmetic progression of positive integers a ,a +d ,a +2d , where d > 0, such that
f (a ) < f (a +d ) < f (a +2d ).
(ii) Must there be an arithmetic progression a ,a +d ,...,a +2003d , where d > 0, such that
f (a ) < f (a +d ) < ... < f (a +2003d )?
[A permutation of
is a one-to-one function
whose image is the whole of ; that is, a function from
to such that for all m in
there exists a unique n
in such that f(n)=m.
]
| Posted on Saturday, 01 March, 2003 - 06:22 pm: |
As for a hint for Q3 - for the first part try setting a = f-1 (1) and remember that any subset of the naturals has a minimal member. For the second part try replacing 2003 with 3.
| Posted on Sunday, 02 March, 2003 - 12:36 am: |
Thanks for the hint on Q3 - it's late now though, I'll look at it tomorrow.
Dave
| Posted on Saturday, 08 March, 2003 - 12:14 am: |
Michael,
Today was the first chance I got to look at Q3... I think I've proved (i), not sure how rigorously tho...
Using your hint, when f(a)=1, f(a+d)> f(a) for all d. The set S={f(a+1),f(a+2),...} has a minimal member, say f(a+c). So f(a) < f(a+c) < f(a+2c).
If f(a) =/= 1, let f(a)=n. The set S is infinite; remove from it any f(a+k) which are < n, along with all f(a+j) where j is a whole divisor of k. The set which remains, S2 , is still infinite and by construction, for each f(a+r) in S2 , f(a+2r) in S2 . S2 has a minimal member, say f(a+b). So f(a) < f(a+b) < f(a+2b).
Is this argument ok? I'm still workin on (ii), but I can't seem to modify the argument further, I see no reason why f(a+3b) can't be in between f(a+b) and f(a+2b), althogh it could be greater than f(a+2b)... any more hints?
Dave
| Posted on Saturday, 08 March, 2003 - 12:32 am: |
David, you have actually solved the first part fully in your second paragraph. Remember you are allowed to choose a however you like. You know that there exists a such that f(a) = 1, so now just follow your second paragraph and you have an immediate answer to the first part.
I think your third paragraph does also work, but your second paragraph solves the problem by itself, and certainly seems the simplest approach.
I think what your third paragraph is showing is that you can make this work for _any_ a. This is more than what the question is asking you to show - but it is certainly correct!
As for part ii) - you're right. There's no reason at all that f(a+3b) can't be in between f(a+b) and f(a+2b). So why not look for a counterexample?
Hint: suppose there exists k such that for every n we have f(n) < f(n+k). Then it is obvious that the conclusion holds - just take any n, and we have f(n) < f(n+k) < f(n+2k) < f(n+3k). So as we're looking for a counter-example we can restrict our attention to functions for which this doesn't hold - in other words there must not exist k such that for all n we have f(n) < f(n+k). So it's a good idea to look for functions which have arbitrarily long decreasing subsequences.
| Posted on Thursday, 13 March, 2003 - 08:53 pm: |
Hi Michael, sorry i've taken so long to get back, mocks these 2 weeks, u know how it is...
Thanks for the tip about part i), I didn't realise I'd proved it so easily, I see now that the one case was enough. I had tried looking for a counterexample, without much luck... what exactly do you mean by functions which have arbitrarily long decreasing subsequences? Would it be something like f(n)=k-n for n < k, f(n)=3k-n for k < = n < = 2k, etc for some large k? here obviously f(n) < f(n+k+1) for all n... I seem to be a bit in the dark on this one, I just can't quite see how to construct a function that'll work.
Care to shed a little more light?
Dave
| Posted on Saturday, 15 March, 2003 - 07:47 pm: |
Hi David,
The problem is exactly as you've said: your functions satisfies f(n) < f(n+k+1) for all n, so the statement holds for your function. What you need is a function for which no inequality like that is true.
Try constructing a function as follows. Partition the naturals into intervals:
[n0 ,n1 -1]
[n1 ,n2 -1]
[n2 ,n3 -1]
...
where nr is some very rapidly increasing sequence (which we'll choose later) with n0 = 1.
Now let f be a bijection from each of the intervals to itself, but in an order reversing way.
Explicitly: on the interval [nr ,nr+1 -1] define f(n) = nr+1 +nr -1-n.
f is clearly a bijection as long as nr is strictly increasing. Now if nr increases linearly then we get something like your function and as you've pointed out this doesn't work.
So try making nr increase much more rapidly than linearly - so quickly that the resulting f is not increasing on any A.P. of length 4. (And then you're certainly done - if f is not increasing on any A.P. of length 4 it is certainly not increasing on any A.P. of length 2004.)
| Posted on Monday, 17 March, 2003 - 03:18 pm: |
Oh, I see now! That's a really nice way you put it, it really gives structure to the argument.
Once you did that the last step was easy: nr =mr for any integer m > = 3 satisfies the requirement. 2r is too slow (e.g. 6,15,24,33), but with 3r , no matter what the first two terms of the A.P. are, we cannot position the next two in separate intervals: if the first two fall in separate intervals, the 3rd must either fall in the same one as the 2nd or in the next one up; if it falls in the next one up, so must the 4th as each interval is twice the size of all the previous ones added together, meaning the d of the A.P. is less than half the size of the interval that the 3rd term falls in.
That's a bit wordy, but you get my gist... and obviously it works for m> 3 too. Is that the right answer?
Thanks for all the hints along the way, much appreciated!
Dave
| Posted on Monday, 17 March, 2003 - 09:57 pm: |
Yes exactly. The key point, as you've realised, is that nr needs to grow exponentially - polynomial growth isn't good enough. As you say nr = mr works for any m > = 3.
| Posted on Tuesday, 18 March, 2003 - 12:00 am: |
Thanks again Michael.