Monday, January 26, 2015

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 ai in this post are assumed to be natural numbers)

Show that for all n ≥ 6 there exists (a1,...,an) such that 1/a12 + ... + 1/an2 = 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 n0=n0(k) such that

all n ≥ n0 there exists (a1,...,an) such that1/a1k+ ... + 1/ank = 1.


(sum of reciprocal kth powers)

We showed above that n0(2) ≤ 6, its easy to show no(2) ≥ 6, so n0(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 (a1,...,an) such that1/a1/k + ... + 1/ank = 1.

If so then find the values (a1,...,an).

(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
n0(k) is hard. I also suspect that proving that this is hard
will be hard.


5 comments:

  1. I like this problem a lot, and I'm assigning it in both Formal Language Theory (Sipser
    book) and Discrete Math this semester.

    ReplyDelete
  2. Replies
    1. (This is bill but for stupid tech reasons I need to do this anon)
      The 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.

      Delete
  3. 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? :)

    ReplyDelete
  4. YES, 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.
    I

    ReplyDelete