Message-Id: <200004050611.CAA26472@theory.lcs.mit.edu>
To: 6042-staff@theory.lcs.mit.edu
Subject: PS7 grading
Date: Wed, 05 Apr 2000 02:08:10 -0400
From: Victor Luchangco <victor_l@raven.lcs.mit.edu>


Hi folks,

	This problem set was happily much easier to grade, 
and so I'm done already.  So I thought I would send out my
grading guide.  Each problem is worth 10pts.

Problem 1: 
All my kids got this, but here's a breakdown of what I think
they should say:
a. Pigeonhole principle: 3pts
b. Five points are pigeons, pairs of parity are holes: 4pts
c. Some argument that two in the same hole gives integer midpoint: 3pts

Problem 2a:
I thought a pretty straightforward pigeonhole, but a lot of 
my kids had some difficulty:
a. State that we will do a pigeonhole argument: 2pts
b. Numbers are the pigeons: 1pt
c. Pairs of consecutive integers are the holes: 4pts
   (Note, some of my kids just said something like "there are n 
   non-consecutive integers," or "put numbers in the same hole if they
   are consecutive."  This is not good enough.  I would take 2pts off
   for this.  They need to state clearly what the holes are.
d. Some argument (or at least a statement) that consecutive integers 
   are relatively prime: 3pts
   (I would take off 1pt if they just state it with no indication at
   all why this is true.)

Problem 4: 
Double pigeonhole:
a. Note that this is a pigeonhole proof: 2pt
b. Note that it requires two uses of pigeonhole: 1pt
   (Probably just by using it twice.)
c. For each color, 20 beans into 6 jars gives at least 2 in 1 jar: 3pts
d. Pigeons for 2nd p.p. are the two beans in one jar for each color: 3pts
   (If they say that the pigeons are the colors, then they need to be 
   clear that each color is assigned to a jar where at least two beans 
   of that color are.  If they obviously mean this--because they did the
   proof right--but aren't clear about this, I would take off 1pt.)
e. Conclude that at least one jar has two beans of each of two colors: 1pt

Some people argued this by trying to show a worst-case.  The best
version of this argues that for each jar, at most one of each color,
except for one color, can be the jar.  Then says that there aren't
enough jars to do this.  This is right, but not clear, so 8pts.  None
of the attempts to do this that I saw are worth even that.  The best
thing I saw said at most one of each color, except for one color, but
then concluded that you can't do better (why not?).  I would give this
at most 5pts, and less if it isn't completely clear.  Note that you 
cannot argue that there will be too many beans in total--or at least
I don't see how you can.

Problem 5: 
Pretty straightforward, but they need to give some explanation for 
their answer. 
a. Correct answer: 6pts
b. Explanation: 4pts (you can take off pts if the explanation isn't good)

One of my kids did a sum: C(14,1) C(8,5) + C(14,2) C(8,4) + ...
I might take off 1pt just because it isn't as simple an answer as is
available.  (My kid actually left off the last term, so I took off 
more than that.)

Problem 6: 
Again, they need to explain their answer:
a. Right answer: 4pts
b. Explain how to count: 3pts
c. Argument that assignment to poles has unique arrangement: 3pts.
   (This doesn't have to be elaborate, but they do have to say
   something about it.)
At least one of my kids had a rather elaborate and rather confusing way
of doing this, and so I took a point off for that (and more because it
was poorly explained).  

Problem 7:
a. Recognize it as inclusion-exclusion: 1pt
b. # of ints <= 1000 divisible by i is \floor{1000/i}: 2pts
   (1pt if they just give you a number, rather than the form, unless 
   they say something about it.)
c. Set up i-e form correctly: 1pt
d. Note that div by 6 and div by 15 is the same as div by 30, etc: 2pts
e. Argue that (d) is true (by noting 30 = lcm(6,15)): 1pt
f. Doing the calculation right: 1pt
g. Doing the 1000 - x, to get those not div by 6, 10 or 15: 2pts

Problem 8: 
a. Recognize that it is incl-excl: 1pt
b. Note that non-square-free are div by 4, 9, 25, 49, and 121: 4pts
   (1pt off if they don't give some reason why you don't go higher than 
   this, either here or later when doing the intersections, 1pt off if
   they leave all the other squares even if they do it correctly, 2pts
   off if no explanation, and 1pt off if it is not a good one.)
c. Setting up incl-excl correctly (possibly truncated): 1pt
d. Argument that all but first two intersections are empty: 1pt
   (So they would lose 2pts total if they don't do this anywhere, but
   only 1pt if they don't do it here, but do it earlier.  If they d
   it here but not earlier, I wouldn't take off for it at all.)
e. Doing the 150-x: 2pts 
   (1pt off if they do 151-x.)
f. Getting the right answer: 1pt

Problem 9:
2pts per part: 1pt for answer, 1pt for explanation.

Problem 10: 
2pts per part: 1pt for answer, 1pt for explanation.
(Don't double count them off if they make a mistake in an 
earlier part, and use that in a later part.)


Okay, that's it.  I hope that sounds okay to everyone.

				Victor