wfe2017's blog

Segment Tree From The IMO
By wfe2017, history, 8 years ago, In English

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 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 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. Post the solution in the comments.

  • Vote: I like it
  • +71
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by wfe2017 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by wfe2017 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by wfe2017 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by wfe2017 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by wfe2017 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wfe2017 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Auto comment: topic has been updated by wfe2017 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Auto comment: topic has been updated by wfe2017 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Auto comment: topic has been updated by wfe2017 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by wfe2017 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Auto comment: topic has been updated by wfe2017 (previous revision, new revision, compare).

→ Reply