There was once a Duke who had an awkwardly shaped duchy, laid out like this:

       XX
 XX  XXXX
 XXXXXXX
XXXXXXXXX
XXXXXXXXX
 XX  XXXXX
 XX XXXXXX
    XXXXXX
     XXXX
     XX

Each X represents a 1000-hectare square.

The Duke was out of favor with the King, and when it came time for the Duke to pass down his land, the King hatched a plan to break up the Duke’s holdings (and thus the political power of his heirs). The King proclaimed that the Duke must split all of the land among his heirs such that:

1) The land is split into at least two pieces, and
2) Every piece has the same shape and size, allowing for rotations and/or reflections of the shape.

What are the largest pieces the Duke can break his duchy into, in accordance with the King’s edict?

suppose the size of the parcels is greater than 4. Then the upper right corner can only be part of a 2x2 square or it will cut off one of its immediate neighbors. So any solution with parcels >=4 has a 2x2 square. Specifically consider parcels of size 6. That same upper corner tells us there are only five possible shapes (including mirror images):

  xx       xx       xx       xx       xx
xxx    xxxx     xxx       xx       xx
  x                 x           x       xx
                                 x

Now look at the "southwest" corner. That corner can not fit shape 1 at all, and shape 2 cuts off the two left-most parcels. That means only shapes 3-5 are still possible. But from the NW corner, shape 4 is impossible as it cuts off those same leftmost parcels, leaving only shapes 3 and 5. (And since 3 and 5 are mirrir images, this is the ONLY potentially possible 6-parcel shape.)  Now consider the two leftmost parcels themselves. If they belong to the same shape, then both 3 and 5 are eliminated: each cuts off a block of three parcels either to the N or S. So these parcels must be in different shapes. There's only one way to do that which leaves a "nook" of two parcels (two east of the left-most.) These two can not belong to separate parcels, because (see shapes 3/5 above) a parcel that has exactly one neighbor is one end of a three-parcel diagonal line, and the upper of the two remaining parcels would have exactly one neighbor if the lower were from a different shape and yet has no available three-line diagonal.

So these "nook" parcels are in the same shape, and it can only have one orientation that doesn't cut something off, where the parcels one up from the upper right corner and one to its right are the rest of the shape.

Now look at the Parcel one doewn and three to the left of the upper right corner. It can't be an end, because its diagonal line of three would at best cut off six parcels in the upper left with the wrong shape. Likewise, it can't be part of a square or the upper right corner (which is also a square, remember) would be cut off from completing the shape. But the only alternative is to simultaneously be next to exactly one parcel of a 2x2 square AND next to one end of a length-3 diagonal. There are only two 2x2 squares that are adjacent to this parcel in this way, and in both cases, there is no additional parcel to complete the shape.

so, by beginning with the only possible size-6 shape and placing it where forced to do so, we arrive at a situation where a parcel can not belong to any shape. So, the sole size six shape is impossible, and the maximum size of the solution shape is LESS THAN 6. Since an earlier poster demonstrated a solution with a shape of size 5, this is necessarily the largest piece, and is the true solution to the puzzle.

Posted by Paul on 2005-06-15 20:55:34