MathDB

4

Part of 2005 Bundeswettbewerb Mathematik

Problems(2)

finite set of integers can be arranged without intersection

Source: folklore

12/29/2004
Prove that each finite set of integers can be arranged without intersection.
invariantinductioncombinatorics proposedcombinatorics
Self-intersections of closed broken lines

Source: German Mathematical Competition BWM 2005, 2nd round, problem 4

9/1/2005
For any integer n≥3n\geq 3, let A(n)A\left(n\right) denote the maximal number of self-intersections a closed broken line P1P2...PnP1P_1P_2...P_nP_1 can have; hereby, we assume that no three vertices of the broken line P1P2...PnP1P_1P_2...P_nP_1 are collinear. Prove that (a) if n is odd, then A(n)=n(n−3)2A\left(n\right)=\frac{n\left(n-3\right)}{2}; (b) if n is even, then A(n)=n(n−4)2+1A\left(n\right)=\frac{n\left(n-4\right)}{2}+1. Note. A self-intersection of a broken line is a (non-ordered) pair of two distinct non-adjacent segments of the broken line which have a common point.
combinatorics proposedcombinatorics