Optimization and Postage Stamp Problem

Question

(1)

Given the set U = {1, 2, 3, ..., 98, 99, 100} of Natural numbers, find the smallest subset S contained in U that:

For every element v belonging to U, there are a, b elements of S, not necessarily distinct, such that v = a + b or v = a.

S is smallest in having the least number of elements.

Example:

T = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90}

T has 18 elements.

Any Natural number v such that 1 <= v <= 100 can be expressed as a sum of 2 elements of T.

For instance,

19 = 9 + 10, 40 = 20 + 20 or 40 = 40

This problem seems to my mind to be related to the "postage stamp problem" in which we have an envelope that has space for 1 or 2 stamps and we wish to find the smallest set of positive stamp values between 1 and 100 so we can affix any postage between 1 and 100 on the envelope.

It seems beguilingly simple but I am not satisfied with the heuristic problem solving I have applied to it. I have constructed sets as follows:

S(n) = {1, ..., n, 2n+1, 3n+2, ..., kn + (k-1)}

1 <= n <= 100 and 2 <= k <= m, k = 1, 2, ..., m

m = smallest k of { kn + (k-1) + n >= 100 : k = 1, 2, 3, ...}

All these sets have a minimum of 18 elements. But these are very regular sets and there are much more.

For n = 6, S(6) = {1, 2, 3, 4, 5, 6, 7, 8 , 17, 26, 35, 44, 53, 62, 71, 80, 89, 98}

98 = 11*8 + (11-1), m = 11

As an example, and going back to the "postage stamp analogy," S(6) can generate every Natural number between 1 and 100 using 1 or 2 of its elements together with the operation of addition (refer to (1) above):

1 = 1, 2 = 2, ... 8 = 8,

9 = 8 + 1, 10 = 8 + 2, 11 = 8 + 3, ... 16 = 8 + 8,

17 = 17, 18 = 17 + 1, 19 = 17 + 2, ... 25 = 17 + 8,

26 = 26, 27 = 26 + 1, ...

...

89 = 89, 90 = 89 + 1, ... 97 = 89 + 8,

98 = 98, 99 = 98 + 1, 100 = 98 + 2

S(6) has 18 elements.

Recapitulating, how can problem (1) be framed in order to exhaustively rank all possible choices for S and then find those or the one with the least number of elements.

Answer 1

I am thinking on the line of calculating the total number of elements in all possible choices for the set S without listing out the elements in S.

where

S(n) = {1, ..., n, 2n+1, 3n+2, ..., kn + (k-1)}

as you have constructed.

For this, I will be establishing that

the total number of elements,  s, 

in the above constructed set,  S(n),

and with a limit of x (that's 100 in this case) 

can be calculated by the below formula:

$$s = n + floor( (x - n) / (n + 1) ) $$

where floor(y) is the greatest integer before x(the floor function).

Or in another way of expressing:

$$floor(y) \le\ y \lt\ floor (y) + 1 $$

(we will use this later in the proof)

So to utilize it just put in the numbers

for example in the case of S(8), where x = 100 and n = 8

s = n + floor((x - n)/(n + 1))
  = 8 + floor((100 - 8)/(8 + 1))
  = 8 + floor(92/9)
  = 8 + 10
  = 18

With this you can calculate every possible S(n) by substituting n.

In general you can also substitute the x with any upper limit.

I have also included my proof for the above formula

Do tell me in the comments if there is anything unclear as this is the first time I have submitted an answer.

Proof: We will split the set S(n) into 2 smaller sets, N(n) and K(n)

where

  N(n) = {1,...,n}, with total number of elements as n

  K(n) = {2n+1, 3n+2, ..., kn + (k-1)}, with total number of elements as k-1 

Since S(n) = N(n) + K(n), we can see that

$$s = n + k - 1$$

Now we will establish that

$$k - 1 = floor((x - n)/(n + 1))$$

or rather

$$k - 1 \le\ (x - n)/(n + 1) \lt\ k --- (1)$$

Lets take a look at set K(n)

remember that the integer x is the upper limit that the mentioned set should produce (in your case is 100), the relation between x, k and n will be

$$x = kn + (k-1) + c$$

where c is an integer where $0 \le\ c \le\ n$ for S(n) be true (note this)

rearranging the equation

$$x = k(n + 1) + c - 1$$ $$k = (x - (c - 1))/(n + 1) ---(2)$$

now to prove (1)

we will prove

$$(x - n)/(n + 1) \lt\ k --- (3)$$

and

$$k - 1 \le\ (x - n)/(n + 1) --- (4)$$

for (3)

looking back, we know that $c \le\ n$ , it follows that $c - 1 \lt\ n$

therefore

$$x - (c - 1) \gt\ x - n$$

dividing both by $n + 1$

$$(x - (c - 1))/(n + 1) \gt\ (x - n)/(n + 1)$$

from (2)

$$k \gt\ (x - n)/(n + 1)$$

for (4)

minus $1$ to both sides of (2)

$$k - 1 = (x - (c - 1))/(n + 1) - 1$$ $$ = (x - (c - 1) - n - 1 )/(n + 1)$$ $$ = (x - (n + c)/(n + 1)) ---(5)$$

Since c is an integer where $0 \le\ c$ , using the same method as proving (3)

$$x - (n + c) \le\ (x - n)$$ $$(x - (n + c)/(n + 1)) \le\ (x - n)/(n + 1)$$

From (5)

$$k - 1 \le\ (x - n)/(n + 1)$$

thus

$$k - 1 \le\ (x - n)/(n + 1) \lt\ k $$

is true, and

$$k - 1 = floor((x - n)/(n + 1))$$

Back to the top, since S(n) = N(n) + K(n)

$$s = n + k - 1$$ $$s = n + floor((x - n)/(n + 1))$$

Q.E.D.