Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



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...@ktalgorithms.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 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. > > 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 samemagnitude 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^n1)/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 abovementioned 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



