Letters in grid

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Letters in grid

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: CGMO 2016 Q6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

178 posts

#1 h Aug 14, 2016, 9:34 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

871 posts

InCtrl

#2 h Mar 5, 2017, 7:50 PM • 3 Y

Y by laegolas, Adventure10, Mango247

Solution

edit: misread the problem

This post has been edited 3 times. Last edited by InCtrl, Mar 10, 2017, 11:50 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

355 posts

#4 h Mar 10, 2017, 8:53 PM • 2 Y

Y by Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by Number1, Mar 11, 2017, 7:32 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

355 posts

#5 h Mar 10, 2017, 10:00 PM • 1 Y

Y by Adventure10

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$ .

This post has been edited 1 time. Last edited by Number1, Mar 11, 2017, 8:02 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

871 posts

InCtrl

#6 h Mar 10, 2017, 11:50 PM • 1 Y

Y by Adventure10

@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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

primesarespecial

364 posts

primesarespecial

#7 h Oct 19, 2021, 11:21 AM

Y by

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.

This post has been edited 1 time. Last edited by primesarespecial, Oct 19, 2021, 11:26 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

201 posts

#8 h Apr 12, 2025, 3:07 AM

Y by

We claim that $m=5$ .

Let $T$ denote the number of unordered pairs of squares of the same letter in the same column. Then we know from condition that $\binom{m}{2} \geq T$
Let $x_i,y_i,w_i,z_i$ be the number of squares containing $C, G, M, O$ in column $i$ respectively. Note that $x_i+y_i+w_i+z_i=m$ . We have $T = \sum_{i=1}^8 \binom{x_i}{2}+\binom{y_i}{2}+\binom{w_i}{2}+\binom{z_i}{2} \geq 8(4) \binom{\frac{m}{4}}{2}=8\frac{m(\frac{m}{4}-1)}{2}=m(m-4)$
Thus $\frac{m(m-1)}{2} \geq m(m-4) \implies m^2-m \geq 2m^2-8m \implies m^2 \leq 7m \implies m \leq 7$
Note that if $m=7$ , at least three pairs of rows must have the same letter in every column, so $3(8) =24 \geq \binom{7}{2}=21$ implies that there exists a pair that collides at more than one column by pigeonhole. Similarly, if $m=6$ at least two pairs of rows must collide in every column, so $2(8) =16 > \binom{6}{2}=15$ means it is impossible by pigeonhole as well. This condition is not broken at $m=5$ and it is achievable with this construction
$\begin{matrix} C&M & M &G & C & C & C &G \\ C & C &O& M&G&G&G&C\\G&C&C&O&C&M&M&M\\M&G&C&C&M&C&O&C\\O&O&G&C&O&O&C&O\end{matrix}$

This post has been edited 1 time. Last edited by de-Kirschbaum, Apr 12, 2025, 3:07 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a