Hacker News Reader

Comment by akavi | Hacker News Reader

I'm unreasonably pleased that I was able to answer both the example questions.

That is wonderful. I struggled at both of them. :) If you don't mind asking, what is your current education level? These exam questions are attempted by high school teenagers in the IIT entrance exam.

Very nice. I can say that I understood the questions, but without consulting external resources, was not able to solve either. (It's been a long time since I've done chemistry, and factoring/roots was always a weakness for me)

First one's simple enough, but second one I couldn't figure out if there's a clever trick. Or are students expected to apply the quadratic formula and do a bunch of symbolic manipulation?

(Spoiler) Here's a way to do the second one: http://tinyurl.com/ojs6ux5

No factoring or quadratic formulas necessary. I'm going to write c_n instead of a_n and a,b instead of alpha,beta.

Since a and b satisfy that equation, you know that

a^2 = 6a+ 2, b^2 = 6b+ 2

and hence

c_10 - 2 * c_8 = a^8 * (6a + 2) - b^8 * (6b + 2) + 2b^8 - 2a^8 = 6c_9.

Dividing by 2c_9 gives 3.

Edit: asafira beat me to it!

Using the same convention as yours, I tried to break c_10 in terms of c_9 as follows:

(a^10-b^10) = (e a + f b) * (a^9-b^9)

Multiplying out the RHS, e = f = 1 are the best choices, but there remained a residual. At a second glance though, this residual was proportional to (a^8-b^8). Problem solved.

I think approximation can be the best way to answer these types of multiple choice questions.

Since its a quadratic, you know alpha is about 6 and beta is about -0.3. Then, since the answer is a whole number, and we're raising to high powers, you throw away the -0.3 and approximate a_n = 6^n.

Divide through by a_8 and you get (6^2 - 2) / 12, which is very close to 3.

There's an interesting connection between the roots of quadratic equations and Fibonacci-like sequences that is applicable to this problem. Let r and s be the roots of x^2 - ax - b, and let c[n] = (r^n - s^n)/(r - s).

Then c[n] satisfies the recursion c[n] = a c[n-1] + b c[n-2].

For instance, if a = b = 1, then that sequence is the Fibonacci sequence, and the quadratic is x^2 - x - 1. r is then the golden ratio, s is -1/r, and (r^n - s^n)/(r-s) is the famous Binet formula for the n'th Fibonacci number.

This applies directly to the ITT problem, giving the recurrence a_{n} = 6 a_{n-1} + 2 a_{n-2} for the a_{n} sequence from the problem, which in turn readily yields the answer.

I think it's easier to think about it as if you are just multiplying the original equations by some power of alpha or beta i.e.

alpha^(n-2)(alpha^2 - 6alpha - 2) = 0 = alpha^n - 6 alpha^(n-1) - 2 alpha^(n-2)

Hard to see without latex typing...

> Hard to see without latex typing...

MathJax to the rescue:

\[\alpha^{n-2}(\alpha^2-6\alpha-2)=0=\alpha^{n}-6\alpha^{n-1}-2\alpha^{n-2}\]

To render with MathJax, use the bookmarklet available here: http://checkmyworking.com/misc/mathjax-bookmarklet/

Since we are discussing the questions. Here is one I can't forget, it was one of the tough Physics question in the year when I took JEE.

Here goes (text from my memory): There is a rolled carpet of length, L, kept on an even floor. A person gives it a gentle push, and the carpet starts to unroll. What will be the velocity of the unrolled piece of the carpet, when the carpet is half unrolled? (You can ignore the contribution of the initial push, for this computation)

PS: I will look for answers, here tomorrow ... :-)

I sometimes wonder if I could pass the IIT JEE, were I taking them today :)

Reply on news.ycombinator.com