Given one rectangular sheet of paper of dimensions 8.5"x11.0",
I want to cut out two identical squares that are as large as
possible.  (Obiously, they cannot overlap.  Also, no gluing, taping,
etc. is allowed.)  Can I do better than 5.5"?  If not, can you prove
it?  If so, what is the best I can do, and how?

Randolph Finder
rf...@andrew.cmu.edu

But by observation with a 5.5" square, the only suitable solution occurs when
the square is parallel to the paper, so a larger square will not work.

If two squares are cut from the paper, there is a line which separates
them. W.l.o.g we may assume that this line has a common point with the
ray AB starting at A. (If it is parallel to AB, then at least on part
is too small to have a square of size 5,5".) This means that the line
must have a common point either with segment AE or with segment CF.
Suppose again that this is AE. In this case one of the squares lies
entirely inside the rectangular triangle AXY. Now it is easy to check
that the biggest square inside a rectangular triangle is the one with
two sides at the rectangular corner (shown by dots), thus its diagonal
is part of AE, therefore has length < AE. Consequently the side of the
square cannot be > 5.5", QED.

The same idea can be used to prove that if the unit square contains
two disjoint squares with sides a and b, then a+b<=1.

Problem: Which is the smallest square into which all the squares with
sides 1, 1/2, 1/3, 1/4, 1/5, ... can be packed without overlapping?

Laci Csirmaz

The area of an 8.5x11 piece of paper is 93.5;

The area of 2  7 2/3 sided squares is 117 5/9.

I believe that the original question is equivalent to "what is the
largest square that will fit into a trapzeoid constructed by drawing a
(straight) line through the center of an 8.5x11 rectangle."  Among
other limits, such a square certainly cannot have a side longer than
hypot(5.5, 4.25), which is 7.10633...

Help!!!  I'd like a short proof if possible that the
sign of a permutation is really well-defined, i.e.,
that any element which is a product of an even number of
interchanges is not the product of an odd number.

Please DON'T give me a proof that says "just take
the determinant of the matrix of zeros and ones representing
the permutation" unless you have a definition of the
determinant that doesn't depend on the sign of a
permutation being well-defined!!!!!!!!!!!!!

I.e., no circular arguments please.

And can you do it by tomorrow morning????

The question was:  how do you demonstrate that the sign of a permutation
is well-defined?  This is no problem.  You use the polynomial:

   p(x_1,...,x_n) = \prod_{i<j} (x_i - x_j).

S_n acts on  p  by permuting the variables.  Then p^(sigma) = +- p.
For any transposition  sigma = (rs),

   p^(sigma)(x_1,...,x_r,...,x_s,...,x_n) = p(x_1,...,x_s,...,x_r,...,x_s(n))
                                          = - p(x_1,...,x_n).

Therefore, tau \in S_n cannot have representations as both an even and
an odd number of transpostions, for in the first case the action would
change the sign of p, and in the second case it would not.  We require
that p neq -p, which follows because p is not identically zero, as can
be seen by specializing the variables appropriately, say x_i = i.

What is happening here is that we define a mechanism for specifying
the sign of each term of a determinant quite independently of any
discussion of permutations.  If you consider the Vandermonde matrix

   [  1         1         ... 1         ]
   [  x_1       x_2       ... x_n       ]
   [  x_1^2     x_2^2     ... x_n^2     ]  ,
   [       .....................        ]
   [  x_1^{n-1} x_2^{n-1} ... x_n^{n-1} ]

then each possible term of its determinant is uniquely determined by the
vector (e_1,...,e_n) of exponents of x_1,...,x_n which it entails.  Each
term x_1^{e_1}...x_n^{e_n} for 0 <= e_i <= n-1 also appears in  p, however.
Use the sign appearing in  p  as the sign for the term in the determinant.
This makes  p  equal to the Vandermonde determinant, and everything else
works out from then on.

If a permutation f is the product of both an odd and an even number
of transpositions then we may write the identity e as the product
of an odd number of transpositions.  Assume WLOG
e = (x_1 y_1) * ... * (x_n y_n) with 1 =< x_i < y_i, where n is odd.
Next, replace (x_i y_i) with (1 x_i)(1 y_i)(1 x_i) if x_i > 1.  We
now have that e = (1 z_1) * ... * (1 z_m) with m odd and z_i>1 for
all i.  This gives a contradiction, since each symbol (1 k) with k>1
must appear an even number of times, and m is odd.

Q.E.D.
--
Chris Long, 272 Hamilton St. Apt. 1, New Brunswick NJ  08901  (201) 846-5569

Lemma:  Any transposition (i.e., interchange) reverses the parity of
the permutation.

Corollary:  Any permutation that consists of an odd number of
transpositions is odd, i.e., has an odd number of inversions.
Similarly for even.

          product for 1 <= i < j <=n  of (x_i - x_j)