Here's the problem (IMO 2013 Problem 1): Assume that k and n are two positive integers. Prove that there exist positive integers m1, ... , mk such that
There is an inductive proof, which 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 tree.
Think:
Spoiler 0How is this related to segtrees?
Spoiler 1Could you reformulate the "fraction multiplication" into something that is more similar to something related to segtrees?
Spoiler 2Maybe relating the ranges of size 2^k to the fractions of the form 1 + 1/m
Spoiler 3Yes, 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 4In 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 to a range [n, n + 2k - 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.com/blog/entry/18051, as an idea on how it works.
Mega SpoilerWhat happens when you do a range sum query? What happens to the lengths?
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 m1, ... , mk such that , where l is an integer and l ≤ 2 × ceil(log2(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 m1, m2, ..., ml.