Let $A_1A_2...A_{101}$ be a regular $101$-gon, and colour every vertex red or blue. Let $N$ be the number of obtuse triangles satisfying the following: The three vertices of the triangle must be vertices of the $101$-gon, both the vertices with acute angles have the same colour, and the vertex with obtuse angle have different colour. $(1)$ Find the largest possible value of $N$. $(2)$ Find the number of ways to colour the vertices such that maximum $N$ is acheived. (Two colourings a different if for some $A_i$ the colours are different on the two colouring schemes).
Problem
Source: 2014 China TST 3 Day 1 Q2
Tags: combinatorics proposed, combinatorics
06.04.2014 20:06
Please clarify if the triangle has to be an obtuse triangle.
07.04.2014 01:56
Yes, please edit the problem: Let $N$ be the number of obtuse triangles satisfying the following: Done. -mod
10.02.2017 01:29
This is a nasty problem. The idea is to label each vertex $x_i = 1$ if the $i$th vertex is red, and $-1$ if the $i$th vertex is blue. The answer will be \[ \sum_{jik obtuse} \frac{(1 + x_i)(1 - x_j)(1 - x_k)}{8} + \frac{(1 - x_i)(1 + x_j)(1 + x_k)}{8} = \sum_{jik obtuse} \frac{(x_jx_k - x_ix_j - x_ix_k)}{4} + \frac{1}{4} \] We will now count the number of times each vertex appears. The contribution from the second term is equal to $\dfrac{(101)(49)(50)}{8}$. The contribution from the first part is more interesting. Let $s_j = \sum_{i = 1}^{101} x_ix_{i+j}$, where indices are taken modulo $101$. Then one can see that the sum is equal to \[ \frac{\sum_{i = 1}^{50} (3i - 101)s_i}{4} \] It suffices to minimize the expresion \[ L = \sum_{i = 1}^{50} (3i - 101)s_i \]Define also the expression \[ M = \sum_{i = 1}^{50} s_i \]and the expression \[ S = \sum_{i = 1}^{101} x_i \]and the expresion \[ K = \sum_{i = 1}^{101} (\sum_{j = 1}^{51} (x_{i + j}))^2 \] One can show that \[ K = 51(101) + 2\sum_{i = 1}^{50} (s_i)*(51 - i) \] Now observe that \[ \frac{3}{2}(K - 51(101)) + L = 52M = 26(S^2 - 101) \] Therefore, it is sufficient to mininize the quantity $26S^2 - \frac{3}{2}K$. It can be seen that \[K \ge \frac{51^2}{101} S^2 \]by say, Titu's Lemma. Therefore, \[ 26S^2 - \frac{3}{2}K \le (26 - \frac{51^2*3}{101*2})S^2 \le (-12.5)S^2 \] At this point observe that the substitution of $(1, 1, -1, 1, \cdots)$ gives $S = 1$ and $K = 101$, so $26S^2 - \frac{3}{2}K$ has a maximum value of at least $-125.5$. Therefore, we can conclude that $26S^2 - \frac{3}{2}K$ can only be maximized at $|S| \le 3$. Therefore, suppose for contradiction that $S = 3$ is when the function is maximized. In this situation, $K$ is the sum of $101$ odd squares, so one can show that since the sum of these squares is $153$, $K \ge 26(3^2) + 75 = 309$. But then $26S^2 - \frac{3}{2}K \le -229.5$, so therefore the expression is minimized when $S = \pm 1$. WLOG $S = 1$, since one can just take the complement of a configuration. $K$ is minimized at $101$ when each of the squares are one. Thus the max value of $26S^2 - \frac{3}{2}K$ is just $-125.5$, and then \[L = 26S^2 - 26(101) - \frac{3}{2}K + \frac{153}{2}(101) = -125.5 - 26(101) + \frac{(153)(101)}{2} = 4975 \]The answer is $\frac{4975}{4} + \frac{(101)(49)(50)}{8} = 32175$. Now for part 2. We basically want to find the number of ways such that all $s_i = x_{i} + x_{i + 1} \cdots + x_{i + 50}$ are equal to $\pm 1$, and the sum of all $x_i$ is $1$. The sum of these quantities is $51$. Therefore, sincer there are $101$ $s_i$, there are $76$ of the $s_i$ equal to one, and $25$ of the $s_i$ equal to $-1$. Now I claim that given $s_i$, we can uniquely determine each of the $x_i$. The proof is simple. I claim that the determinant of the circulant matrix with $51$ consecutive $1$'s in each row and zeroes elsewhere is nonzero. This is well known to equal the product of the quantities $\sum_{i = 0}^{50} \omega^{ij}$ for integers $j$, if $\omega$ is a primitive $101$th root of unity. Since the minimal polynomial of a primitive root of unity is $x^{100} + x^{99} + \cdots + 1$, this is nonzero. However, it should be noted that $x_{i} = s_i + s_{i + 51} - 1$, so one needs $s_i$ and $s_{i + 51}$ to not both be $-1$. Since $51$ and $101$ are coprime, this is equivalent to asking for $101$ times the number of sets of $25$ positive integers (corresponding to the gaps) which have a sum of $76$. This will be $101\dbinom{75}{25}$. Multiply by two at the end to get $202\dbinom{75}{25}$.