Let $n$ be a positive integer not divisible by $3$. A triangular grid of length $n$ is obtained by dissecting a regular triangle with length $n$ into $n^2$ unit regular triangles. There is an orange at each vertex of the grid, which sums up to \[\frac{(n+1)(n+2)}{2}\]oranges. A triple of oranges $A,B,C$ is good if each $AB,AC$ is some side of some unit regular triangles, and $\angle BAC = 120^{\circ}$. Each time, Yen can take away a good triple of oranges from the grid. Determine the maximum number of oranges Yen can take.
Problem
Source: 2018 Taiwan TST Round 1
Tags: combinatorics, Taiwan
31.03.2020 11:02
Why n is not divisible by himself?
31.03.2020 21:46
Bump for question in #2...
01.04.2020 05:30
Oof that's a huge huge typo... $n$ is not divisible by $3$, my bad!
07.04.2020 19:45
We claim that the answer is $\min\{\alpha, \frac{(n+1)(n+2)}{2}-3\}$ where $\alpha$ denotes Yen's maximal capacity. The bound $\alpha$ is true by definition and the construction in all situations is direct. It suffices to prove an upper bound of $\frac{(n+1)(n+2)}{2}-3$ assuming $\alpha \ge \frac{(n+1)(n+2)}{2}-3$. Note that the number of oranges he can take is divisible by $3$, and so is the total number of oranges. Thus it suffices to show that he cannot take all oranges. In fact, we claim that he cannot take all oranges on all $3$ sides. Considering adding the $120^\circ $ angles that cover the bottommost line one by one from left to right. Label the points $1,...,n+1$ in order, in each step we will add in the angle covering the point with the smallest label not yet covered. We claim that each time after one or two new angles are added, the point having the largest label among those already covered satisfies the following property: the point immediate to the right and above it is also covered. Indeed, starting from one such stage (including the initial stage) there are $2$ possible ways to put in the angle we want to add, if it does not cover the 2nd-largest-label-not-yet-covered then there is only one way to add in a second angle; otherwise we are already done. In either case our claim is true which brings a contradiction if all labels are eventually covered, so we are done.
09.04.2020 07:28
stroller wrote: We claim that the answer is $\min\{\alpha, \frac{(n+1)(n+2)}{2}-3\}$ where $\alpha$ denotes Yen's maximal capacity. The bound $\alpha$ is true by definition and the construction in all situations is direct. It suffices to prove an upper bound of $\frac{(n+1)(n+2)}{2}-3$ assuming $\alpha \ge \frac{(n+1)(n+2)}{2}-3$. Note that the number of oranges he can take is divisible by $3$, and so is the total number of oranges. Thus it suffices to show that he cannot take all oranges. In fact, we claim that he cannot take all oranges on all $3$ sides. Considering adding the $120^\circ $ angles that cover the bottommost line one by one from left to right. Label the points $1,...,n+1$ in order, in each step we will add in the angle covering the point with the smallest label not yet covered. We claim that each time after one or two new angles are added, the point having the largest label among those already covered satisfies the following property: the point immediate to the right and above it is also covered. Indeed, starting from one such stage (including the initial stage) there are $2$ possible ways to put in the angle we want to add, if it does not cover the 2nd-largest-label-not-yet-covered then there is only one way to add in a second angle; otherwise we are already done. In either case our claim is true which brings a contradiction if all labels are eventually covered, so we are done. How is the construction direct? I personally think that the construction part is nontrivial :/
10.11.2023 19:03
I think finding such construction is the harder part. Here is my solution.