Let . If and there aren't any squares in Find the maximum possible value of The squares in T use points in S as vertices.
Solution
Let . We aim to find the maximum possible value of for a subset such that there are no squares in .
To solve this, we need to ensure that no four points in form the vertices of a square. The key observation is that for any square in , we can have at most 3 of its vertices in . This gives a weak upper bound:
We will use a more refined approach to maximize . Consider the columns of . If a column contains all its elements in , then the adjacent columns can have at most 2 elements in to avoid forming squares. Thus, it is more efficient to avoid having all elements of any column in .
We can choose 3 elements from each column in 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 and 1 element not in . This pattern avoids forming squares and maximizes the number of elements in .
For example, consider the following arrangement for 4 columns:
Here, represents an element in and represents an element not in .
This pattern can be repeated, with a separating column containing only 1 element in 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:
The maximum number of elements in is:
Therefore, the maximum possible value of is: