Conference rusure::math

Here's a fallacious proof.  Find the error in the proof.
Maybe you can then fix the proof up.

Situate the rectangles so that the sides are horizontal and vertical.

Start at the top left corner and walk around the figure as follows:
Each time you find yourself at the top left corner of a new rectangle,
proceed either down or to the right, whichever way has integral
length.  Since you are always going down or right, you will eventually
reach either the bottom border or the right border of the outer rectangle.
Since your path length has been made up of integral segments only,
this shows that the appropriate side of the original rectangle is integral.

Re: .1

>Each time you find yourself at the top left corner of a new rectangle,
>proceed either down or to the right, whichever way has integral
>length.

This was one of my attempts to prove, but you are not guaranteed to find
yourself at the top left of a new rectangle after proceeding down or right
along the previous one, for example:

   +----+-+-----..           +---->
   !    ! !                       !
   +----+ !                       !
   !  +-+-+---+       ==>         V
   !  !       !                   ?
   :  :       :

Assume the enclosing rectangle has non-integer sides but all the enclosed
rectangles have at least one integer side. We show a contradiction:

Find the leftmost vertical line that is an integral distance from the left
edge. Extend the vertical to the top and bottom of the outer rectangle and
cut away everything to the left. This cut does not affect the integer-
noninteger properties of the remaining rectangles: if they were integers
they remain so and vice versa. Find the uppermost horizontal line that is
an integral ditance from the top, extand, and cut away the top. Repeat these
two processes until there is one rectangle left. Because of the invariance
of the integer-noninteger property under this reduction, it has no integer
side, which is a contradiction. - Lynn Yarbrough

Re .3:

I don't follow your proof at all.  Why must there be a leftmost vertical line
that is an integral distance from the left edge?  Why does cutting along that
line not affect integer/noninteger properties of the remaining rectangles;
might it not cut some of them?


				-- edp

Right - my attempt was wrong. I think the approach is right but I overlooked
some cases that invalidate the argument. Not the first time! I'll try again
later.

Lynn Yarbrough

    Let's see if I can clarify Lynn's proof.

    Start at the upper-left corner of the large rectangle.  Consider the
    small rectangle that shares this corner, and determine which side is
    an integer.  If the horizontal side is an integer, slice away the
    part of the large rectangle to the left of the small rectangle's right
    side.  If the vertical side is an integer, slice away the part of the
    large rectangle above the bottom side of the small rectangle.

    Since subtracting an integer from an integer yields an integer, and
    subtracting an integer from a non-integer yields a non-integer,
    all sides of all rectangles retain their integer/non-integer property
    after they've been truncated.

    As you continue this process, eventually you will be left with only
    a portion of the small rectangle that shared the lower-right corner
    with the original large rectangle.  Since the trimming hasn't affected
    the integer/non-integer property of any of its sides, we know that 
    at least one of the sides in an integer.  And from this we can deduce
    that at least one side of the original large rectangle was as integer.

    -Jim

Re .6:

>    Since subtracting an integer from an integer yields an integer, and
>    subtracting an integer from a non-integer yields a non-integer,
>    all sides of all rectangles retain their integer/non-integer property
>    after they've been truncated.

You might have this situation:

	+------------------------
	|  A  |
	+---+--------
	| B | C
	+---+-----------

Even if rectangle A has an integer horizontal side, cutting through the
vertical right side of A will remove a non-integer length from C when B has
a non-integer horizontal side.


				-- edp

re: 313.7
	An alternate proof could explicitly handle this case, but a general
	proof would need to identify all classes of such exceptions.

re: 313.?
	The 'traversal' proof looked promising, but seems to have difficulty
	with the following diagram (choose [non-]integer sides as you wish).

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

Here's another approach. I can't formalize it yet, but it seems promising:

If there exists a non-integer rectangle whose components each have at least
one integer side, then it is topologically equivalent to a similarly built
figure in which all the fractional (i.e. non-int) sides are exact multiples
of 1/2. This we can prove cannot exist, since the area of each component
rectangle is (int * (int+1/2)) = int + 1/2; and the sum of all these is an
integral multiple of 1/2; but the total area is (int+1/2)*(int+1/2) = 
(int + 1/4), which is not an integral multiple of 1/2.

Lynn Yarbrough

(int * (int+1/2)) = int + 1/2  ???

re .11: Ooops, I meant (int * (int+1/2)) = int * 1/2 . That is, we are dealing
with multiples of 1/2 for each of the interior rectangles, while the outer
rectangle has a 1/4 left over that doesn't fit. - Lynn

I do not think the following rectangles are topologically equivalent to any set
of rectangles composed of edges whose lengths are multiples of one-half and
such that the integer and non-integer edges remain integer and non-integer
edges, respectively: 

	+-----------+
	|     1     |
	+---+---+---+
	|1/3|1/3|1/3|
	+---+---+---+

The numbers indicate lengths of the adjacent horizontal edges.  The 1/3 edges
must be mapped to edges with lengths which are odd multiples of 1/2.  Their
sum will therefore be an odd multiple of 1/2.  The 1 edge must be mapped to
an edge with an integer length.  This length must be the same as the sum
previously mentioned, which is not an integer.


				-- edp

I have also been burning up a lot of brain cells on this problem
& have come up with the following approach.  In playing around with
various partitions I noticed that all cases I came up with that
satisfied the problem conditions had the property that there existed
two sub-rectangles within the partition which shared a common edge.

Thus, I have tried (and thus far failed) to prove the following
assertion:  "if a set of sub-rectangles with at least one integer side are
placed together to form a larger rectangle, (>=) two of the sub-rectangles
will share a common side". (I am obviously excluding trivial cases
where ALL sub-rectangles have ALL integer sides).

If this could be demonstrated, then .0 could be trivially proved
by induction on the number of sub-rectangles.  If the above assertion
is false, then there must exist a rectangle such that 1) all sub-rectangles
have at least one integer side; and 2) no two rectangles share a common
side.

My next step was to attempt to characterize partitions of rectangles
where no two sub-rectangles share a common side.  It can be proved
by induction that any such partition must contain the following
structure:

			        .  |            { -, | } = mandatory lines
			        .  |               { . } = optional lines
			        .  |
			-----+-----+
                             |     |...
                          ...|     |
			     +-----+-----
			     |  .
			     |  .
			     |  .


Furthermore, two such partitions I have found (there are undoubtedly many
others) can be defined by the base partitions:

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

plus the (infinite) set of partitions obtained by recursively substituting
one of the base partitions in any sub-rectangle.  One other interesting
fact is that in either base partition, if the large rectangle has 2 integer
and 2 non-integer sides, it is *impossible* for all the sub-rectangles to have
at least one integer side.


				--- Paul Jensen

re .13; no, the figure in .8 is a counterexample.

Is an answer for this problem known?


				-- edp

 I was given this problem by a friend of mine, without the answer. I didn't
ask him if there was a known answer (and I don't know it yet). If there's
no solution to come, I'll try to contact him and ask him (or work a bit
harder myself?).

                                               Enjoy... - Nitsan

   It's not difficult to prove the theorem for certain specific cases.
   Here's a proof for the moderately complex arrangement below.

                                  
                                B        
            +----------------------------+-----------+
            |             F              |     J     |
            |E                          G|           |
            |                            |           |
            |             H              |           |
            +-------------+--------------+I         K|
            |      R      |      V       |           |
            |             |              |           |
           A|             |U            W|           |C
            |             |              |           |
            |             |      X       |     L     |
            |Q           S+--------------+-----------+
            |             |             N            |
            |             |                          |
            |             |M                        O|
            |             |                          |
            |             |                          |
            |      T      |             P            |
            +-------------+--------------------------+  
                                D                    


[Notation: '@' means 'has the property'; i = 'integer'; n='non-integer']
         
[Rules: (i +- i) @ i; (i +- n) @ n;]                                             
         A=C @ n  {Assumed}                            
         B=D @ n  {Assumed}                                                    
         A=C=E+Q
         A=C=K+O
         B=D=F+J
         B=D=P+T
         Q=S=U+M
         I=K=G+W
         F=H=R+V
         N=P=X+L
         
         E@i | F@i
         I@i | J@i
         M@i | N@i
         Q@i | R@i
         U@i | V@i
 
Now try, say, E@i and see how the rules propogate to a contradiction:

E@i & A@n ->Q@n ->T@i; &D@n -> P@n ->O@i; ->K@n ->J@i ->F@n;
-> {U,V}@n, which contradicts the last equation.

Lynn Yarbrough

...and now I think I have a complete proof for the general case. The method
of proof is to apply a set of transformations that reduces the problem space
until only one rectangle is left, with out changing the property that every
component rectangle has at least one integer side (i.e. two opposite int
sides).

The transformation rules are as follows:

1) If two rectangles share a common edge, combine them into one by erasing
that edge. (If the side erased is an integer (i) side then both ends of the
combined rectangle are i; otherwise, both sides are i+i = i.)

2) If there are no interior rectangles, then there must be a 'fault line'
joining opposite edges of the containing rectangle; split the figure along
the fault line and retain for further reduction a piece that has a
non-integer (n) edge perpindicular to the fault line. (Other wise the containing
rectangle has an i-side, qed.)

3) Reduce the number of interior rectangles thus: find an interior rectangle
near an edge. Its edges must look like

	|
	+---+--
	|   |
     ---+---+
            |
since otherwise it would have an edge in common and be reduced as in (1)
above. Transform it and the adjacent edge rectangle by extending its area 
by moving its i-edge to the outermost edge. This does not affect the 
'i-ness' of either rectangle, but reduces by 1 the number of interior 
rectangles. Repeat this until there are no more interior rectangles.

All of the three transformations may have to be used, in whatever order is
appropriate for the case at hand, but one of them always applies until the
number of rectangles has been reduced to 1.

Lynn Yarbrough

(the following idea is stolen from Jensen).

re .18
How can the centered rectangle below be extended without affecting
the i-ness of the adjacent rectangles?

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

re .18,.19; The open-ended figures on the outside are reducible by step (1).
That is the reason I specified that the algorithm operates on rectangles
near an edge; after you apply step 1 there are no 'T' intersections with
the foot of the 'T' on the outer boundary. - Lynn Yarbrough

Let me give the rest of the context.

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

Again, how is it possible to extend the center rectangle?

Or: which rectangles CAN be extended, thereby reducing the
total number of rectangles?  Can you prove that there always
exists a rectangle which, when extended, reduces the total
number of rectangles?

Also, it's unclear why a diagram with no interior rectangles
must have a 'fault' line.

					- Gilbert

P.S.  The reason I'm hounding at this is because it seems like
this approach might be fruitful (to mix metaphors).

re .21; The reduction procedure I gave specifically says to choose a
rectangle near the EDGE of the figure. You have to work from the outside
in.

If there is more than one rectangle and no fault lines then there must be
at least one line entering from each edge. In the simplest case they meet
each other and frame a central rectangle; in more complex cases they connect
up with multiple interior rectangles. The only way the four lines can fail
to form a rectangle is if two or more are concurrent, i.e. they form fault
lines. - Lynn 

re .22
> The reduction procedure I gave specifically says to choose a rectangle
> near the EDGE of the figure. You have to work from the outside in.

How near the edge must it be?

> If there is more than one rectangle and no fault lines then there must be
> at least one line entering from each edge. In the simplest case they meet
> each other and frame a central rectangle; in more complex cases they connect
> up with multiple interior rectangles.

While this may be true, it's unclear why this must be so.  For example, in
the following (partial) diagram, the lines drawn with "=" and "#" enter from
the sides, but aren't fault lines, and it's not clear that completing the
tiling must produce either an interior rectangle or a fault line.

                    +------+-----------+
                    |      #           |
		    |      #           |
		    +------+--+        |
                    |         +========+
                    +=========+        |
		    |         +---+----+
                    |             #    |
                    |             #    |
                    +-------------+----+

We make the following definitions for a rectangular tiling of a rectangle.

Def'n:	A fault line is a line segment connecting two opposite edges of the
	rectangle, and not passing through any of the tiles.

Def'n:	An interior tile has no side on the edge of the rectangle.

Theorem 1:
	Any rectangular tiling of a rectangle must either have a fault line,
	or an interior tile, or be a trivial tiling (e.g., only one tile).

Proof:
	The proof is by contradiction.  Assume we have a non-trivial tiling
	of a rectangle, with neither a fault line, nor any interior tiles.
	Furthermore, assume that this tiling has a minimal number of tiles.

	There must be at least one line entering each side of the rectangle,
	since otherwise, we'd either have a fault line or a trivial tiling.
	Consider a line ("|") entering from the bottom side ("=") of the
	rectangle, and the first intersection of this line with another line.
	This intersection can in one of four forms:

      		   |                   |         |
		 --+--     --+--     --+         +--
		   |         |         |         |
		===+===   ===+===   ===+===   ===+===

	In the first two forms, the tiles on either side of the line can be
	combined into a single rectangle, without affecting our assumptions
	(note that the intersection in the second form cannot meet the opposite
	edge, as this contradicts the assumption of no fault lines).  However,
	this contradicts our assumption of a minimal number of tiles, so we
	know that the intersection must be of the third or fourth form.

	Without loss of generality, we consider the fourth form equivalent to
	the third form.

	In the third form, consider the point just above and to the left of the
	intersection.  The tile containing this point must share a side with an
	edge of the rectangle.  It clearly can't share a side with the bottom
	or right edge of the rectangle (that would make the point either below
	or to the right of the intersection), so the tile must share a side with
	either the top ("=") or left ("#") edge (note that the sides labelled
	a, b, c, and d may have other intersections along them, but none that
	cut through the tile).

		+==+===
		|  |      +--a--+       
		c  d      #     |       
		|  |      +--b--+       
		+--+      #     |       
		   |            |       
		===+===      ===+===    

	In the first case, note that we have a fault line, a contradiction.
	In the second case, all the tiles below the line segment labelled 'a',
	to the bottom edge of the rectangle, can be replaced with a single tile
	without affecting the assumptions, except that we now have fewer tiles,
	contradicting our assumption of a minimal number of tiles.

	Thus, the assumptions must be contradicted, and the theorem is proved.

Does anyone care to post a proof that if neither (1) or (2) in 313.18 applies,
then there must be a rectangle as in (3), adjacent to two rectangles that
border the edge of the (large) rectange?

In the following tiling, which Lynn found, each tile has a 'T'
on one of its sides.

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

This pokes a hole in the proofs proposed so far (but note that it isn't
a counter-example to the original theorem), since it shows that there are
tilings that have interior tiles, none of which are of the form:

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

Does anyone have any ideas for an approach to find a possible proof?

I haven't been following this discussion, but offer the following...

If all of the horizontal edges of the rectangles are non-integral, then
all of the vertical edges are integral, and hence the containing rectangle
has an integral vertical side (being the sum of integers...)

Assuming therefore that one of the horizontal edges is integral, extend its
vertical sides up and down and excise the resulting column.  This does not
change the length of the vertical side, nor the non-integralness of the
horizontal side.

It does, however, remove 1 segment from the segments formed by projecting
all the vertical edges onto the bottom edge of the large rectangle.

Iterate this process until either (1) all the vertical edges are integral
which proves that the vertical side is integral or (2) there is only one
segment left on the bottom edge.

Since this one segment MUST be the downward projection of all the contained
rectangles, and at least one of those MUST be integral, this segment is
integral.  Since we have only been taking out integral horizontal amounts
the original rectangle must have had a integral bottom edge.

/Bevin

Back to .9-.11; I think this approach works, because of the following 
observation: It is always possible to transform the whole rectangle,
without changing its 'i-ness', by INSERTING a strip of unit width anywhere,
either horizontally or vertically. Apply this transformation wherever
required, and transform so that all non-i distances are odd multiples of
1/2, and the argument of .9 is correct: the counterexample of .11(.12?) is
overcome by inserting strips in among the 1/3's.

So the complete argument runs:

If there exists a rectangle with all non-i sides, tiled with rectangles all 
having at least 1 i-side, then there exists a topologically equivalent
rectangle all of whose non-i-edges is an odd multiple of 1/2. This is
obtained, if necessary, by inserting unit strips where needed to provide
lattice points at odd multiples of 1/2. The area of each interior rect. is
an integer multiple of 1/2, so the sum of all of them is also; but the area
of the enclosing rectangle is (m+1/2)*(n+1/2) = mn+1/2(m+n)+1/4, contradiction.

Re .28:

I do not understand how you can excise a vertical strip -- this will affect
some of the remaining rectangles.  Some of the affected rectangles might be
needed later in the algorithm.

Re .29:

I do not understand what you are changing when you insert a unit strip.  What
is gained by doing this?


				-- edp

re .9 and .-1

When you're adjusting the non-integer sides of the tiles to be multiples
of 1/2, might this also inadvertantly change one of the edges of the
rectangle to an integer?  For example ("=" and "#" mark the edges of the
original rectangle):

		#       |         #
		+===*===+===*=====+

If the two non-integer edges marked with asterisks are stretched to 3/2,
this changes a (non-integer) side of the rectangle to an integer.

 I don't know if it helps or not, but without loss of generality we can specify
that all the small rectangles (the "tiles") have one side EQUAL 1 and one side
LESS OR EQUAL 1. This is exactly equivalent to the original problem.

 The proof of equivalence is very simple:

(<==) If we have the =1/<=1 condition then each tile has an integral side
      (the "=1" side).

(==>) If each tile has an integral side, cut it to strips of width 1 along
      this side, and then cut each strip to squares of 1x1 (or 1xf in the
      edge).

re .30; what you are changing is the spacing between parallel lines, assuring
that there is a lattice point between them with coordinates that are n*1/2.
re .31; think of sliding the non-i edges (or stretching) until they line
up on the lattice, while keeping the i-edges fixed on the lattice.
re .32; I don't agree that you can restrict in this way; what about a rectangle
that abuts (on one edge) the integer sides of a thousand other rectangles?
Nor do you need to restrict in this way: the analysis is easier when you
consider dimensions that are large, but constrained as to the set of values
they are able to take on.

Re .33:

It took some work, but I think I understand what you are saying:  Suppose there
is a rectangle which has an integer vertical side and a non-integer horizontal
side and the non-integer horizontal side is not a multiple of one-half.  Without
loss of generality, assume the left side of the rectangle lies on a multiple of
one-half (if it does not, perform the operation described below on all
rectangles to the left of the current rectangle). 

Insert an extra unit into the entire rectangle:  Above or below the rectangle
under consideration, the extra unit is incorporated into whatever rectangle
happens to be above or below the right end of our rectangle.  Adjacent to our
rectangle, a new rectangle is created, with a horizontal length of one and a
vertical length equal to that of our rectangle (which must be an integer).

We now have two adjacent rectangles with integer vertical sides, so we can move
the adjoining edge back and forth without creating rectangles without any
integer sides.  There is a point which is a multiple of one-half from the left
edge of the containing rectangle within our two adjacent rectangles.  Move the
adjoining edge so that it incorporates this point. 

Repeat this procedure until all horizontal edges are multiples of one-half,
then repeat the corresponding procedure for vertical edges.

Then the area of the containing rectangle is equal to the sums of the areas
of the contained rectangles, which are multiples of one-half, so the area of
the containing rectangle is a multiple of one-half, but it is also the product
of the sides of the containing rectangle, which are odd multiples of one-half
(since they are not integers), so the area is an odd multiple of one-quarter,
which is a contradiction.

Is this correct?


				-- edp

re .34
	You've added another rectangle, and that rectangle does not have
	an integer horizontal side.  Thus, the transformation must be
	applied again and again.  Consider:

		+---- 3.7 ---+
		|            |
		2            2
		|            |
		+---- 3.7 ---+

	This is transformed to:

		+------ 4.0 -----+- 0.7 -+
		|                |       |
		2                2       2
		|                |       |
		+------ 4.0 -----+- 0.7 -+

Here's a proof!

--------

Consider the following transformation of a tiling.  It leaves any integer
side of a tile as an integer, and the integer/non-integer sides of the
rectangle retain their integer/non-integer status.

Let the lower left corner of the rectangle be at cartesian coordinate (0,0).
Then, consider the vertical edges in the tiling, in order, from left to right,
and let these be at x coordinates 0 = x[0] < x[1] < ... x[n].  Then,

	z[0] := 0;
	For i := 0 to n do
	    if x[i] is an integer
	    then z[i] := floor(z[i-1]+1)
	    else z[i] := floor(z[i-1]+1/2) + 1/2;

Thus, if the edge at x[i] is at an integer distance from the left edge of
the rectangle, so is z[i].  Transform (stretch horizontally) the tiling so
that edges and vertices at x-coordinate x[i] are now at coordinate z[i].

Any tiles with integer horizontal edges still have integer horizontal edges.
If a tile with an integer horizontal edge had vertical edges at integral x[i],
the transformed tile also has vertical edges at integral distances from the
left side of the rectangle, and the transformed tile has an integer horizontal
edge.  If a tile with an integer horizontal edge had vertical edges that
weren't at an integer distance from the left edge of the rectangle, the length
is now (integer+1/2) - (integer+1/2), another integer.

Note that the integer/non-integer status of the horizontal length hasn't
been affected.

We can apply a similar transformation in the y-coordinates, stretching the
tiling vertically.

--------

With the above transformation, we can take any tiling, and transform it
so that each non-integer edge of a tile is a multiple of 1/2, and so that
the integer/non-integer status of the edges of the rectangle is unaffected.

Given any counter-example to the theorem (in 313.0), we can transform it,
as above, into another counter-example.

However, there can be no counter-example all of whose tiles have edges that
are a multiple of 1/2, since this imples that the area of each tile is a
multiple of 1/2, and so must the sum of their areas.  However, we know the
area of the rectangle is (integer+1/2) * (integer+1/2) = integer*1/2 + 1/4,
which is not a multiple of 1/2.

Thus, there can be no counter-example to the original theorem, since it would
lead to a contradiction, and the theorem is proved.

					- Gilbert

Many thanks to everyone who contributed to solving this problem,
especially Lynn Yarbrough.  Thanks also to the proposer!

Re .35:

> 	You've added another rectangle, and that rectangle does not have
> 	an integer horizontal side.

Yes, I realized this after I entered the note and went home (naturally).  So
what is wrong with my understanding of the explanation?


				-- edp

Re .36:

It looks good to me, although a couple of things should be mentioned:  Some
non-integer sides will become integer sides.  Some rectangles will disappear,
because some vertical lines (e.g., .1 and .2) will map to the same place.
However, I do not see any way that these hurt the proof.


				-- edp

Yes, I should've mentioned that some non-integer edges will become integer.

Rectangles won't disappear, though.  An edge at .1 would map to .5, then
an edge at .2 would map to 1.5.

Re .39:

Oh, I see what happens.  But this shows another (slight) error.  The line:

	For i := 0 to n do

should read:

	For i := 1 to n do


				-- edp

Does anyone know the original source of this problem?

I am planning to send this problem in to the problem column of
a math journal, and would like to credit the original source,
if known.

I tried to trace the original source back, but got stuck. If I find the
guy who told it to the guy who told it to me - I'll resume the trace...

  Nitsan Duvdevani

    The simplest solution is to consider a checkerboard of 1/2 x 1/2 squares.
    I'll let someone else enjoy completing this proof.

A friend of mine showed me this solution:


         a b                  a           b
         ( (   iPI(x+y)       (   iPIx    (   iPIy
Let  S =  \ \ e        dxdy =  \ e    dx * \ e    dy ,
           ) )                  )           )
           0 0                  0           0

then S=0 if and only if a or b is integer (easy to see, by the Sin and Cos).
So: S=0 over each of the "small" rectangles, therefore, by summing it up,
S=0 over the "big" rectangle, therefore, A or B is integer for the "big"
rectangle.

Nitsan.

p.s. I'm not sure if that should be PI or 2PI

    Re .44:
    
    That's great!  It should be two pi, and the integrals need to run from
    wherever a rectangle starts to where it ends, rather than from 0 to
    something, but it is still an elegant proof:
    
    For each rectangle, integrate e^(2*pi*i*(x+y)) from its lower boundary
    to its upper and from its left boundary to its right.  If (but not only
    if) either the horizontal or vertical distance is an integer, the
    integral is zero (because the period of sine and cosine is 2*pi, so
    they go completely up and down in a distance of 2*pi, cancelling out).
    Each rectangle in the larger one meets this condition, so all of their
    integrals are zero.  This sum must equal the same integral for the
    large rectangle.  We can put it so that its lower and and left
    boundaries are on the x and y axes, and then the "if" becomes an "if
    and only if", so it must have an integer length on one side.
    
    
    				-- edp 

    I also partly remember another proof, based on the following lemma:
    
    Let p be a prime number; a p-rectangle is defined as a rectangle
    with one side being a multiple of p, the other being integral.
    
    Lemma: if a rectangle is tiled by p-rectangles, then it is a p-rectangle.
    
    The proof is trivial: each p-rectangle's surface is a multiple of
    p, so is the large rectangle's, being their sum; since p is prime,
    one of the sides is a multiple of p.
    
    Then, memory is fuzzier; if I remember correctly, for any e>0, there  |
    exists p prime, such that all sides multiplied by p are integral      |
    (or e-near integral?); the original integral parts become multiples   |
    of p, the lemma applies, so the large rectangle is a p-rectangle;     |
    re-dividing by p gives one of the sides being integral.               |
        
    (This was an "exercise partly solved" in Prof. Boechat's Number
    Theory course, Univ. Lausanne, in the paragraph on Diophantic
    Approximation and Dirichlet's Theorem).
    
    Would anyone care to correct the "|" part?
    
    John.

>Re .3:
>
>I don't follow your proof at all.  Why must there be a leftmost vertical line
>that is an integral distance from the left edge?  Why does cutting along that
>line not affect integer/noninteger properties of the remaining rectangles;
>might it not cut some of them?
>
>
>				-- edp

Let's see if I can break out part of this.

The existence of the required leftmost vertical line can be established by
some lemmas from the hypotheses of his RAA proof:

Given:
H1. All rectangles have at least one integer side.
H2. Both sides of the enclosing rectangle are non-integers.

Lemma 1
-------
To Be Proved:
L1. At least one smaller rectangle on the leftmost edge of the enclosing
rectangle has a non-integer vertical side.

Proof:
Assume no such smaller rectangle exists. (i.e. L1. is false)
Then, the vertical sides of all leftmost edge rectangles are integers.
(restatement of the negation of L1).
It follows that the vertical side of the enclosing rectangle must be
an integer (closure of the integers under addition).
But this contradicts H2, which asserted that both sides of the enclosing
rectangle were non-integers.
Since -L1 --> -H2, (restatement of last sentence)
it follows that H2 --> L1, (contrapositive)
and also (H1 and H2) --> L1 (irrelevance of additional hypothesis).
Q.E.D.

Lemma 2
-------
L2. There is a leftmost integral horizontal edge of a smaller rectangle interior
to the enclosing rectangle.

Proof:

We must first establish that there exists at least one interior integral
horizontal edge having one endpoint on the leftmost edge of the enclosing
rectangle.  Then we must show that that there is a leftmost one of these.

The first part is easy given L1.  It guarantees at least one bordering
rectangle with a non-integer vertical side.  It follows (by H1) that the
horizontal side of that rectangle is an integer (otherwise both sides would
be non-integers).

To establish the second part, we need to assume a finite number of rectangles.
(I don't believe this was stated explicitly, but I think it's reasonable,
and it may be necessary to make Lynn Yarbrough's procedure terminate).

We select the set of sides of rectangles on the left border with integral
horizontal sides.  Considering the lengths of these sides, we see that there
must be a greatest lower bound (minimum) within the set since it's finite (by
the mumbledy-mumble theorem of real analysis).  Choose the rightmost edge of
the corresponding small rectangle as the given-to-find 'leftmost vertical line'.

Q.E.D.

	re .-1

>>	Given:
>>	H1. All rectangles have at least one integer side.
>>	H2. Both sides of the enclosing rectangle are non-integers.

	Either H1 and H2 are contradictory, or there is no
	enclosing rectangle.

	Dan

re .48:

>>>	Given:
>>>	H1. All rectangles have at least one integer side.
                ^
Hmm.  Maybe this should say 'enclosed rectangles ..' ?
I'll take a detailed look later tonight.

>>>	H2. Both sides of the enclosing rectangle are non-integers.
>
>	Either H1 and H2 are contradictory, or there is no
>	enclosing rectangle.

I'm afraid I don't fully understand; are you saying that H1 and H2 can't both
be true ?  I think that's what I'm trying to show in .47.

	I meant the enclosing rectangle couldn't satisfy both H1
	(having at least one integer side) and H2 (having both
	sides be non-integers).  You suggested rewording H1 so
	that it doesn't apply to the enclosing rectangle.

	Dan

Somewhere I have a copy of a few dozen varied (!) proofs of this.
One was like the 'stretching transformation' in .36, another was the
double integral in .44.  The proofs were rich in variety.

This was in a math magazine.  If/when I find it, I'll let you know.

Here's a short proof.

Put one corner of the large rectangle at (0,0), and align the x- and y-axes
along the sides of the large rectangle.  To each point which is the corner of an
interior rectangle (which will include the four outer corners), apply this
transformation independently to its x- and y-coordinates:

If the coordinate is an integer, leave it alone.
If the coordinate is in (n, n+1) where n is an integer, move it to n+1/2.

It is easy to see that integer sides remain integer sides, since both endpoints
will either be moved to integers or to integers + 1/2.  It is also clear that
rectangles stay rectangles under the transformation, and that the new rectangles
will tile the new large rectangle.  Some non-integer sides may become integers,
and some sides may become zero, but this doesn't matter.  You can simply discard
the empty rectangles afterward if you like.

Assume (to get a contradiction) the original large rectangle had two non-integer
sides.  Then the corner opposite (0,0) has been mapped into (n+1/2, m+1/2) for
some integers n and m.  Considering areas gives a contradiction, since each
small rectangle has an area that is a multiple of 1/2, but the total area is a
multiple of 1/2 plus 1/4.