Conference rusure::math

        Do the pieces have to be connected?  Do they have to be
        "real" shapes like you can cut with scissors, or can they
        be arbitrary point sets?
        
        Dan

>        Do the pieces have to be connected?  Do they have to be
>        "real" shapes like you can cut with scissors, or can they
>        be arbitrary point sets?

Well, feel free... the original problem was stated with "real" shapes 
assumed, but it would be interesting to see alternatives. Proving
congruence may be tough with point sets. 

Now that I think about it, you have raised an issue: for what kinds of 
dissections is a "point set" solution feasible? Necessary?

Lynn 

    re .1 .2,
    
    By the way, what does congruence mean between two sets?  Same measure?
    That would be easy.
    
    Eugene

>>	what does congruence mean between two sets?
        
        The same things for arbitrary sets as when the sets look
        like triangles -- there is an isometry carrying one set
        onto the other.  I.e. you can change one into the other
        with a finite sequence of reflections, translations, and
        rotations.
        
        Dan

    
    Here's an idea for a strategy for a computer program to solve this
    problem (dissecting a square into an odd number of congruent pieces).
    
    Define a legal n-tomino as a linked set of n unit squares that is
    NOT in the shape of a rectangle.  For example, here's a legal 5-tomino:
    
    		+---+
    		|   |
    	    +---+---+
    	    |	|   |
    	    +---+---+---+
    		|   |   |
    		+---+---+
    
    Have the program try fitting n n-tominos together into a square.
    For example, the program would first try each type of 5-tomino,
    attempting to fit 5 of them together into a 5x5 square.
    
    Then it would try fitting all types of 7-tominos together into a 7x7
    square.
    
    Obvious question (non-obvious answer to it though!):  If there's ANY
    solution to the problem, will there necessarily therefore be an
    n-tomino solution related to the given solution ?  For example, if some
    set of rounded shapes are a solution, can we approximate that rounded
    shape with an n-tomino that also gives a legal solution ?
    
    /Eric

    
    I've been fooling around with disjoint shapes, and still can't find
    any solution.
    
    For example, try to take a 5x5 square of 25 little squares, and
    form 5 sets of 5 little squares, such that each set is the same
    shape.  Don't even restrict yourself to connected squares !
    
    /Eric

        How about a hint, like, what is the smallest odd number
        (greater than one) of pieces for which it is known it can
        be done?
        
        Dan

The smallest square known so far is 15x15, using a piece that resembles a
"P" pentile. There are perhaps easier dissections for larger squares. 

	Do you have that exact P-pentile solution ?  Is the "P" filled in,
	in the loop ?  I assume so, lest the hole not be covered by the piece.

	By the way, you didn't say 15 pieces.  You only said a 15x15 square.

	Would you be willing to, and do any of you readers mind if you, publish
	the solution ?

Thanks.

/Eric

The minimal solution known is made of 25 pieces of the shape:
	+--+--+--+--+--+--+
	|                 |
	+        +--+--+--+
	|        |
	+--+--+--+

which has area 9; the total area is 25*9 = 225 = 15^2.

I don't have the exact solution with me, but I'll enter it later if no one 
else finds it first. 

I think there are also solutions based on the P-pentomino itself with more 
pieces, but I haven't found one yet.

Lynn 

   Try this:
    
             ________________________________
             |      ______|     ______|     |
             |_____|      |_____|___________|
             |     |____________|     ______|
             |____________| |   |_____|     |
             |______      | |   |___________|
             |     |______| |_  |_____      |
             |____________|   | |     |_____|
             | |   | |    |   | |___________|
             | |   | |    |___|_|     | |   |
             | |_  | |__  |___________| |   |
             |   | |   |  |_____      | |_  |
             |   | |   |  |     |_____|   | |
             |___|_|___|__|___________|   | |
             |      ______|     |     |___|_|
             |______|___________|___________|
    
    -Joe

	Hey, that's great Joe!  How did you do it ?  Did you cut out pieces
	and play with them ?

	Now, is this really the minimal solution to the problem ?  Seems kind
	of eerie if it is.

	/Eric

    No, I didn't cut anything out.  Just good old graph paper.  I used
    the obvious ways to add the sides up to 15 units and worked in and
    arround a corner.
    
    I don't know if there is a smaller solution.  At least I can't prove
    it.  I had pretty much settled on trying 15 X 15 before any hints
    were given.  I had looked at 3 X 3 and 5 X 5, and intuitively came
    to the conclusion that I needed an odd unit side that was not prime.
    Fifteen seemed the logical choice.  The hints confirmed that.  
    
    -Joe

Coyle's solution is correct, but not unique. Obviously there are many
solutions based on flopping pairs of pieces, but there are many different
rearangements of larger groupings of pieces. How many different ones can 
you find?

Then, there's the question of what *other* shapes are useful, and whether 
there may yet be solutions with fewer pieces. It certainly seems there 
ought to be solutions based on the P-pentomino.

An interesting point ot this puzzle is that no symmetry principles can 
apply: what can the "middle" piece look like?

Lynn 

    
    
    Here's a simpler answer that I just found on REC.PUZZLES.  Makes
    me wonder if there's even a simpler one...
    
    /Eric
    
Article         5143
Path: engage.enet.dec.com!shlump.nac.dec.com!ryn.esg.dec.com!decvax!mcnc!mephisto!tut.cis.ohio-state.edu!snorkelwacker!husc6!m2c!wpi!drwho
From: drwho@wpi.wpi.edu (Eric Ant Von Laudermann)
Newsgroups: rec.puzzles
Subject: Re: divide a square into an odd number of congruent nonrectangular pieces
Summary: An answer
Message-ID: <6947@wpi.wpi.edu>
Date: 19 Jan 90 02:25:55 GMT
References: <9001091936.AA17997@decwrl.dec.com>
Organization: Worcester Polytechnic Institute, Worcester, Mass.
Lines: 53
 
In article <9001091936.AA17997@decwrl.dec.com>, osman@hannah.dec.com (Eric, dtn 235-8439, DSG1-2/D8  09-Jan-1990 1433) writes:
> 
> 	Hi.  A problem I enjoyed recently:
> 
> 		Divide a square up into an ODD number of congruent
> 		NONRECTANGULAR pieces.
 
I got an answer!  Took only a couple of minutes with pencil & paper.
 
Spoilers:
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
___________________
|  _|  _|  _|  _| |
|_| |_| |_| |_|___|
|___|___|___| |_  |
|  _|  _| |___| |_|
|_| |_| |___|___| |
|___|___|  _| |___|       (Each piece consists of 3 unit squares.)
|  _|  _|_|___|_  |
|_| |_| |  _| | |_|
|___|___|_|___|___|
> 
> 	Can anyone think of a way to solve this on a computer ?
 
No.
                                --E.V.L.
 
"Let us think the unthinkable, let us do the undoable.  Let us prepare to
grapple with the ineffable itself and see if we may not eff it after all."
                                                       --Dirk Gently
    

Someone published a simpler solution with 15 pieces in a recent JRM. To 
duplicate it, find a dissection of a 9x5 rectangle with L-triminoes,
then stretch the shorter dimension of the rectangle until a 9x9 square 
is formed.

If disjoint pieces are permitted, a 3-piece solution is: 

Divide the square into 9x9 smaller squares. Let each 'piece' consist of
one representative row from each of the 3 3x9 strips, i.e.

	+---+---+---+---+---+---+---+---+---+
	| XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX |
	+---+---+---+---+---+---+---+---+---+
	|   |   |   |   |   |   |   |   |   |
	+---+---+---+---+---+---+---+---+---+
	|   |   |   |   |   |   |   |   |   |
	+---+---+---+---+---+---+---+---+---+
	| XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX |
	+---+---+---+---+---+---+---+---+---+
	|   |   |   |   |   |   |   |   |   |
	+---+---+---+---+---+---+---+---+---+
	|   |   |   |   |   |   |   |   |   |
	+---+---+---+---+---+---+---+---+---+
	| XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX |
	+---+---+---+---+---+---+---+---+---+
	|   |   |   |   |   |   |   |   |   |
	+---+---+---+---+---+---+---+---+---+
	|   |   |   |   |   |   |   |   |   |
	+---+---+---+---+---+---+---+---+---+