Segment Tree From The IMO

Правка en10, от wfe2017, 2017-02-04 19:33:57

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 0
Spoiler 1
Spoiler 2
Spoiler 3
Spoiler 4
Mega 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 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en13 Английский wfe2017 2017-02-08 19:48:16 71
en12 Английский wfe2017 2017-02-04 20:08:33 144
en11 Английский wfe2017 2017-02-04 19:35:37 69
en10 Английский wfe2017 2017-02-04 19:33:57 407
en9 Английский wfe2017 2017-02-04 14:52:33 604
en8 Английский wfe2017 2017-02-04 14:17:42 365
en7 Английский wfe2017 2017-02-04 11:16:24 7 Tiny change: ' $l \leq 2\ceil(log_2' -> ' $l \leq 2 \times ceil(log_2'
en6 Английский wfe2017 2017-02-04 11:15:55 12 Tiny change: 'd $l \leq log_2(k)+1$. \n\nCha' -> 'd $l \leq 2\ceil(log_2(k/2+1))$. \n\nCha'
en5 Английский wfe2017 2017-02-04 11:13:54 6 Tiny change: 'er and $l <= log_2(k)+' -> 'er and $l \leq log_2(k)+'
en4 Английский wfe2017 2017-02-04 11:13:32 211
en3 Английский wfe2017 2017-02-04 11:11:40 1307 (published)
en2 Английский wfe2017 2017-02-04 11:03:39 7
en1 Английский wfe2017 2017-02-04 11:03:15 271 Initial revision (saved to drafts)