3
$\begingroup$

$N$ is an integer. We need to write $N$ as a sum of $K$ integers (not necessarily distinct) such that by adding some(or all) of the integers we can get every integer in $[1,N]$.What is the minimum value of $K$?

e.g. $N=7$ here we can write $7$ as a sum of $3$ integers $(1+2+4=7)$. And...

$1, 2, 1+2=3, 4, 4+1=5, 4+2=6, 1+2+4=7$ every integer less than equal to $7$ can be expressed by adding these integers. So minimum value of $K$ is $3$.

Doing this for small integers I guessed a solution that the minimum value of $K$ will be the length of binary representation of $N$. But I am unable find why this is the case.

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

If $N = 2^{I+1} -1$ then the minimal set of you integers is $\lbrace1,2,4,\ldots,2^I\rbrace$. Now you are left with all cases inbetween the powers of $2$ ... My suspiction is that you may iteratively apply following decomposition. Lets say $U_N$ is the set you are looking for, then: $U_N = \lbrace2^{I_N}\rbrace \cup U_{N-2^{I_N}}$, where $I_N$ the largest number $I$ so that $2^I\leq ceil(N/2)$. Edit: see comments below this answer.

$\endgroup$
3
  • $\begingroup$ I think if $N=2^{I+1}-1$ then minimum set will be {${{1,2,4,...,2^{I}}}$}. Isn't it? $\endgroup$
    – Sujan Dutta
    Commented Nov 9, 2018 at 9:59
  • $\begingroup$ Well, you are right, something is fishy,lets see : $\sum_{i=0}^I2^i = \tfrac{1-2^{I+1}}{1-2} = 2^{I+1}-1$ ... You are correct :) $\endgroup$
    – denklo
    Commented Nov 9, 2018 at 10:03
  • $\begingroup$ Your logic now holds good. Now I understand why it works. $\endgroup$
    – Sujan Dutta
    Commented Nov 9, 2018 at 10:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .