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.independent

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
Re: Two combinatorial problems
Posted: Jun 28, 2010 11:56 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Jun 28, 12:47 pm, Henry <s...@btinternet.com> wrote:
> On 26 June, 18:13, Knud Thomsen <sa...@kt-algorithms.com> wrote:
>

> > 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.

>
> The answers are correct, and the questions probably originated in
> problems of efficiently weighing with scales.
>
> The first is true because your method can generate each number
> from 0 to 2^n - 1 in only one way, and with no gaps, in effect using
> the binary counting, so there cannot be a better method.
>
> The second is true using a similar aregument: for any positive number,
> you must be able to produce a same-magnitude negative number, and your
> method can produce each number from
> -(3^n - 1)/2 to (3^n - 1)/2 in only one way, and with no gaps, in
> effect using ternary counting and subtracting (3^n-1)/2 (so the digits
> are in {-1,0,1} rather than {0,1,2}), so there cannot be a better
> method.


Many thanks, Henry - that's exactly what I needed!
And you're quite right about the original problems having to do with
weighing with scales.
In Problem 1, you're only allowed to put standard weights (from the
above-mentioned set) onto the scale opposite the scale with the goods
you want to weigh.
In Problem 2, you're also allowed to put standard weights onto the
scale with the goods.
Best regards,
Knud




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.