Conference rusure::math

This can be proved by induction.  For n=0 it is true.  For n>0, 3n>2n, so there
must be two stars which are in the same row (by the pigeonhole principle). 
Strike out this row, and then choose a column so as to strike out an additional
star, for a total of three.  Apply the induction hypothesis to the resulting
array, and you are done.  (It is obvious that if there are less than 3(n-1)
stars remaining this can only help.)

Place the stars like this:
  For i=1..2n, place a star at (i,i)  -- on the main diagonal
  For i=1..n, place a star at (i+1,i) -- adjacent to main diagonal
  Place a star at (1,n+1)             -- top left corner of 2nd half of array

+---------+
| * *     |
|   * *   |
| *   *   |
|       * |
+---------+

Now the stars in the first n+1 rows and columns can be removed only by
striking out some combination of n+2 rows and columns (or by striking
n+1 rows or n+1 columns, but that's not allowed by the problem).  The
remaining n-1 stars on the diagonal take n-1 more rows or columns, for
a total of 2n+1.

    re .1
    
    This doesn't work for me. Removing one row and one column and three
    stars transforms 3n stars and a 2n * 2n array into 3n-3 stars and an
    array that is 2n-1 * 2n-1. The stars are set for the inductive step but
    the array is not.

    Illustrative proof with n = 10:

    Write the numbers in sequence:

     1 2 3 4 5 6 7 8 9

    Now reverse the order of the even numbers and add a 0 for tidiness

     1 8 3 6 5 4 7 2 9 0

    Since these still run odd,even,odd.. an odd length sequence can't be 0 mod
    n.

    An even sequence can be partitioned into, at most, n/2 pairs where each
    pair sums to -1 mod n or 1 mod n depending n whether it starts at an odd
    or even slot (in this case the pair sums are 9 9 9 ... or 11 11 11). So
    again the sum can't be 0 mod n.

    Dick
    (Is that really worth 5 points?)

>    Since these still run odd,even,odd.. an odd length sequence can't be 0 mod
>    n.

No, you still need to consider the case of an odd-length sequence that contains
an even number of odd numbers.

If the odd-length sequence of length j < n begins with an odd number, then it
starts with an odd number that is at most n-j, followed by (j-1)/2 pairs that
sum to 1 mod n.  The total is at most (n-j) + (j-1)/2 = n-(j+1)/2, which is
strictly less than n.

If the odd-length sequence of length j < n begins with an even number, then
it starts with (j-1)/2 pairs that sum to 1 mod n, followed by an even number
that is at most n-j-1.  The total is at most (n-j-1) + (j-1)/2 = n-1-(j+1)/2,
which is strictly less than n.

Here's a non-inductive proof for 3(a).

Eliminate rows with more than one star until either:
  - you have eliminated n rows (and at least 2n stars), or
  - there are no more rows with more than one star.

In the first case, there are n or fewer stars remaining, and you can
remove them by eliminating n or fewer columns.

In the second case, continue eliminating rows with one star until either:
  - you have eliminated a total of n rows, so that n or fewer rows remain,
    each containing a single star, or
  - there are no more stars.

The remaining n or fewer stars can be removed by eliminating n or fewer columns.

Sorry, you're right.  Instead, consider this statement:

In an array with 2n-i rows and 3n-2i stars, there is a row with at least 2 stars
in it.

By the pigeonhole principle this will be true if 3n-2i > 2n-i, which is true iff
n>i.  So, for i=0,...,n-1 we can find a row with at least two stars in it,
strike it out, and then add dummy stars (if needed) to the new array to bring it
up to 3n-2(i+1) stars.

So after striking out n rows in this way, the number of stars plus dummies is
then 3n-2n = n, which we can strike out with n columns.

1(a)

If a corner of the cardboard touches side AB at point P, then when the triangles
are folded in, lines (not segments) AP and BP must coincide, else there will be
a wedge-shaped gap or overlap near P.  Thus, the angle at P must be 1/2 of 180
degrees, so the cardboard must be a rectangle.

When the paper is folded in, its corners meet either in a single point or
in two points -- otherwise there's a hole or overlap in the middle.

If they meet in a single point, then we can draw a perpendicular through
this point to each of the four sides of the cardboard rectangle, and around
to the back.  These perpendiculars are the diagonals of the paper quadrilateral,
and they meet at a right angle.

If the corners don't meet at a single point, then they meet at two points
along a diagonal of the cardboard rectangle.  The two edges of the paper
quadrilateral that fold in to form this diagonal must have been parallel.

1(b)

Assume WLOG that AB is no longer than BC.  Mark P at the midpoint of AB, and
R at the midpoint of CD.  Draw the circle for which PR is a diameter; mark
Q at an intersection of the circle with BC, and S diametrically opposite at
an intersection of the circle with DA.  Now PQRS is a rectangle, and when
points A and B are folded in they will coincide.  Similarly, points C and D
will coincide.  Also, line BC will fold in to lie on the diagonal QS, and
so will like DA.

re .4
    
>    (Is that really worth 5 points?)
    
    Remember that this is the *junior* competition - intended for children up
    to about 15 years of age. I will post a paper from the senior competition
    within the next few weeks and we'll see whether it is more challenging.
    (I personally find it useful to tackle a mix of problems that I can do
    and some that I can't do.)

    By the way, this particular problem becomes tedious rather than difficult
    once the solution for the ordering is "discovered". I too did it this
    way. I would be interested to see anyone's non-constructive proof.