A nice problem from a Romanian Math Problem Book

(All of the math for this problem is here)
My Discrete Math Honors TA Ioana showed me a Romanian Math Problem book
(She is Romanian) and told the following problem:


(All a_i in this post are assumed to be natural numbers)

Show that for all n ≥ 6 there exists (a₁,...,a_n) such that 1/a₁² + ... + 1/a_n² = 1.

(sum of reciprocals squared)

Normally my curiosity exceeds my ego and I would look up the answer.
But it was in Romanian! Normally I would ask her to read the answer to me.
But I was going out of town! Normally I would look it up the answer on the
web. But this is not the kind of thing the web is good at!

So I did the obvious thing- worked on it while watching Homeland Season 2
the first four episodes. And I solved it! Either try to solve it yourself
OR goto the link.

Some possibly open questions come out of this

1) I also prove that, for all k there is an n₀=n₀(k) such that

all n ≥ n0 there exists (a₁,...,a_n) such that1/a₁^k+ ... + 1/a_n^k = 1.


(sum of reciprocal kth powers)

We showed above that n0(2) ≤ 6, its easy to show n_o(2) ≥ 6, so n₀(2)=6.

Obtain upper and lower bounds on n0(k).

2) What is the complexity of the following problem:

Given k,n find out if there exists (a₁,...,a_n) such that1/a_1/^k + ... + 1/a_n^k = 1.

If so then find the values (a₁,...,a_n).

(We know of an example where the Greedy method does not work.)

3) What is the complexity of the following problem: Just as above
but now we want to know HOW MANY solutions.

4) Meta question: How hard are these questions? The original one was
on the level of a high school or college math competition. The rest
might be easy or hard. I suspect that getting an exact formula for
n₀(k) is hard. I also suspect that proving that this is hard
will be hard.