Return to Answer

I've verified the statement for all $k\leq 15$ with the following greedy algorithm combined with (multiple) initial random shufflings.

Greedy algorithm. Given an ordered list with $k$ values of $x$'s, we start with $s=0$, and at each of $k$ steps we extract and add to $s$ the first element $v$ from the list such that $0\leq s+v<1$. The algorithm succeeds if we are able to extract all $k$ elements from the list, and fails otherwise (when at some step a suitable element does not exist).

From Fedor's observation it follows that for a fixed $k$, we can restrict our attention to values $x_1 = \frac{m}{2^k-1}$ for $m\equiv 2\pmod4$ in the interval $[2,2^k-2]$ and the sequences of $x_i$ emerging from them. For each such sequence, we try the greedy algorithm on its various random shufflings until one succeeds.

It's worth to note that for a fixed $k$, the average number of random shufflings (over all $m$) used in my computation was about $2.5^k$.

PS. The order of nonincreasing absolute values suggested by Alex Ravsky above works well for a noticeable fraction of sequences and can be used before going into random orders, although this fraction decreases as $k$ grows.

UPDATED. I've changed the verification strategy and computationally proved the statement for all $k\leq 30$, using the following randomized algorithm.

Randomized algorithm. For a given list of $k$ values of $x$'s sorted in increasing order, we set initially $s=0$, and at each of $k$ steps we identify the range of list elements that belong to the interval $[-s,1-s)$, select one of them, say $v$, randomly, remove it from the list, and add $v$ to $s$ (thus keeping $s$ in the interval $[0,1)$). The algorithm succeeds if we are able to make all $k$ steps, and fails otherwise (when at some step there are no suitable elements in the list).

From Fedor's observation it follows that for a fixed $k$, we can restrict our attention to values $x_1 = \frac{m}{2^k-1}$ for $m\equiv 2\pmod4$ in the interval $[2,2^k-2]$ and the sequences of $x_i$ emerging from them. For each such sequence (sorted in increasing order), we run the randomized algorithm multiple times until it succeeds.

It's worth to note that for a fixed $k$, the average number of algorithm runs (over all $m$) used in my computation was about $k/2$.

I've verified the statement for all $k\leq 13$ with the following greedy algorithm combined with (multiple) initial random shufflings.

Greedy algorithm. Given an ordered list with $k$ values of $x$'s, we start with $s=0$, and at each of $k$ steps we extract and add to $s$ the first element $v$ from the list such that $0\leq s+v<1$. The algorithm succeeds if we are able to extract all $k$ elements from the list, and fails otherwise (when at some step a suitable element does not exist).

From Fedor's observation it follows that for a fixed $k$, we can restrict our attention to values $x_1 = \frac{m}{2^k-1}$ for $m\equiv 2\pmod4$ in the interval $[2,2^k-2]$ and the sequences of $x_i$ emerging from them. For each such sequence, we try the greedy algorithm on its various random shufflings until one succeeds.

PS. The order of nonincreasing absolute values suggested by Alex Ravsky above works well for a noticeable fraction of sequences and can be used before going into random orders, although this fraction decreases as $k$ grows.

I've verified the statement for all $k\leq 15$ with the following greedy algorithm combined with (multiple) initial random shufflings.

Greedy algorithm. Given an ordered list with $k$ values of $x$'s, we start with $s=0$, and at each of $k$ steps we extract and add to $s$ the first element $v$ from the list such that $0\leq s+v<1$. The algorithm succeeds if we are able to extract all $k$ elements from the list, and fails otherwise (when at some step a suitable element does not exist).

From Fedor's observation it follows that for a fixed $k$, we can restrict our attention to values $x_1 = \frac{m}{2^k-1}$ for $m\equiv 2\pmod4$ in the interval $[2,2^k-2]$ and the sequences of $x_i$ emerging from them. For each such sequence, we try the greedy algorithm on its various random shufflings until one succeeds.

It's worth to note that for a fixed $k$, the average number of random shufflings (over all $m$) used in my computation was about $2.5^k$.

PS. The order of nonincreasing absolute values suggested by Alex Ravsky above works well for a noticeable fraction of sequences and can be used before going into random orders, although this fraction decreases as $k$ grows.

I've verified the statement for all $k\leq 25$ with the following greedy algorithm combined with (multiple) initial random shufflings.

Greedy algorithm. Given an ordered list with $k$ values of $x$'s, we start with $s=0$, and at each of $k$ steps we extract and add to $s$ the first element $v$ from the list such that $-1<s+v<1$. The algorithm succeeds if we are able to extract all $k$ elements from the list, and fails otherwise (when at some step a suitable element does not exist).

From Fedor's observation it follows that for a fixed $k$, we can restrict our attention to values $x_1 = \frac{m}{2^k-1}$ for $m\equiv 2\pmod4$ in the interval $[2,2^k-2]$ and the sequences of $x_i$ emerging from them. For each such sequence, we try the greedy algorithm on its various random shufflings until one succeeds.

It's worth to note that for each $k$ the maximum of numbers of random shufflings (for different values of $m$) used in my computation was about $2^{k/2}$, while their average was bounded by $k\log(k)^2$ or alike.

PS. The order of nonincreasing absolute values suggested by Alex Ravsky above works well for a noticeable fraction of sequences and can be used before going into random orders, although this fraction decreases as $k$ grows.

I've verified the statement for all $k\leq 13$ with the following greedy algorithm combined with (multiple) initial random shufflings.

Greedy algorithm. Given an ordered list with $k$ values of $x$'s, we start with $s=0$, and at each of $k$ steps we extract and add to $s$ the first element $v$ from the list such that $0\leq s+v<1$. The algorithm succeeds if we are able to extract all $k$ elements from the list, and fails otherwise (when at some step a suitable element does not exist).

From Fedor's observation it follows that for a fixed $k$, we can restrict our attention to values $x_1 = \frac{m}{2^k-1}$ for $m\equiv 2\pmod4$ in the interval $[2,2^k-2]$ and the sequences of $x_i$ emerging from them. For each such sequence, we try the greedy algorithm on its various random shufflings until one succeeds.

PS. The order of nonincreasing absolute values suggested by Alex Ravsky above works well for a noticeable fraction of sequences and can be used before going into random orders, although this fraction decreases as $k$ grows.