There are $100$ points on the circumference of a circle, arbitrarily labelled by $1,2,\ldots,100$. For each three points, call their triangle clockwise if the increasing order of them is in clockwise order. Prove that it is impossible to have exactly $2017$ clockwise triangles.
Problem
Source: 2017 Iran MO 3rd round , second combinatorics exam P1
Tags: Iran, combinatorics
13.09.2017 03:26
First, note that any group of $4$ points must have an even number (0,2, or 4) of clockwise triangles among them. For a group of $4$ points $\text{Group}_i$, let $f(\text{Group}_i)$ be the number of clockwise triangles that group contains. Since each triangle is included in exactly $97$ groups of $4$ points, the total number of clockwise triangles must be $$\frac{\sum_{i} f(\text{Group}_i)}{97}$$Since the numerator of this fraction is even and the denominator is odd, the number of clockwise triangles must be even. Thus there can not be exactly 2017 clockwise triangles.
13.09.2017 06:10
Switching two adjacent labels changes the orientation of exactly 98 triangles, so the parity of clockwise triangles is invariant under such a switch. By repeatedly performing switches we may arrive at the labelling with 1, ..., 100 in counterclockwise order, which has no clockwise triangles. Thus the number of clockwise triangles is always even; in particular, it can't be 2017.
16.10.2018 17:18
Let $C(i)$ be the number of the triangle including $i$ as maximal labelled number for any arrangement. When $(a_{1},\cdots,a_{i-1})$ is the permutation of smaller number than $i$ in clockwise, $C(i)$ equals to the number of pairs $(a_{k},a_{l})$ satisfying $a_{k}<a_{l}$$(k<l)$, which is called "Good pair". So $C(i)+A(i)=\binom{i-1}{2}$ holds when $A(i)$ is the anti-clockwise triangle including $i$ as maximal. Because $\binom{i-1}{2}$ is odd when $i\equiv0,3\pmod{4}$, it's sufficient to show that $C(4k+3)\equiv C(4k+4)\pmod{2}$. Suppose that $4k+4$ lies between $a_{i}$ and $a_{i+1}$ for arrangement $(a_{1},\cdots,a_{4k+2})$ consisting of numbers smaller than $4k+3$ in clockwise. There are $x$ good pairs in term $(a_{1},\cdots,a_{i})$, $y$ pairs in $(a_{i+1},\cdots,a_{4k+2})$, and $z$ between them, So $C(4k+3)=x+y+z$. Now we count clockwise triangles from $4k+4$. Considering permutation $(b_{1},\cdots,b_{4k+3})$ from $4k+4$, it's identical to $(a_{i+1},\cdots\,a_{4k+2},4k+3,a_{1},\cdots,a_{i})$ Now we get $C(4k+4)=x+y-z+(4k+2-i)(i+1)$ as desired. There are $50$ pairs such as $(4k+3,4k+4)$ in given range so that $\sum C(i)$ must be even.
14.10.2024 18:15
62861 wrote: Switching two adjacent labels changes the orientation of exactly 98 triangles, so the parity of clockwise triangles is invariant under such a switch. By repeatedly performing switches we may arrive at the labelling with 1, ..., 100 in counterclockwise order, which has no clockwise triangles. Thus the number of clockwise triangles is always even; in particular, it can't be 2017. Can you kindly explain how you get exactly 98 triangles? Like if you swap $A, B$, then for every other $X$ (of 98 vertices), $\triangle XAB$ orientation changes. But when we change the position of $A$, then for some triangle of the form $\triangle X_0 A X_1$ where $X_0, X_1 \neq B$, it might change its orientation.
15.10.2024 14:09
\bump thread