Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
sales@kt-algorithms.com

Posts: 78
Registered: 1/29/05
Two combinatorial problems
Posted: Jun 26, 2010 1:13 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.