Combinatorics shortlist

Cosmin Negruseri
10 decembrie 2012

Short lists are often used in math camps to cover some subject by going through a bunch of problems. I've thought of doing the same for programming contests. The first list is related to combinatorics.

Discuss the solutions in the comment section.

1. (10th grade math course) How many different strings of length 9 are there which contain 3 'a's, 3 'b's and 3 'c's.
2. How many ways are there to climb a n level staircase if at each step you can climb one or two levels.
3. (olimpiada online 2001) Given n points on a circle. Draw all possible n(n-1)/2 chords. What’s the maximum number of triangles one can see. Example: With n = 4 there are 8 triangles (4 with 3 of the 4 circle points and 4 with 2 circle points and 1 the intersection of the diagonal).
4. (⁴, agora scholarships 2001, infoarena) What is the maximum number of regions the plane can be split into by n lines. (Same problem for n circles, n planes, n spheres) Example: For n = 3 we can get 7 regions.
5. (¹) What is the maximum product for collection of natural numbers that sum up to n.
6. (¹, romanian national olympiad, 10th grade, 2000) How many ways can you tile a 3xn rectangle with dominoes.
7. (romanian IOI selection, 1999)
   for i1 = 1,n
   _for i2 = i1,n
   __for i3 = i2,n
   ____…
   _____for ik = ik - 1,n
   ______print ‘*’
   How many stars will be printed for a given n and k.
8. (⁵, acm.sgu.ru) Count the number of ways k rooks can be placed on a nxn chessboard so that they don’t attack each other.
9. (¹, romanian county olympiad, 11th grade 2000, acm.sgu.ru) Count the number of length n permutations with no fixed points. A fixed point in a permutation p is p(i) = i
10. (¹, county level olympiad, 1994) Count the number of correct bracket sequences of length 2n.
11. (10th grade math course) Count the number of paths on a grid going from 1,1 to n, m. At each step you can either increase your x coordinate or increase your y coordinate.
12. Given a permutation of numbers 1 to n, what's the minimum number of swaps one can use to get to the identity permutation.
13. Count the number of size n permutations such that p^2(i) = i for all i in {1..n}.
14. (¹, infoarena) Given a permutation p what's the minimum k so that p^k(i) = i for all i in {1..n}.
15. (romanian IOI selection 99, topcoder 2004, infoarena) Find a permutation p of n elements which maximizes k so that p^k(i) = i for all i in {1..n}.
16. (¹) 6 people are at a party. Each two persons can be either friends or enemies. Prove that there is at least a group of three mutual friends or a group of three mutual enemies.
17. (acm.sgu.ru) Count the number of circular black/white necklaces of length n. (babb is the same with bbab because the first necklace can be rotated to align with the second one)

Some math books useful for programming competition enthusiasts:
¹ Ioan Tomescu "Probleme de combinatorica si teoria grafurilor"
Every year during my highschool there was at least one problem in the national olympiad or in the IOI team selection tests from this book.
² Ioan Cuculescu "Olimpiadele Internationale de Matematica ale Elevilor"
³ E. A. Morozova, I. S. Petracov, V. A. Skvortov "Olimpiade internationale de matematica"
⁴ "Probleme de matematica traduse din revista sovietica KVANT"
⁵ A. M. Iaglom, I. M. Iaglom "Probleme neelementare tratate elementar"
⁶ Mathematics for computer science