blog/combinatorics-shortlist

Combinatorics shortlist

1. Given n points on a circle. Join all possible nC2 cords. What’s the maximum number of triangles you can see. ex?
2. Given n lines what’s the max number of regions the plane can be split into. (Same problem for n circles, n planes, n spheres)
3. What’s the maximum product you can obtain from a set of positive natural numbers that sum up to n.
4. How many ways can you tile a 3xn rectangle with dominoes.
5.
  for i1 = 1 to n
    for i2 = i0 to n
      for i3 = i1 to n
        ….
         for ik = ik - 1 to  n

Problem short lists are often used in math camps to cover some subject by going through a bunch of tricks. I've thought of doing the same for programming contests. My first list is related to combinatorics.
 
1. (olimpiada online 2001) Given n points on a circle. Join all possible n(n-1)/2 cords. 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).
2. (agora scholarships) 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 = 4 we can get 7 regions.
3. What is the maximum product you can obtain from a set of positive natural numbers that sum up to n.
4. (romanian national olympiad, 10th grade 2000) How many ways can you tile a 3xn rectangle with dominoes.
5.
[code]
  for i[1] = 1 to n
    for i[2] = i[1] to n
      for i[3] = i[2] to n
        …
         for i[k] = i[k - 1] to  n

             print ‘*’

How many stars will be printed

[/code]
How many stars will be printed for a given n and k.

6. How many ways can k rooks on a nxn chessboard so they don’t attack eachother.
7. How many permutations of length n have no fixed points. A fixed point for a permutation p is p(i) = i
8. ()(())