blog/combinatorics-shortlist

Cosmin Negruseri
10 decembrie 2012

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
print ‘*’
How many stars will be printed
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)