Hello Hawston.
Thanks you for your answer. Now i undestand very well the solution.
Really thanks :)
2009/8/19 Hawston LLH <[email protected]>
>
>
> 2009/8/19 Saul Hidalgo <[email protected]>
>
>> Thanks Sami.
>>
>> Now, i have some new questions.
>>
>> About the Solution A:
>>
>> 1. I undestand this ecuation:
>>
>> α^n == an + bn*sqrt(5); (Alpha)^n ( α^n = summation of i
>> from 0 to n {nCi. 3^i . [+sqrt(5)]^(n-i) })
>
>
>> but, i do not sure that:
>>
>> β^n == an - bn*sqrt(5); (Beta)^n ( β^n = summation of i
>> from 0 to n {nCi. 3^i . [-sqrt(5)]^(n-i) })
>>
>> Are both an and bn the same? How can i see it?
>>
>
> Use binomial expansion (shown above in red), expansion of both α^n and β^n
> got n+1 terms, the corresponding coefficients of even terms (pure integers)
> are the same but the odd terms (contains sqrt(5)) differ by a negative sign.
> Thus adding up even terms will get an, and adding up odd terms will get (+)
> bn*sqrt(5) for α^n and (-) bn*sqrt(5) for β^n.
>
> By summing of α^n and β^n = Xn will cancel out odd terms (or bn), and even
> terms will be doubled (2an), hence Xn is pure integer. So far the (1)
> equation analysis only bring one conclusion: Xn is integer, that's all.
>
> from (2) point, it further analysis β^n term, since β < 1, then β^n < 1.
> Then Xn is the first integer greater than α^n, thus the integer part of α^n
> is definitely Xn - 1 !!! e.g. α^n = 123.45678, β^n = 0.5432, Xn = α^n + β^n
> = 124, thus the integer part of α^n = Xn -1 = 123 !
>
> So instead of calculating α^n (the initial question) or β^n in exact form,
> we use the fact that Xn = 2an. The remaining is to find an.
>
>
>
>
>
>>
>>
>> 2. Suppose that
>>
>> (Alpha) == 3+sqrt(5);
>>
>> ==>
>>
>> (Alpha)^n == an + bn*sqrt(5);
>>
>> And then ==>
>>
>> (Alpha)^(n+1) == (3+sqrt(5)) * (an + bn*sqrt(5));
>>
>> Fine, now ... similar to the Solution A...
>> a_(n+1) == 3*an + 5*bn;
>> b_(n+1) == (3*bn + an)*sqrt(5); (remove the sqrt(5), bn itself
>> do not contain the sqrt(5), remember α^n == an + bn*sqrt(5), both an and bn
>> are integers!)
>>
>> Now, the target is find an and bn, if i found an and bn with the
>> ecuation (4), why is it wrong??
>>
>> (an + bn*sqrt(5))%1000; //It should be right. (this is correct
>> mathematically, but it may involve numerical precision error, so it is
>> better to manipulate integers rather than double)
>>
>> About the Solution B:
>>
>> 1. In the step/equation (6). How can i write the matrix?
>>
> step (6) itself do not contain recurrence form (n -> n+1), thus we need to
> use (1) and (6) and generalize into (7) which is recurrence.
> (Xn+2 ) = (6 -4) (xn+1 )
> (Xn+1 ) (1 0) (xn )
>
>>
>>
>> Thanks again :):)
>>
>>
>>
>> On Wed, Aug 19, 2009 at 9:12 AM, Sami Ghawi <[email protected]> wrote:
>>
>>>
>>>
>>> As you can see, we used a conjugate to get rid of the number's
>>> irrationality. so (3+sqrt(5))^n=r-(3-sqrt(5))^n
>>> since 3-sqrt(5) is always less than 1 no matter what the value of n,
>>> then the integer value of (3+sqrt(5))^n=r-1
>>> to avoid negative values, we used instead (r+999)%1000
>>> Calculating the value of r by using fast exponentiation and
>>> multiplying it with x0,y0 (2x1 matrix of x0 y0) where x0=1 and y0=0.
>>> you get that it equals m[0][0] +m[1][1]
>>> But m[0][0] = m[1][1]
>>> so the answer is (2*m[0][0]+999)%1000
>>>
>>> I hope i managed to help
>>>
>>> Sami
>>>
>>>
>>> On Aug 18, 1:07 pm, Saul Hidalgo <[email protected]> wrote:
>>> > Hi...
>>> >
>>> > I was trying to solve the problem Number(Round 1A). I read the
>>> Contest
>>> > Analysis, but... i do not undestand why do they calculate that.
>>> >
>>> > "return (2 * M_n[0][0] + 999) % 1000"
>>> >
>>> > Because, in this matrix (4) in the Costest Analysis, we have the
>>> > numbers an and bn.
>>> >
>>> > Why is it wrong? (an + bn*sqrt(5))%1000;
>>> >
>>> > Thanks =)
>>> >
>>> > --
>>> > Saul Hidalgo
>>>
>>>
>>
>>
>> --
>> Saul Hidalgo
>>
>>
>>
>
> >
>
--
Saul Hidalgo
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
