Label the vertices of a regular n-gon from 1 to n > 3. Draw all the diagonals. Show that if n is odd then we can label each side and diagonal with a number from 1 to n different from the labels of its endpoints so that at each vertex the sides and diagonals all have different labels.
Solution
Labeling the diagonal/side between i and j as i+j (reduced if necessary mod n) almost works. The labels for all the lines at a given vertex will be different. But the line between i and n will have label i, the same as one endpoint. However, we are not using the label 2i for the lines from vertex i. So for the line between i and n we use 2i instead of i+n. The only points that need checking are (1) whether a line from i to n has a label different from n, and (2) whether all the lines at n have different labels. Both points are ok because n is odd.
© John Scholes
jscholes@kalva.demon.co.uk
9 Sep 2002