Combinatorics shortlist

Cosmin Negruseri
10 decembrie 2012

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 to n
for i² = i¹ to n
for i³ = i² to n
…
for i[k] = i[k - 1] to n
print ‘*’
[/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. ()(())
9. How many ways can you go from 0,0 to n, m.
non palindromes
10. black and white beads
ladder 2 steps, 1 step
11 ramsey theory 3 people all know eachother 3 people don’t know
3a 3b 3c
permutation with max cycle p
permutation with largest p, ordonarea cu nr minim de swaps
f(f(x)) = f(x)