Maths Olympiad Prep

Library / /44 of 97

Combinatorics Difficulty 7.9 National olympiad, round 2 Find the answer

Let S={(x,y)x=1,2,,1993,y=1,2,3,4}S = \{(x,y) | x = 1, 2, \ldots, 1993, y = 1, 2, 3, 4\}. If TST \subset S and there aren't any squares in T.T. Find the maximum possible value of T.|T|. The squares in T use points in S as vertices.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let S={(x,y)x=1,2,,1993,y=1,2,3,4} S = \{(x,y) \mid x = 1, 2, \ldots, 1993, y = 1, 2, 3, 4\} . We aim to find the maximum possible value of T |T| for a subset TS T \subset S such that there are no squares in T T .

To solve this, we need to ensure that no four points in T T form the vertices of a square. The key observation is that for any square in S S , we can have at most 3 of its vertices in T T . This gives a weak upper bound:
T34S. |T| \leq \frac{3}{4} |S|.

We will use a more refined approach to maximize T |T| . Consider the columns of S S . If a column C C contains all its elements in T T , then the adjacent columns can have at most 2 elements in T T to avoid forming squares. Thus, it is more efficient to avoid having all elements of any column in T T .

We can choose 3 elements from each column in T T without forming squares. To achieve this, we can use a pattern where each set of 4 adjacent columns has distinct permutations of 3 elements in T T and 1 element not in T T . This pattern avoids forming squares and maximizes the number of elements in T T .

For example, consider the following arrangement for 4 columns:
\begin{array}{cccc} \bullet & \circ & \circ & \circ \\ \circ & \circ & \bullet & \circ \\ \circ & \bullet & \circ & \circ \\ \circ & \circ & \circ & \bullet \\ \end{array}
Here, \bullet represents an element in T T and \circ represents an element not in T T .

This pattern can be repeated, with a separating column containing only 1 element in T T to avoid forming squares. Given that there are 1993 columns, we can divide them into groups of 5 columns (4 columns with 3 elements each and 1 separating column with 1 element).

Thus, we have:
1993=5398+3. 1993 = 5 \cdot 398 + 3.

The maximum number of elements in T T is:
39813+33=5183. 398 \cdot 13 + 3 \cdot 3 = 5183.

Therefore, the maximum possible value of T |T| is:
5183. \boxed{5183}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.