1Thanks
LinkBack URL
About LinkBacks
Hi,
well i need some help with the following problem. I have posted fractions of this problem before and got very helpful comments. Now when the Proof is nearly done i need for someone to check it and tell me how bad the proof is. So let me recapitulate. This is a toy problem connected to CS class. What i have is :
Defn_1:
where
1. 0<A[a]<=n
2. A[a]-1 <= A[a+1] for 0<=a<=A[l]
3. A[a]-1 = A[a+1] for n-A[l]< a <= n
A[a] is an array value on position a. A[l] is the last array value such that A[l-1] < A[l] and A[l] > A[l+1] , su A[l] is the last local maximum
Defn_2:
Problem:
If y>=1 then.
Proof:
Suppose. Suppose
. By plugging in
we get
which is a contradiction. Thus for
. Furthermore, by definition 2 we have
and
thus:
by defn 2
by defn 1
Therefore if y>=1 then
_________________
So this is how far i came. However i feal that i am missing something since my domain (array length) is limited. Or should i say, i feal that the above would hold if array was infinite in size. Also to depict the problem i am going to give an example:
A is my array
. . 0 1 2 3 4 5 6 7 8 9 0 1 2 3
A: 7 6 5 4 6 5 4 3 2 5 4 3 2 1
the claim that i should prove is, if i make k jumps where k im my example let say is 1, the the distance if i start in 0 -> A[0]=7 equals 10 since |A[0]| + |A[7]| = 10. But this will not hold if my k =4 because then i am out of range. and this is what is bugging me. all examples that i have seen up until now are working with sets that are infinite in size and i have not seen an example that is limited by a size....
so please help by giving an advice on what should i read or what should i do to make my proof and problem definition correct. And please check what nonsense have i written in the section above. Remember that i am still learning how to prove claims.
Thank you
baxy
