Let \(n \ge 3\) be an integer, and consider a circle with \(n + 1\) equally spaced points marked on it. Consider all labellings of these points with the numbers \(0, 1, ... , n\) such that each label is used exactly once; two such labellings are considered to be the same if one can be obtained from the other by a rotation of the circle. A labelling is called beautiful if, for any four labels \(a\lt b\lt c\lt d\) with \(a + d = b + c\) the chord joining the points labelled \(a\) and \(d\) does not intersect the chord joining the points labelled \(b\) and \(c\).
Let \(M\) be the number of beautiful labelings, and let N be the number of ordered pairs \((x, y)\) of positive integers such that \(x + y \le n\) and \(gcd(x, y) = 1\). Prove that \(M = N + 1.\)
=============
Proof:
In the proof when necessary we use a sequence starting with \(0\) to represent a labelling.
Terminology:
Since we mainly rely on Mathematical Induction, denote \(S_n\) as the set of beautiful labellings described above. We say \(p\in S_{n-1}\) is extendable if there exists \(q\in S_n\) such that the latter is obtained by inserting \(n\) to the former.
A \(k-\)chord is a chord with end points summing up to \(k\). By saying \(q\) is \(k-\)symmetric we mean all its \(k-\)chords are parallel to each other.
When a beautiful labelling \(p\in S_n\) is \(n-\)symmetric, which we will prove is always the case, its axis is the line perpendicular to all \(n-\) chords in \(p\). Its pole is the intersection of the axis and the circle that has no mark, i.e. \(p\) has \(1\) pole if \(n\) is even and \(2\) otherwise.
We will have two inductions, where all initial conditions are easy to verify and therefore omitted below.
With Induction I we prove the followings.
(1) All beautiful labellings in \(S_n\) are \(n-\)symmetric and therefore have axis.
(2) All beautiful labellings could be extended in either \(1\) or \(2\) ways.
We will use (1p) to denote induction hypothesis of (1), and so on.
Induction I:
We start with some \(p\in S_{n-2}\) with numbers ranging from \(1\) to \(n-1\), and try to insert \(n\) and \(0\). By (2p) there is \(1\) or \(2\) places that we could insert \(n\), which we call \(s_1,s_2\) though \(s_2\) may not exist. If we flip every number \(k\in p\) to \(n-k\) to obtain \(p'\), we are equivalently finding place in \(p\) to insert \(0\), meaning that there is also \(1\) or \(2\) places to put \(0\), i.e. \(s'_1,s'_2\). Because of (1p) and the relation between \(p\) and \(p'\), \(s_i\) and \(s'_i\) are symmetric with respect to the axis of \(p\) for \(1\leq i\leq 2\).
This tells us a lot. We only need to further check \(n-\)chord, because there is no way that \(0+b=n+d\). So the only possible insertions are \(s_i\) together with \(s'_i\) for \(1\leq i\leq 2\) if they exist. Note that inserting \(s_1\) and \(s'_2\) will introduce a new \(n-\)chord that crosses existing ones. This establishes (1) and (2).
Induction II:
We will show that the number of cases where we can extend in \(2\) ways to obtain a beautiful labelling in \(S_n\) is equal to the number of ordered pairs \((x,y)\) such that \(x+y=n\) where \(x\) and \(y\) are positive integers and \(gcd(x,y)=1\).
When there are \(2\) ways to extend:
It happens if and only if we can insert a new number to the pole of \(p\in S_{n-2}\). After adding both \(0\) and \(n\) at the same pole, suppose they are immediately surrounded by \(x\) and \(y=n-x\). We will prove that the necessary and sufficient condition is \(gcd(x,n)=1\). Note that \(gcd(x,n)=1\) if and only if \(gcd(x,y)=1\). Let the sequence be \(0,n,x,\ldots,y\).
If \(gcd(x,n)\neq1\), then \(x\neq1\) and \(x\neq n-1\). Due to number \(1\) and \((n+1)-\)chord, \(x+1\) comes somewhere after \(1\). Similarly \((2x+1 \pmod{n})\) is somewhere after \(x+1\), etc. until we hit \(y+1\) because we will never see any of \(\{0, n, x, y\}\). Now \(\{x, y, x+1, y+1\}\) produce \(2\) crossing \((n-1)-\)chords.
If \(gcd(x,n)=1\), following the same process we get \(0,n,h_1,h_2,\ldots,h_{n-1}\) where \(h_k\equiv kx\pmod{n}\) for \(1\leq k\leq n-1\). We want to show this sequence fully characterized by \(x\) is beautiful.
Clearly \(n-\)chords are all parallel and do not cross, so we can merge \(n\) and \(0\) such that it is \(n\) when considering \(k-\)chord with \(k\gt n\), and \(0\) if \(k\lt n\). Since \(gcd(x,n)=1\), \(x\) has a unique multiplicative inverse modulo \(n\), i.e. \(x'\in [1,n-1]\) such that \(xx'\equiv 1\pmod{n}\). A \(k-\)chord has endpoints \(ix\pmod{n}\) and
\(\left(ix\pmod{n}\right)+\left(jx\pmod{n}\right)=k\), implying
\((i+j)x\equiv k\pmod{n}\), i.e.
\((i+j)\equiv kx'\pmod{n}\)
A \(k-\)chord then corresponds to a \(\left(kx' \pmod{n}\right)-\)chord in labelling \(0,1,2,\ldots,n-1\), which is beautiful.
Q.E.D.
No comments:
Post a Comment