[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

315.0. "Making shapes from pieces" by HARE::GILBERT () Tue Jul 16 1985 10:38

Consider a piece made up of aligned unit squares, for example,

		+-------+
		|       |
		+---+   |
		    |   |
		    +---+

and consider constructing shapes from several aligned copies of
such a piece.  For example, the following shape:

		    +-------+
		    |       |
		+---+       +-------+
		|                   |
		+---+               |
		    |               |
		    +-------+   +---+
		            |   |
		            +---+

can be disected into aligned copies of the above piece:

		    +-------+
		    |       |
		+---+---+   +-------+
		|       |   |       |
		+---+   +---+---+   |
		    |   |       |   |
		    +---+---+   +---+
		            |   |
		            +---+

1. Show that, for any piece made up of unit squares, a shape made from aligned
   copies of that piece has a unique disection into aligned copies of the piece.

2. Show that if there are two different pieces, a shape need not have a unique
   disection.

3. Is it possible to have two or more (particular) pieces, such that any shape
   made from aligned copies of the pieces has a unique disection?

(although not precisely formulated, I think you understand the problems).
T.RTitleUserPersonal
Name
DateLines
315.1METOO::YARBROUGHTue Jul 16 1985 12:396
re .3; Yes - consider the two pieces:
(1) a cross consisting of 5 squares
(2) a square consisting of 4 (or 9 or 16 etc.) squares.
Any shape made up of these pieces is uniquely so.

Lynn Yarbrough
315.2SPRITE::OSMANTue Jul 16 1985 13:275
The singular disection into aligned pieces starts to sound isomorphic to the
unique factorization properties of the integers.

/Eric

315.3R2ME2::GILBERTMon Aug 12 1985 01:243
Lynn's answer to my third question is better that the one I'd had.

As far as the first two questions go, does everyone give up?
315.4read a random note todayHERON::BUCHANANAndrew @vbo DTN 828-5805Thu May 11 1989 17:3857
> < Note 315.3 by R2ME2::GILBERT > 11-AUG-1985

> As far as the first two questions go, does everyone give up?


	Not so fast, Peter.

	Q1. Well, suppose I have a shape, S, which has two distinct 
dissections into tesselations T and T' of an oriented tile A.   Call this
property Ethel.   Suppose further, that S is minimal: that there is no smaller 
shape which is Ethel.

	Examine the squares on the Western-most column of S.   Each of these
squares in T and T' must correspond to the one of the Western-most squares
of A.   Which one?   Well, most of them we don't know.   But the Northern-
most of the Western-most column of S can only be the Northern-most of the
Western-most of A.   But knowing one square fixes the whole tile.   So T and
T' both contain the same tile in the same place.   So we can remove it, and
the shape S\{A} is Ethel.   But S was defined to be minimal Ethel.   
Contradiction.   Therefore no Ethel S exists.


	Q2. Zilliards of examples.   Q2 really just served as a entry to Q3,
of the which I find myself admiring Lynn's idea.   To prove Lynn's suggestion,
however:

	Suppose we have a shape, S, satisfying property Mavis, which is defined
in the obvious way, given Lynn's construction.   Suppose further that S is
minimal Mavis.

	Once again, let's examine that Western-most column of S.   And once
again, let's pick the Northern-most square, N, of that column.   Is the square
below N of S?   If 'no', then in both T and T', N is the Western-most blob of
the cross.   If 'yes', then in both T and T', N is the North-Western corner
of a square.   But in either case, we can remove the shape to leave some
shape S\{?} which is still Mavis, contradicting the minimality of S.   So
no Mavis S exists.


	Let me offer another pair of tiles, which have the same effect, but
the reasoning seems to me to be marginally different.

		+---+			+---+
		|   |			|   |
	    +---+   +		    +---+   +
	    |       |		    |       |
	+---+       +		    +---+---+
	|           |
        +---+---+---+

	(Q4) Can you prove it?

	(Q5) So, can we make some kind of statement about what pairs of oriented
tile will force uniqueness of tiling?   Peter said he had an example "which
wasn't as good as Lynn's".   Can you recall it?

Andrew.
315.5link to coding theoryHERON::BUCHANANAndrew @vbo DTN 828-5805Fri May 12 1989 12:1598
315.6KOBAL::GILBERTOwnership ObligatesWed Jun 07 1989 16:4824
re .5:
	Very nice!

>	(Parenthetically, a problem: if A is **, what is the smallest A' which
> will make {A,A'} efficient.   I have a solution which I believe to be the
> smallest possible.)

	Let A" be the smallest A' which makes {A,A'} efficient.  Such a A'
	exists, because the following A' is efficient with A.

		 *****
		** * **

	Now, A" is not

		**		**		*	 *		 **
		*	***	**	****	***	***	or	**

	because the following (respectively) are ambiguous:

		** **	******	**	****	***	 ***		 **
		****		**		*****	*****		**

	Thus, A" must have 5 or more squares.
315.7smallest A' such that {**,A'} efficientHERON::BUCHANANcombinatorial bomb disposal squadThu Dec 14 1989 12:1545
>> What is the smallest A' which makes {**,A'} efficient?

>           <<< Note 315.6 by KOBAL::GILBERT "Ownership Obligates" >>>
>	Let A" be the smallest A' which makes {A,A'} efficient.  Such a A'
>	exists, because the following A' is efficient with A.
>
>		 *****
>		** * **
>
>	Now, A" is not
>
>		**		**		*	 *		 **
>		*	***	**	****	***	***	or	**
>
>	because the following (respectively) are ambiguous:
>
>		** **	******	**	****	***	 ***		 **
>		****		**		*****	*****		**
>

	(Nit) Also need to check what happens if you rotate these shapes
by 90 degrees.

>	Thus, A" must have 5 or more squares.

	Suppose each row of A" is a single strip of stars, without gaps,
denoted *???* , then *???* concatenated with ** is the same as ** concatenated
with *???* .   We can do this for each row, and hence have constructed an
ambiguous shape.   Therefore, there exists a row of A' with a hole in it.
The smallest such shape, unique up to relection, is:

	* *
	***

	Note that the top row is such that {**, *_*, _} satisfy the u.p.c,
and that from the parsed top row we can parse the top shapes uniquely, as
discussed in -.2, so this *is* A".

	[Btw, I have realized that there are quite a number of questions and
topics which I looked at but didn't or couldn't solve, and where there are
still questions open.   I will go into 'retrospective mode' for a while to tidy
some of them up.   I hope to look at: 7,624,834,836,865,886,913,914,975,982,
1041,1095,1098,1149,1153,1154, if anyone cares to anticipate me.]

Andrew.