tokens are to be placed on the squares of a board such that no 4 tokens be the vertices of a rectangle with sides parallel to the sides of the board. Find the greatest value of for which this is possible.
Solution
Let be the set of the positions of the tokens in the th line of the board, . The problem is equivalent to finding such that for and is maximum.
Let be . The subsets of with 2 elements must not be contained in any other . Hence
By Cauchy's inequality,
The equality holds if and only if 5 of the 's equal 4 and the other 5 equal 3. In this case, and hence each subset of with 2 elements should be in exactly one .
Therefore if it were possible to construct an instance with 35 tokens, each element of would either be in 3 subsets with 4 elements or
in 1 subset with 4 elements and 3 subsets with 3 elements. Since there are 5 subsets with 4 elements, there must be elements which belong to 3 subsets with 4 elements. We may thus suppose wlog that , , . However any other subset with 4 elements would be contained in and therefore its intersection with one of , or would have at least 2 elements. We conclude that it is impossible to have .
On the other hand, there exist instances with 34 tokens: