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
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
