In some of the $ 1\times1 $ squares of a square garden $ 50\times50 $ we've grown apple, pomegranate and peach trees (At most one tree in each square). We call a $ 1\times1 $ square a room and call two rooms neighbor if they have one common side. We know that a pomegranate tree has at least one apple neighbor room and a peach tree has at least one apple neighbor room and one pomegranate neighbor room. We also know that an empty room (a room in which there’s no trees) has at least one apple neighbor room and one pomegranate neighbor room and one peach neighbor room. Prove that the number of empty rooms is not greater than $ 1000. $
Problem
Source:
Tags: combinatorics proposed, combinatorics
jgnr
29.09.2010 15:34
Very nice problem Let $a,b,c,d$ be the numbers of apple trees, pomegranate trees, peach trees, and empty rooms, respectively. Each room not containing apple tree is neighbouring with at least one apple tree, if we sum over all such rooms, each apple tree is counted at most 4 times, therefore $a\ge\frac{b+c+d}4$. Since $a+b+c+d=2500$, then $b+c+d\le2000$. Similarly we have $b\ge\frac{c+d}3$ which gives $c+d\le1500$, and $c\ge\frac{d}2$ which gives $d\le1000$, as desired.
sepehrOp
05.04.2016 19:47
Assume that we have $k => 1001$ empty rooms.every peach room at maximum can be the neighbour of $2$ empty room . so we have at least $501$ peach room .now we have at least $1502$ rooms that need pomegranate room and every pomegranate room at maximum can be the neighbour of 3 rooms so we have at least $501$ rooms.now we have at least $2003$ rooms that need apple . and every apple room at maximum can be the neighbour of $4$ rooms .so we have at least $501$ apple rooms . We can realized that we have at least 2504 rooms but the table is $50*50$ which mean it has $2500$ rooms.contradiction. So $k <= 1000$