Let $n\ge 3$. $n$ Canadians and $n$ Thailanders are playing in a tournament.

Question

Canadians are only allowed to play against thailanders and vice versa. Note there doesn’t exist a quartet with 2 people from each country with both Canadians played with both Thailanders. Show that the maximum number of games is at least $\frac{3n^2}{4(n-1)^{\frac{2}{3}}}$

Answer 1

Solution for special $n$

Consider a finite projective plane of order $p$. Identify Canadians with the points and Thais with the lines, with a Canadian and a Thai playing each other if the point is on the line. This ensures that no pairs play each other.

We then have $n=p^2+p+1$ and $(p+1)(p^2+p+1)$ games. These values satisfy the required inequality with plenty to spare.

The projective plane is only known to exist for $p$ a prime power. However the given bound is so easily satisfied by the projective plane solution that it can easily be adapted for values of $n$ which cannot be expressed as $p^2+p+1$.

Proof for $3\le n\le16$

Let Canadian $i$ play Thais $i$ and $i+1$. Then the number of games is $2n$ and it is easy to check that $2n\ge \frac{3n^2}{4(n-1)^{\frac{2}{3}}}$ on this range.

Proof for $13\le n\le381$

As illustrated in the table below, we only need use the games determined by a projective plane of order $p$ where $p^2+p+1\le n$.

$$\begin{vmatrix}p&n&(1+p)(1+p+p^2)&Bound \\3&13&52&24.18\\4&21&105&44.89\\5&31&186&74.65\\7&57&456&166.47\\9&91&910&309.25\\13&183&2562&782.08\\19&381&7620&2075.18\end{vmatrix}$$

Proof for all $n$

For general $n$, let $p$ be the largest possible prime such that $1+p+p^2\le n$. Then the next largest prime is less than $2p$ (Chebyshev's Theorem) and so $n<2p+4p^2$. We are then required to prove that $$(p+1)(p^2+p+1)\ge \frac{3n^2}{4(n-1)^{\frac{2}{3}}}$$ and this is indeed true unless $p\le103$.

For such small primes we can improve the '$2p$' bound to $p+8$. The required inequality then holds except for $p\le13$ i.e for all $n$ less than $1+17+17^2=307$ and these cases have already been dealt with.

Answer 2

Equivalently, you want to find an $n\times n$ matrix of $0$'s and $1$'s which does not have any four ones which occupy the vertices of an axis-aligned rectangle, and with at least $\frac34 n^2(n-1)^{-2/3}$ ones.

Since you have the tag probabilistic-method, here is a probabilistic solution. Suppose we independently fill each entry of the $n\times n$ matrix with a one with probability $p$, and with a zero with probability $1-p$. We will specify $p$ later. The expected number of ones is $n^2p$. Then, for each instance of four ones forming a rectangle in the matrix, we turn one of the ones to a zero. The expected number of rectangles is $\binom{n}2^2 p^4$, so all in all the expected number of remaining ones is $$ E[\text{# ones}]=n^2p-\frac{n^2(n-1)^2}{4} p^4 $$ It turns out that when you choose $p=(n-1)^{-2/3}$, you exactly get $E[\text{# ones}]=\frac34 n^2 (n-1)^{-2/3}$. For that choice of $p$, we conclude there is a matrix with at least $\frac34 n^2 (n-1)^{-2/3}$ ones and no rectangles of ones.