## Task A-2.7.

In the figure, a set of 16 points is arranged along 10 highlighted directions. We say that two points of this set are connected if they belong to the same highlighted direction.

a) What is the maximum number of points that can be selected from the observed set so that there are no connected points among them?

![](https://cdn.mathpix.com/cropped/2024_05_30_9afe9556dd3f84037ce6g-13.jpg?height=297&width=297&top_left_y=1322&top_left_x=1436)

b) Determine the number of subsets of the observed set of points without connected points that have the maximum possible number of elements.
## First Solution.

Among the distinguished lines, let's name 5 mutually parallel lines as $p_{1}, p_{2}, p_{3}, p_{4},$ and $p_{5}$. Similarly, the lines in the other direction are named $q_{1}, q_{2}, q_{3}, q_{4},$ and $q_{5}$. Four points that lie on exactly one line will be called corners. Eight points that lie on the lines $p_{1}, p_{5}, q_{1},$ and $q_{5}$ will be called boundary points. The remaining four points will be called central points.

Consider the lines $p_{1}, p_{2}, p_{3}, p_{4},$ and $p_{5}$. On these lines, at most 5 points can be selected, because otherwise, there would be at least two selected points on the same line. On these 5 lines, there are 2 (corner) points, but these two corner points lie on the same line $q_{3}$, so we can select at most one of these two points. Therefore, the maximum number of points among which there are no connected points is less than or equal to 6.

We will prove that this number is equal to 6 and determine the number of ways to select such points. Note that to ensure that among the six selected points there are no connected points, respecting the arguments at the beginning, one must be located on each of the 5 parallel lines $p_{1}, p_{2}, p_{3}, p_{4},$ and $p_{5}$, and one of these points must be a corner point.

A corner point that does not lie on any of the lines $p_{i}$ can be selected in two ways.

Consider the lines $p_{1}$ and $p_{5}$. We have two choices for the point on the line $p_{1}$. Each of these points lies on the same line as one of the two points on the line $p_{5}$. Therefore, after selecting a point on the line $p_{1}$, the point on the line $p_{5}$ is uniquely determined.

Consider the lines $p_{2}$ and $p_{4}$. The selected corner point lies on the line $q_{3}$, so we cannot select the central points on these lines.

Therefore, we again have only two choices for the point on the line $p_{2}$. Analogously to the previous case, depending on the choice of this point, the point on the line $p_{4}$ will be uniquely determined.

Finally, on the line $p_{3}$, we cannot select the central point because it would be connected to the points we selected on the lines $p_{1}$ and $p_{5}$.

Therefore, we can only select one of the two corner points (in two ways).

The total number of subsets is the product of all possible choices, and it is $2^{4}=16$.

1 point