Olympiad Maths Prep

Library / /30 of 45

Combinatorics Difficulty 6.5 National olympiad Prove it Ukraine

For a natural number n2n \ge 2, consider an n×nn \times n board. Let n2n^2 points denote the centers of each of the 1×11 \times 1 squares on this board. What is the largest number of these points that can be marked in such a way that no three marked points form the vertices of a right triangle?
*(Mykhailo Shtandenko)*

Solution

We will show that there is an example where the marked number of points satisfies the conditions of the problem. For this, we will denote the centers of all the cells in the first row and the first column, except for the center of the cell at the intersection of the first row and the first column (see Fig. 3). By simple enumeration, it is easy to see that no three marked points are vertices of a right triangle.

Suppose that this is not the maximum possible value for the number of marked points, i.e., it is possible to mark 2n12n-1 centers of the marked centers in such a way that no three of them form the vertices of a right triangle. It follows that for each marked point, this is the only marked point in the row or column with this point. Let there be a1,a2,...,ana_1, a_2, ..., a_n marked points in the columns respectively. If ai>1a_i > 1 for some ii, then for each of the marked points in the ii-th column, this point is the only one in its row, otherwise a triangular rectangle will be formed. Therefore, the total number of such points for which ai>1a_i > 1 is no more than nn — the total number of rows. But if there are exactly nn of these points, then the total number of marked points is also nn, which does not exceed 2n22n-2. Otherwise, the sum of all aia_i greater than one does not exceed n1n-1. On the other hand, the sum of all aia_i that are equal to one is also no more than nn. If there are exactly nn of these points, then again all the marked points are nn, which does not exceed 2n22n-2. Thus, the number of both types of marked points is no more than n1n-1, and therefore their total number is no more than 2n22n-2. Thus, there cannot be more marked points than this value.

Figure 1
Fig. 3

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.