Here's the problem (IMO 2013 Problem 1): Assume that $k$ and $n$ are two positive integers. Prove that there exist positive integers $m_1 , \dots , m_k$ such that $1+\frac{2^k-1}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_k}\right).$ ↵
↵
There is an inductive proof,but some people have issues with induction because they give no insight. ↵
↵
Another solution path is just plugging in formulas and if they're right it generally works out. But there may beno hints as to where the formula came from. My proof and intuition behind my solution has a lot of similarities with howwhich is generally the more popular solution, but I would like to demonstrate a solution that relates this problem to a well-known data structure: the segment trees function. ↵
↵
Think:↵
↵
<spoiler summary="Spoiler 0">↵
How is this related to segtrees?↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 1">↵
Could you reformulate the "fraction multiplication" into something that is more similar to something related to segtrees?↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 2">↵
Maybe relating the ranges of size 2^k to the fractions of the form 1 + 1/m↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Spoiler 3">↵
Yes, each thing on the RHS may be taken as ranges. But you need the range length (including start, but not end) to be a divisor of the numerator. Hmmm now how could we do this? ↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 4">↵
In a segment tree that covers the range (1,1024), look at all the nodes that cover ranges of size 8. Do they have anything in common with fractions of the form 1+1/m? Let's try to turn the LHS fraction $\frac{n+2^k-1}{n}$ to a range $[n, n+2^k-1]$. Let's try to "modify" our segment tree so that each range overlaps with the previous range of the same size, such as [0,8], [8,16], [16,24] for size = 8. You may want to see the visualization here: http://codeforces.net/blog/entry/18051, as an idea on how it works.↵
</spoiler>↵
↵
<spoiler summary="Mega Spoiler">↵
What happens when you do a range sum query? What happens to the lengths?↵
</spoiler>↵
↵
Here's a generalization, which is much easier once you've found the segtree solution to the above problem. Assume that $k$ and $n$ are two positive integers. Prove that there exist positive integers $m_1 , \dots , m_k$ such that $1+\frac{k}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_l}\right)$, where $l$ is an integer and $l \leq 2 \times ceil(log_2(k/2+1))$. ↵
↵
Challenge: Implement the two variants of the problem. In the generalization, you are given $k$ and $n$, and you are required to output an array that consists of $m_1$, $m_2$, ..., $m_l$.
↵
There is an inductive proof,
↵
Another solution path is just plugging in formulas and if they're right it generally works out. But there may beno hints as to where the formula came from. My proof and intuition behind my solution has a lot of similarities with how
↵
Think:↵
↵
<spoiler summary="Spoiler 0">↵
How is this related to segtrees?↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 1">↵
Could you reformulate the "fraction multiplication" into something that is more similar to something related to segtrees?↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 2">↵
Maybe relating the ranges of size 2^k to the fractions of the form 1 + 1/m↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Spoiler 3">↵
Yes, each thing on the RHS may be taken as ranges. But you need the range length (including start, but not end) to be a divisor of the numerator. Hmmm now how could we do this? ↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler 4">↵
In a segment tree that covers the range (1,1024), look at all the nodes that cover ranges of size 8. Do they have anything in common with fractions of the form 1+1/m? Let's try to turn the LHS fraction $\frac{n+2^k-1}{n}$ to a range $[n, n+2^k-1]$. Let's try to "modify" our segment tree so that each range overlaps with the previous range of the same size, such as [0,8], [8,16], [16,24] for size = 8. You may want to see the visualization here: http://codeforces.net/blog/entry/18051, as an idea on how it works.↵
</spoiler>↵
↵
<spoiler summary="Mega Spoiler">↵
What happens when you do a range sum query? What happens to the lengths?↵
</spoiler>↵
↵
Here's a generalization, which is much easier once you've found the segtree solution to the above problem. Assume that $k$ and $n$ are two positive integers. Prove that there exist positive integers $m_1 , \dots , m_k$ such that $1+\frac{k}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_l}\right)$, where $l$ is an integer and $l \leq 2 \times ceil(log_2(k/2+1))$. ↵
↵
Challenge: Implement the two variants of the problem. In the generalization, you are given $k$ and $n$, and you are required to output an array that consists of $m_1$, $m_2$, ..., $m_l$.
