Find the greatest positive integer $m$, such that one of the $4$ letters $C,G,M,O$ can be placed in each cell of a table with $m$ rows and $8$ columns, and has the following property: For any two distinct rows in the table, there exists at most one column, such that the entries of these two rows in such a column are the same letter.
Problem
Source: CGMO 2016 Q6
Tags: combinatorics
InCtrl
05.03.2017 22:50
For the sake of convenience let the letters be $A,B,C,D$. Let $a_i$ be the number of letters $a$ in row $i$, $i$ ranges from $1$ to $m$. Similarly define $b_i,c_i$ and $d_i$. The given condition means that there is no mono-lettered rectangle on the board.
Let $S_a=\sum a_i$ and similarly for $S_b,S_c, S_d$.
Counting rows, this means that $\sum\dbinom{a_i}{2}\le \dbinom{8}{2}$, otherwise there would be a rectangle by pigeonhole. By Jensen, we have the inequality $\sum \dbinom{a_i}{2}\ge m\dbinom{\frac{S_a}{m}}{2}$. Combining this with the previous inequality yields
$$m\left(\frac{S_a}{m}\right)\left(\frac{S_a}{m}-1\right)\le 56\iff$$$$S_a^2-mS_a\le 56m$$.
Adding similar inequalities for $b,c,d$ yields
$$S_a^2+S_b^2+S_c^2+S_d^2-m(S_a+S_b+S_c+S_d)\le 224m\iff$$$$S_a^2+S_b^2+S_c^2+S_d^2-m\times 8m\le 224m$$.
By Cauchy Schwarz, $(1+1+1+1)(S_a^2+S_b^2+S_c^2+S_d^2)\ge (S_a+S_b+S_c+S_d)^2\iff (S_a^2+S_b^2+S_c^2+S_d^2) \ge 16m^2$. Our previous inequality becomes
$$16m^2-8m^2\le 224 m\iff m\le \boxed{28}$$.
The construction has two of each letter in each row and is rather standard.
edit: misread the problem
Number1
10.03.2017 23:53
Say $c_i$, $g_i$, $m_i$ and $o_i$ are the numbers of $C,G,M$ and $O$ in $i-th$ column respectively. Then for each $i\in \{1,2,...8\}$ we have: $ c_i+g_i+m_i+o_i = m$ The pair of rows $\{R_i, R_j\}$ connect with $k$, if the rows mach in $k-th$ column. Then the degree $r_{i,j}$ of each pair is at most 1 and the degree of $k$ is $d_k$: $$ d_k = {c_k\choose 2} + {g_k\choose 2} + {m_k\choose 2} + {o_k\choose 2}\geq {{1\over 4} m^2-m\over 2}$$By double counting we have $$ \sum _{\{i,j\}} r_{i,j} = \sum _{k=1}^8 d_k \;\;\;\;\;\;\;\;(*)$$and thus $${m\choose 2} \geq 8{{1\over 4} m^2-m\over 2}\;\;\; \Longrightarrow \;\;\; m\leq 7$$ If $m=7$ then $d_k \geq 3{2\choose 2} +1{1\choose 2} = 3$ and thus, by $(*)$ we have ${7\choose 2} \geq 8\cdot 3$ and we have a contradiction. If $m=6$ then $d_k \geq 2{2\choose 2} +2{1\choose 2} = 2$ and thus, by $(*)$ we have ${6\choose 2} \geq 8\cdot 2$ and we have a contradiction. So $m\leq 5$ and a configuration for $m=5$ is not difficult to find.
Number1
11.03.2017 01:00
Another prove that $m$ is less then $6$. Suppose we have $6$ rows. Then in each column we have at least two pairs of cells with the same letter. Thus we have at least $16$ pairs in $8$ columns. But in a set $\{1,2,3,4,5,6\}$ we have at most $15$ pairs. Thus by a pigeonhole principle at least one pair repeats and then we have two rows which match in two columns. So we have a contradiction and thus $m\leq 5$.
InCtrl
11.03.2017 02:50
@above it appears that i have misread the problem to mean that there are no mono-coloured rectangles. instead it should rather be "2-colour" rectangles, in which case your solution is correct and mine is wrong.
primesarespecial
19.10.2021 14:21
Cute. Connect two cells in a column by an arrow if they contain the same letter. We claim that the greatest number of rows is $5$. If $m=6$,then we see that that every column contains at least $2$ arrows. Thus the no. of arrows is at least $16$. Whereas by the condition ,it is atmost $\binom {6}{2} =15$, a contradiction. For $m=5$,the construction is easy to get. An example $(CGMOC),(GOCOM),(COMGG),(MMOCG),(OGCMC),(OCMCG),(MGCMO),(MGOOC)$, where () is a column.