Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
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
2) Is added
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
2) Is added
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
|
|
|
|
