Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 sales@kt-algorithms.com Posts: 78 Registered: 1/29/05
Re: Two combinatorial problems
Posted: Jun 28, 2010 11:56 AM

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

Date Subject Author
6/26/10 sales@kt-algorithms.com
6/28/10 Henry
6/28/10 sales@kt-algorithms.com