Combinatorics

1. An International Food Group consists of twenty couples who meet four times a year for a meal. On each occasion, four couples meet at each of five houses. The members of the group get along very well together; nonetheless, there is always a bit of discontent during the year when some couples meet more than once! Is it possible to plan four evenings such that no two couples meet more than once? There are many problems like this. They are called combinatorial designs. Investigate others.
2. What is the fewest number of colours needed to colour any map if the rule is that no two countries with a common border can have the same colour. Who discovered this? Why is the proof interesting? What if Mars is also divided into areas so that these areas are owned by different countries on earth. They too are coloured by the same rule but the areas there must be coloured by the colour of the country they belong to. How many colours are now needed? References: [Hut], [Bal], [A&H].
3. Discover all 17 ``different'' kinds of wallpaper. (Think about how patterns on wallpaper repeat.) How is this related to the work of Escher? Discover the history of this problem. References: [Shep], [Cox], [C&C].
4. Investigate self-avoiding random walks and where they naturally occur. Reference: [Sla].
5. Investigate the creation of secret codes (ciphers). Find out where they are used (today!) and how they are used. Look at their history. Build your own using prime numbers. References: [F&K], [Bal].
6. It is easy to cover a chessboard with dominoes so that no two dominoes overlap and no square on the chessboard is uncovered. What if with one square is removed from the chessboard? (impossible - why?) What if two adjacent corners are removed? What if two opposite corners are removed? (possible or impossible?) What if any two squares are removed? What about using shapes other than dominoes (eg 3 squares joined together)? What about chessboards of different dimensions? Reference: [Gol]. See the following problem as well.
7. Polyominoes are shapes made by connecting certain numbers of equal-sized squares together. How many different ones can be made from 2 squares? from 3, from 4, from 5? Investigate the shapes that polynominoes can make. Play the ``choose-up'' Pentomino game. References: [Gol], Volume 1 of [Gard3], [Gard5].
8. Find pictures which show that ; that ; and that . How many other ways can you find to prove these identities? Is any one of them ``best''? References: [S&R], or Proofs without words, regular feature of Mathematics Magazine.