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.