Maths Olympiad Prep

Library / /107 of 520

Combinatorics Difficulty 5.8 AIME, harder Prove it

Label the vertices of a regular nn-gon from 1 to n>3n>3. Draw all the diagonals. Show that if nn is odd then we can label each side and diagonal with a number from 1 to nn 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\mathrm{i} and j\mathrm{j} as i+j\mathrm{i}+\mathrm{j} (reduced if necessary mod n\mathrm{n}) almost works. The labels for all the lines at a given vertex will be different. But the line between i and nn 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 ii and nn we use 2i2 i instead of i+ni+n. The only points that need checking are (1) whether a line from i\mathrm{i} to n\mathrm{n} has a label different from n\mathrm{n}, and (2) whether all the lines at n\mathrm{n} have different labels. Both points are ok because n\mathrm{n} is odd.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.