Let us consider the case \(M=X\) first.

Since integers greater than or equal to \(X\) are unnecessary, we can use brute-force search when \(X\) is small (we can find that there is no \(S\) when \(X=3,5,6,9,10\)).

Also, when \(X \ge 16\), \(S\) can always be constructed by the following procedure.

• Add powers of two to \(S\) in order, like \(S = \lbrace 1, 2, 4, 8, \dots \rbrace\), until just before the sum becomes greater than or equal to \(X\)
• If \(x:=X-1-\mathrm{sum}(S) > 0\), add \(x\) to \(S\)
  • However, if \(x\) is also power of two, duplication of elements will occur. This can be avoided by decrementing the last element of \(S\) by \(-1\) or \(-2\) beforehand.

In the case of \(M>X\), we can add appropriate elements to \(S\) created above to complete the task. For example, by adding \(2^i (X+1)\ (i \ge 0)\), we can satisfy the condition except for \(k\), which can be written as \(k = (X+1)n + X\ (n \ge 1)\). And by adding \(2X + 1\), all the conditions become satisfied.

With this solution, \(S\) will have at most \(19\) elements.