Intentionally brute force Perl solution to http://beust.com/weblog/2011/10/30/a-new-coding-challenge/

weights.pl

#!perl -w
use strict;

# Solution to http://beust.com/weblog/2011/10/30/a-new-coding-challenge/
# Chris Dolan

# Iterate over all combinations of weights, rejecting cases where they don't sum to 40
for my $w1 (1..37) {
   for my $w2 ($w1..37) {
      for my $w3 ($w2..37) {
         w:
         for my $w4 ($w3..37) {
            next w if $w1 + $w2 + $w3 + $w4 != 40;

            my @solutions;

            # look at all target weights, see if we can find a combination of the four that sums to that
            # target weight is on the "left" scale
            x:
            for my $x (1..40) {
               my $good = 0;
               # for each weight, try it on the left (-1), the right (1) or omit it (0)

               side:
               for my $side1 (-1..1) {
                  for my $side2 (-1..1) {
                     for my $side3 (-1..1) {
                        for my $side4 (-1..1) {
                           my $sum = $w1*$side1 + $w2*$side2 + $w3*$side3 + $w4*$side4;
                           if ($sum == $x) {
                              $good = 1;

                              # create a human-readable representation of the balance
                              my @left = ("[$sum]");
                              my @right = ();
                              for my $s ([$w1,$side1], [$w2,$side2], [$w3,$side3], [$w4,$side4]) {
                                 my ($w,$side) = @{$s};
                                 next if 0 == $side;
                                 if ($side < 0) {
                                    push @left, $w;
                                 } else {
                                    push @right, $w;
                                 }
                              }
                              push @solutions, join(" + ", @left) . " = " . join(" + ", @right);

                              last side;
                           }
                        }
                     }
                  }
               }
               next w if !$good;
            }
            print "WIN $w1 $w2 $w3 $w4\n";
            print "   $_\n" for @solutions;
         }
      }
   }
}

In retrospect, the solution of [1,3,9,27] makes perfect sense. There are three states for each weight: on the left side of the scale, on the right side of the scale or omitted from the scale. This trinary state maps to base-3, so weights that are multiples of 3 can represent any value up to their sum. "40" seems like an arbitrary value as the problem is described, but it's actually very specific to this problem. There is no solution for 41 or higher (you need more than 4 stones). The solution for a value less than 40 requires that the heaviest stone be decreased linearly (e.g. 39 = [1,3,9,26], 38 = [1,3,9,25], ...)