A regular polygon of $ n$ sides ($ n\geq3$) has its vertex numbered from 1 to $ n$. One draws all the diagonals of the polygon. Show that if $ n$ is odd, it is possible to assign to each side and to each diagonal an integer number between 1 and $ n$, such that the next two conditions are simultaneously satisfied: (a) The number assigned to each side or diagonal is different to the number assigned to any of the vertices that is endpoint of it. (b) For each vertex, all the sides and diagonals that have it as an endpoint, have different number assigned.
Problem
Source: Spanish Communities
Tags: modular arithmetic, combinatorics unsolved, combinatorics
grobber
14.05.2006 18:53
Label each edge with endpoints $i,j\in\overline{1,n-1}$ with the number in $\overline{1,n}$ congruent to $i+j\pmod n$. Now for each $i\in\overline{1,n-1}$ all numbers in $\overline{1,n}$ appear on edges adjacent to $i$ except for one, which is different from $n$ (otherwise we'd have $2i\equiv 0\pmod n\Rightarrow i\equiv 0\pmod n$, contradiction; the implication is a consequence of the fact that $n$ is odd). Label the edge $in$ with this number. This is the labeling we're looking for.
RMACR7LP
21.12.2017 06:13
This is a little hard to explain, so it might be a little long. (For the sake of explanation I present the case when $n=11$ while detailing the solution). WLOG suppose all numbers are positioned clockwise ( if not then just relabel the numbers). Let us assign to every edge the number corresponding to the vertex opposite to it ( we can guarantee there is one since $n$ is odd) (see figure 1). Now pick a vertex, say 1, draw diagonals to the endpoints of the opposite edge, we will call these diagonals "main diagonals". As you can see, we end up with two symmetric shapes , each of which has $n$ numbers on it, specifically; $1, 2, 3, 4,..., n$ and there will be a "middle" or "pivot" number on each side, in our example 9 and 4 are pivot numbers(Remark: The pivot number could be either on an edge or a vertex), and that will be the assigned number to the main diagonal nearest to it. Now if you draw all diagonals from vertex 1, there will always be a pivot number for each diagonal (this because of the parity of $n$) and that's gonna be the one you'll assign to it (See figure 2). Finally, to see that every diagonal connected to 1 is different, notice by symmetry on our pick of the numbers of the edges that the endpoint (different from 1) of any diagonal is counted as an edge on the other shape formed by the other main diagonal i.e. the other symmetrical half, thus there can't be two diagonals with the same number.
Attachments:
