(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

_{1},...,a

_{n}) such that 1/a

_{1}

^{2}+ ... + 1/a

_{n}

^{2}= 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

_{0}=n

_{0}(k) such that

all n ≥ n0 there exists (a

_{1},...,a

_{n}) such that1/a

_{1}

^{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

_{0}(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

_{1},...,a

_{n}) such that1/a

_{1/}

^{k}+ ... + 1/a

_{n}

^{k}= 1.

If so then find the values (a

_{1},...,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

_{0}(k) is hard. I also suspect that proving that this is hard

will be hard.

I like this problem a lot, and I'm assigning it in both Formal Language Theory (Sipser

ReplyDeletebook) and Discrete Math this semester.

ai 's are distinct?

ReplyDelete(This is bill but for stupid tech reasons I need to do this anon)

DeleteThe ai's NEED NOT be distinct.

For example, for n=4 we COULD use (2,2,2,2) since 1/4+1/4+1/4+1/4=1.

bill g.

I have solved it for n = 6 and I should be able to generalize for the others using the same thing. Basically start by checking for the largest part. assume there is no ai =2 then the max sum for 6 terms in 6/9 . so there must be a ai=2 and so on and so forth... Ok to post the outline so far here? :)

ReplyDeleteYES, I would be interested in your solution to see how it differs from mine (which is linked to). It sounds like you are doing a greedy solution which I don't think works.

ReplyDeleteI