Aims/Objectives. The Moscow University Mathematics Undergraduate Problem Seminar  -  conducted annually by the great Russian mathematician V.I.Arnold  -  presents unsolved problems to students (and staff) to think about.  Possible solutions are presented, discussed, accepted or rejected.  Solvers usually develop into outstanding leading mathematicians.

I have a much more modest aim in my course.  I wish to draw the attention of my students to the rich resource of some well-known collections of solved problems (see recommended reading list below), and to study (by discussion, hints, etc) a selection of problems. 

In considering the types of problems that I present to my students it is uppermost in my mind that a good number of those problems to be ones they can tell to their non-mathematical friends (as challenges or fun); problems that do not require knowing any mathematical theorems or theories. Some of the topics are unashamedly 'recreational mathematics' (and why not!)...

Learning Outcomes. At the end of this course students should have added a number of new problem-solving strategies to their repertoire, and have developed (I hope!) a life-long passion for problem solving.

How I teach my course. I sit with my students in my office; we chat, ask questions, give hints, struggle towards solutions. I tell them stories about famous mathematicians (for a break from time to time), I pull my hair out; we play Nim (great fun!); we walk into Dublin one afternoon and have coffee and cakes in Panem - or somewhere nearby - and talk mathematics en route (I want them to experience that doing mathematics is not confined to sitting at a desk, and yes, I mention the classic in-joke that a mathematician is a machine for turning coffee into theorems...).
    I lend my students personal copies of problem books from the reading list (below); I expect each one to read through the book, identify a problem that appeals to them, try to solve it, and if stuck consult the sketch solution. If still stuck then talk about it with the others, and finally with me. The student will eventually make a presentation of that problem to the others and myself. 
   Sometime we will watch the Paul Erdös N is a number video ('The story of a wandering mathematician obsessed with unsolved problems'), and the Andrew Wiles BBC Horizon video...

A selection of problems that I have in mind, some of which are classics I will add more details in time, but for the moment just a flavour. If I don't attribute a problem it's simply that it's 'well-known' (it's been around for a long time...), but otherwise I will attribute when I know an actual source (which may not itself be 'original').

1. An 8 by 8 chess board may, of course, be covered with 32 non-overlapping dominoes; argue that if two opposite corners are removed then the resulting board cannot be covered with 31 dominoes. (That simple sounding problem leads to others...)

2. Play Nim (and subsequently understand the mathematical theory behind it), a game for two people: Place any number of matches in any number of piles; a player's 'move' entails removing whatever number of matches from whichever pile he/she wishes (an entire pile may be removed). It is then the other player's move, and the game continues until there are no matches left. The 'winner' is the one who removes the last match (which may be several in one move). So, get out your matches, and play...
    Do a Google web search on 'Nim'. Play Nim online (with 3 piles and a maximum of 21 'matches').
    Some 40 years ago when I first encountered 'Nim' in Hardy and Wright's great classic I rather "looked down my nose" at it, but now my attitude is that if it was good enough for Hardy and Wright to include in their Theory of Numbers then I shouldn't feel too badly about introducing it to my students.

3. Encounter the extraordinary card trick of William Fitch Cheney (this email that I sent to All Users in my college will tell you what it is if you don't already know) and study its wonderful () generalization... . In connection with the trick's generalization I will need to introduce my students to the 'base factorial' representation of whole numbers, and more besides... . Michael Kleber's (Brandeis university) Mathematical Intelligencer article - The Best Card Trick - is available here, and  a Math Forum article about it here.
    If you want to know a lot more about the mathematics of card tricks, you need look no further than Colm Mulcahy on card tricks.
    I've prepared a related Maple worksheet: (n!+n-1).mws (53KB), and for readers without Maple I have made a html version (54KB, plus an 'images' folder). I thank Michael Kleber for pointing out an error (a completely foolish one, which I told my students about) in my original presentation.
    Here was a great reaction I had in September (2002): I mentioned this trick to a second year BA student (Aoibheann R), and I told her that she would study it in the third year... A few days later she said she had told it to her father who was out of his mind wanting to know how to solve it; I was horrible and said she'd have to wait until next year... Then, at the start of the second term I displayed Ian Stewart's New Scientist article about the trick, Aoibheann read and understood it, and finally took her father out of his agony. This is precisely the sort of thing I hoped would happen... [Aoibheann went to my beloved London college - Royal Holloway College - to study for the Masters in Information Security.]

4. The classic 6-people-at-a-party problem: in a group of 6 people, argue that there must be three (at least) of them, every two of whom know each other, or there must be three of them (at least) no two of whom know each other.
    This elementary, but non-trivial problem allows one a first step into the wonderful world of Ramsey numbers. How quickly one then gets into really deep waters and unsolved problems... Look up Frank Ramsey at the monumental St Andrews University History of Mathematics site. Here are some Ramsey numbers notes that I typed up in pdf format (218KB). 
   Stanislaw Radziszowski maintains an invaluable Small Ramsey Numbers site.

5. Choose any (n+1) different numbers from the 2n numbers (1, 2, 3, ... , 2n); argue that that at least one of those must divide ('evenly') into another (different one, of course) of those. (One should keep in mind that this result is 'best possible' in the sense that the same conclusion does not necessarily hold if 'n+1' is replaced with 'n'.) 
    People 'in the know' will know that a very beautiful solution to this problem exploits the Dirichlet box principle (aka the pigeonhole principle: if m 'objects' are placed in n 'boxes', and m is greater than n, then some 'box' must contain at least two 'objects'); in fact I wish to use this problem to introduce my students to this incredibly powerful principle, and to demonstrate its power I will use it to prove (using an idea of Axel Thue's) Fermat's great classic that every prime number that leaves remainder 1 on division by 4 is expressible as a sum of two squares of integers:

 ... ad infinitum
    

    I have prepared a quite detailed Maple worksheet on this topic: Fermat-Thue (mws format (62KB), or in zip format (15KB) - in those I have removed the output which you may recreate by executing Maple commands - and for readers without Maple I have made a html format version (76KB, plus an 'images' folder)

6. Let there be any number of boys and girls at a party, and suppose no boy dances with every girl, and that every girl dances with some boy; argue that there must be a boy-girl pair (b, g) who dance, and another such pair (B, G), but that 'b' does not dance with 'G', nor does 'g' dance with 'B'. (This was problem A-4 in the 1965 William Lowell Putnam Mathematical Competition). Here is a solution that I typed up, in two formats: Word zip (18KB), rtf zip (16KB).

7. Some (positive) whole numbers can be expressed as a sum of consecutive (positive) whole numbers; e.g. 7 = 3+4, 14=2+3+4+5, ... whereas 8 cannot be so expressed (check to see). Find (with proof, of course!) those which can, and those which can't. This is an old problem, and was the subject of a paper of mine: A Halmos Problem and a Related Problem, American Mathematical Monthly, 993-996, Vol. 101, No 10, December 1994. It may be obtained by anyone with access to JSTOR, or whose university subscribes to it. If you can't access it then send me an email and I'll send you a hard copy.

8. A well known problem (dear to Paul Erdös): for any n non-collinear points in the plane, prove that some two of them lie on a line that passes through no other one of them (answering a question first posed by Sylvester). Here is a solution that I typed up, in two formats: Word zip (19KB), rtf zip (16KB).

9. A problem (with a related proof-idea): Let A be a set of 2n points in the plane, no three of which are collinear. Suppose n of them are coloured red and the remaining n blue. Prove or disprove: there are n closed line segments, no two with a point in common, such that the endpoints of each segment are points of A having different colours (This was problem A-4 in the 1979 William Lowell Putnam Mathematical Competition). Here is a solution that I typed up, in two formats: Word zip (19KB), rtf zip (16KB).

10. Prove that if n is any whole number greater than 1, then n does not divide (). This was problem A-5 in the 1972 William Lowell Putnam Mathematical Competition, and clearly it provides lots of fodder as far as understanding is concerned: why does this work with '2' (so what happens if '2' is replaced with 3, 4, 5, ... ?), and what happens if (e.g.) one replaces () with ()?

11. Egyptian fractions (The outstanding US mathematician Ron Graham did his PhD - with D.H. Lehmer (no less!) - on egyptian fractions; so this is a non-trivial topic, with many unsolved problems, e.g.: the Erdös-Strauss conjecture, or the odd greedy algorithm, or ...).
 Prove that every  positive fraction satisfies

  + ... +

for some distinct whole numbers , ... , . Thus, for example:

I never realised until I began this topic with my students just how fascinating it would turn out to be... Do a Google web search on egyptian fractions, and delight in the exceptional egyptian fractions site (which has many fine related links) of David Eppstein. I have prepared a substantial (67KB, output removed) Maple worksheet on Egyptian fractions , and also in html format.

12. A problem of Ducci (I first heard of this from Richard Dubsky when I visited the wonderful Hockaday School of Dallas in March 2002)...

13. Some problems based on a 1989 paper of mine, A Remark on Euclid's Proof of the Infinitude of Primes, American Mathematical Monthly, 339-341, Vol. 96, No. 4, April 1989. (It may be obtained by anyone with access to JSTOR, or whose university subscribes to it. If you can't access it then send me an email and I'll send you a hard copy.) A typical problem: choose any number of primes whatever, from the first one (2), up to and including any other one p (say) (it must be chosen to be at least the fourth prime). Finally choose any one of those primes - q (say) - and form the product of all the original primes (with q excluded) plus 1. Now prove that number cannot be a power of the excluded prime.
    Comments. One needs the "at least the fourth prime" (if one used only 2, 3 and 5, then 3*5 + 1 is 2⁴). The result is trivial if q = 1 (mod 4) (why?), but is not so when q = 3 (mod 4). Also I have many unpublished results when two primes are omitted: prove - for example - that 5 + 1 = 2¹*3¹ and 5*7 + 1 = 2²*3² are the only examples of 5*7*11*13*...*p + 1 = 2^m*3ⁿ. 
    Serious number theorists might be interested to note that none of these results are consequences of the celebrated abc conjecture, though they appear as though they ought to be.

14. Prove that the number can be expressed as the product of no less than n prime factors (not necessarily different). 
     I first saw that (expressed as a) problem in the Entrance Examinations for the Independent University of Moscow, Notices of the American Mathematical Society, February 1993, Vol. 40, N0. 2, page 138. (Of course anyone who knows about Fermat numbers will be immediately amused by that problem...)

I will add more when time allows...

Recommended reading list 

Kurchak J., Hungarian Problem Books 1 and 2 (Eötvös Competitions), 1984-1905 and 1906-1928, Mathematical Association of America, 1963. 

Greitzer S.L. (Compiler and Solver), International Mathematical Olympiads, 1959-77, Mathematical Association of America, 1978.

Klamkin M.S. (Compiler and Solver), International Mathematical Olympiads (and 40 supplementary Problems), 1978-85, Mathematical Association of America, 1986.

Yaglom A.M. and Yaglom I.M., Challenging Mathematical Problems, Holden-Day.  1967.