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 ]

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
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
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
represented by an n-digit radix r=2 number defining the combination in

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

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

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

Best regards,
Knud Thomsen

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

[Privacy Policy] [Terms of Use]

© The Math Forum 1994-2015. All Rights Reserved.