An equilateral triangle $T$ with side $111$ is partitioned into small equilateral triangles with side $1$ using lines parallel to the sides of $T$. Every obtained point except the center of $T$ is marked. A set of marked points is called $\textit{linear}$ if the points lie on a line, parallel to a side of $T$ (among the drawn ones). In how many ways we can split the marked point into $111$ $\textit{linear}$ sets?
Problem
Source: ARO Regional stage 2024 9.9=11.9
Tags: combinatorics
Sourorange
16.02.2024 14:38
When $111$ is replaced by $3n$ The answer is exactly $3(n+1)$ I 'll give a brief idea.
For $3n$, let the number of the legal ways to split the marked points be $T_n$ .Then we consider the $3n-1$points on one edge of the big triangle $T$
If the are in different linear sets, then only 2 ways are legal. (Check it by yourself)
Otherwise, they are in the same set. Then we turn to consider another edge of $T$. If the $3n-1$ points are in different sets, there is only one legal way.(Still check it on your own).
Then we assume that $3n-1$ points of these two edges of $T$ are in exactly $2$ sets. It's easy to find that all the points on the third edge of $T$ are also in one set.
Finally we only need to deal with the "inner" points of $T$, which has $T_{n-1}$ ways according to induction hypothesis.
So $T_n=3+T_{n-1}$. We are done
NO_SQUARES
16.02.2024 23:10
Sourorange wrote: When $111$ is replaced by $3n$ The answer is exactly $3(n+1)$ I 'll give a brief idea.
For $3n$, let the number of the legal ways to split the marked points be $T_n$ .Then we consider the $3n-1$points on one edge of the big triangle $T$
If the are in different linear sets, then only 2 ways are legal. (Check it by yourself)
Otherwise, they are in the same set. Then we turn to consider another edge of $T$. If the $3n-1$ points are in different sets, there is only one legal way.(Still check it on your own).
Then we assume that $3n-1$ points of these two edges of $T$ are in exactly $2$ sets. It's easy to find that all the points on the third edge of $T$ are also in one set.
Finally we only need to deal with the "inner" points of $T$, which has $T_{n-1}$ ways according to induction hypothesis.
So $T_n=3+T_{n-1}$. We are done
You are mistaken. The right answer is $2^{4107}$. Sourorange wrote: If the are in different linear sets, then only 2 ways are legal. (Check it by yourself) For example, even this is not true, of course.