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, which is generally the more popular solution among IMO contestants, but I would like to demonstrate a solution that relates this problem to a well-known data structure: the segment tree. ↵
↵
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 we could relatinge the ranges in a segtree to 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. Note that we could multiply the numerator and denominator by the same number. For example $\frac{9}{8} = \frac{72}{64}$. 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. Which ones have anything in common with fractions of the form 1+1/m? How about if the size is 2, 4, or 16?↵
↵
Let's try to turn the LHS fraction $\frac{n+2^k-1}{n}$ to a range $[n, n+2^k-1]$. "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$. Post the solution in the comments.
↵
There is an inductive proof, which is generally the more popular solution among IMO contestants, but I would like to demonstrate a solution that relates this problem to a well-known data structure: the segment tree. ↵
↵
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 we could relat
</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. Note that we could multiply the numerator and denominator by the same number. For example $\frac{9}{8} = \frac{72}{64}$. 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. Which ones have anything in common with fractions of the form 1+1/m? How about if the size is 2, 4, or 16?↵
↵
Let's try to turn the LHS fraction $\frac{n+2^k-1}{n}$ to a range $[n, n+2^k-1]$. "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$. Post the solution in the comments.
