On a $ 50 \times 50$ board, the centers of several unit squares are colored black. Find the maximum number of centers that can be colored black in such a way that no three black points form a right-angled triangle.
Problem
Source: Argentina TST 2009
Tags: induction, pigeonhole principle, combinatorics unsolved, combinatorics
mszew
15.05.2009 16:03
Induction on $ m+n$ for an $ m \times n$ board with $ m,n \ge 2$ with maximum for $ f(m \times n)=m+n-2$
Base case: $ m+n=4$, $ m=n=2$
Trivial with an example painting the two diagonal squares then $ f(2 \times 2 )= 2=m+n-2$
Assume that it is true for every $ m \times n$ square with $ 4 \le m+n < k$ and $ m,n>2$
For the case of $ m+n=k$, one example with $ f(m \times n)=m+n-2$ is painting the first row and the first column without its intersection.
Suppose that there is a painting with $ f(m \times n)>m+n-2$ then by pigeonhole principle there is a column with two painted squares in row $ i$ and $ j$.
Case 1) $ i=1$, $ j=m$ then $ f(m \times n)\le 2+f((m-2) \times n)$ no more painted squares on the $ i$ or $ j$ row.
If $ m>3$ then $ m-2\ge 2$ then by induction hypothesis $ f(m \times n)\le 2+f((m-2) \times n)=2+m-2+n-2=m+n-2$ Contradiction.
If $ m=3$ then $ f(m \times n)\le 2+f(1 \times n)$
if it is painted the square of that column on the remaining row then there is no other square painted on that row, $ f(m \times n)\le 2+f(1 \times n)=2+1=3$ Contradiction.
If that square it is not painted then $ f(1 \times n) \le n-1$ then $ f(m \times n)=f(3 \times n) \le 2+n-1=1+n-2$ Contradiction.
If $ m=2$ then $ f(m \times n)=2$ no more painted squares on the $ i$ or $ j$ row. Contradiction.
Similarly for the other cases with two or three bands.
Then $ f(50 \times 50)=98$
hungnguyenvn
15.08.2010 06:00
Is it 98 ?.
Thunder365
12.01.2011 03:47
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=338084&sid=f001ffbf948e330ffdd013a6d5e4a9ed#p338084