Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Two combinatorial problems
Replies: 2   Last Post: Jun 28, 2010 11:56 AM

 Messages: [ Previous | Next ]
 sales@kt-algorithms.com Posts: 78 Registered: 1/29/05
Two combinatorial problems
Posted: Jun 26, 2010 1:13 PM

Below two similar problems are presented for which solutions are
suggested.
Certainly someone can prove/disprove the suggested solutions, and I'm
fully aware that the problems most likely are well-known, or may be
considered special cases of well-known problems.
Apologies for any ambiguities in the statement of the problems - I'm
not a mathematician.

Problem 1
---------
Consider a set of n positive integers, designed so that by combining
these by means of addition - subtractions not allowed - one may
obtain
every integer in a range 1..m.
That is, each integer in the set may contribute to in 1 out of r=2
possible ways:

1) Doesn't contribute

For a given n, the problem is to identify that set of integers which
maximizes m (if a unique set does indeed exist).
Experiments and intuition suggest the following geometric progression
as the solution:

(1, 2, .. , 2^(n-1))

giving m = 2^n-1, so that each of the integers 1..m effectively may
be
represented by an n-digit radix r=2 number defining the combination in
question.

Problem 2
---------
This time the n positive integers may be combined using either
addition or subtraction, to produce the integer range 1..m.
That is, each integer in the set may contribute in 1 out of r=3
possible ways:

1) Doesn't contribute
3) Is subtracted

For this problem another geometric progression is proposed as the
solution:

(1, 3, .. , 3^(n-1))

giving m = (3^n-1)/2.
So, in this case, combinations may analoguosly be given a radix r=3
representation.

Best regards,
Knud Thomsen
Denmark

Date Subject Author
6/26/10 sales@kt-algorithms.com
6/28/10 Henry
6/28/10 sales@kt-algorithms.com