Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM 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 wellknown, or may be considered special cases of wellknown 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^(n1))
giving m = 2^n1, so that each of the integers 1..m effectively may be represented by an ndigit 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^(n1))
giving m = (3^n1)/2. So, in this case, combinations may analoguosly be given a radix r=3 representation.
Best regards, Knud Thomsen Denmark



