Merry Discrete Christmas

Hi Kiddies,

It has come to my attention that the Chistmas period is a gloomy time for us compscis. Without our staple diet of lectures and UNIX, we feel obliged to socialise. Those of you who have ever seen (or been) a compsci socialising will know that this behaviour is guaranteed to end in tears. Help is at hand, however, in the form of Jamie’s Christmas Vacation Work (tm). Guaranteed to bring you hours of fun and excitement (*) and keep you out of harm’s way.

Have fun :o)

Jamie

(*) Your interpretation of ‘fun and excitement’ may not coincide with that of the Jamie’s Christmas Vacation Work Corporation.

To be handed at the start of next term:

Do questions 1-4 and 6-10 from the third set of exercises in the notes.

Also, for all you closet mathematicians out there, here are a couple of more interesting (read: ‘harder’) problems:

Show that a list of length 2^n, each element of which is one of a set of n positive integers contains a non-empty sub-list of numbers whose product is a perfect square. For example: [2,3,5,3,2,3,2,5] (which has 8 elements, each drawn from the set {2,3,5}) contains the sequence [3,2,3,2].

HINT: At the start of the list, and after each item, consider the set of all numbers which have appeared an odd number of times since the start of the list. What does it mean if two of these sets are the same?

Just for fun (it’s completely off the course and quite difficult) what is the smallest natural number which cannot be described in fewer than fifteen English words?

HINT: Look carefully at my description of it, but stop if your brain starts to frazzle.

Finally, prove that you’d have had a lot more fun over Christmas if you’d ignored these questions and gone out to the pub every night. You may assume the existance of a local pub, L and a social life, S.

NOTE: You can’t use this result to get out of doing the rest of the work, because you haven’t proved that you have a social life and so don’t have a rigorous proof.