jetbeans's blog

Need help for a problem from ONTAK2014
By jetbeans, 10 years ago, In English

This is a problem from ONTAK 2014 and you can find the polish statment here Sumy.

You are given a sequence A = {a1, a2, ..., an}, every element in A is different.

You should construct another sequence B = {b1, b2, ..., bm} which meets the following conditions:

  1. m ≤ n
  2. sum of all elements in each subset (there are 2k subset in total) of B should be different
  3. every element in A can be represented as sum of some elements of B

n ≤ 21, 1 ≤ ai ≤ 1017

can someone provide some ideas?

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

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I suggest asking Swistakk (by PM or something) — it was his problem. Sadly, I do not remember the solution, but what I do remember is that the problem was really cool (and hard :)).

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

:>. Indeed nice problem, though I have to admit that it wasn't fully mine, I've just adapted math version of that problem to an algorithmic one.

One can firstly think of some criterion which will imply that all sums of subsets are different. I suggest you thinking about it in terms of binary expressions.

→ Reply