[Email sent on November 22, 1999, best viewed with a 
non-proportionally-spaced font like Courier.]



Hey hey, 

Next Thursday, December 2nd, at 4:30, we'll have a meeting of
the Lafayette Problem Group, still in search of a better name.
Come by and pick up a copy of the first set of problems from 
the envelope outside of Pardee 224, or just snip them off the
end of this message -- handy, no?  Get one right, win a prize.

[Still wondering why in the world you would want to be part of
all this?  A few possibilities:  

You like solving problems.
You might like solving problems, if only you had the chance to
   try.
You don't like solving problems, but your dormmates think you
   do, and image is everything.
You want to work for Microsoft, and they like asking questions 
   like these in interviews.  (They really do.)
You despise Microsoft and want to know the enemy better.
It's required for your major.
You've thought of a catchy name.]


Cheers, 
Derek


-----


				     Problem Set #1

1.  Your sock drawer is a mess.  It's got 12 red socks, 10 blue 
socks, and 10 green socks in it, but they're all jumbled together.
  
Also, your halogen lamp and your alarm clock are busted, so you 
didn't wake up from your afternoon-into-evening nap until five 
minutes before the dining hall closes, and it's dark as pitch.  
If you grab blindly into your drawer, what's the minimum number 
of socks you need to grab to insure that you've got at least 
one matching pair to put on as you slide down the banister of 
the stairway, even if the pair doesn't match your purple shirt?


2.  Three pasture fields have areas 10/3, 10, and 24 acres, 
respectively.  The fields initially are covered with grass of the 
same thickness, and new grass grows on each field at the same rate 
per acre.  If 12 cows eat the first field bare in 4 weeks and 21 
cows eat the second field bare in 9 weeks, how many cows will eat 
the third field bare in 18 weeks?  Moo.


3.  Is it possible to list the numbers 1, 2, 3, ..., 15 in such a way
that there are neither increasing subsequences of length 5 nor
decreasing subsequences of length 5?  If so, exhibit a list.  If
not, prove that it can't be done.  

For example,   [1 2 9 4 6 10 12 7 3 14 8 5 11 15 13]   is not such a 
list, since     ^ ^   ^ ^       ^                      form an increasing 
subsequence of length 5 (and there are many others).             


4.  Let f be defined on the natural numbers 1, 2, 3, ... as follows:

	f(1) = 1

	f(n) = f(f(n-1)) + f(n - f(n-1))   for n>1

Find, with proof, a simple explicit expression for f(n) which is valid 
for all n=1, 2, 3, ...


5.  Show that regardless of where you draw five points on a sheet of
paper, either (a) at least three of the points lie on the same line,
or (b) four of the points form the vertices of a convex quadrilateral.


6.  Start with a plain 8x8 grid.  Initially color some of the cells.

Now, start coloring all of the other cells you can, with the requirement 
that a plain cell can only become colored when at least two of its four 
neighboring cells to the north, east, south, and west are already colored.

What's the smallest number of cells you need to color initially to allow 
every cell in the grid to become colored eventually?  Why will no smaller 
number do the trick?