Problem 1.

Let $a$ and $b$ be positive integers. The cells of an $(a+b+1) \times(a+b+1)$ grid are colored amber and bronze such that there are at least $a^2+a b-b$ amber cells and at least $b^2+a b-a$ bronze cells. Prove that it is possible to choose $a$ amber cells and $b$ bronze cells such that no two of the $a+b$ chosen cells lie in the same row or column.

Let $A$ and $B$ denote the sets of rows and columns that contain at least one amber cell and one bronze cell respectively. Let $S$ denote the set of cells in the intersection of a row in $A$ and a column in $B$. By double counting, the number of cells in $S$ is at least $a^2 + ab – b$ (since each row in $A$ has at least $a$ amber cells and each column in $B$ has at least $b$ bronze cells) and at the same time is at least $b^2 + ab – a$ (since each row in $B$ has at least $a$ bronze cells and each column in $A$ has at least $b$ amber cells).

Thus, we have $a^2 + ab – b \geq b^2 + ab – a$, which simplifies to $(a-b)(a+b-1) \geq 0$. Since $a+b-1 \geq 1$, it follows that $a \geq b$. Similarly, we can show that $b \geq a$, and hence we must have $a=b$.

Now, let us consider the $a$ rows in $A$ and the $a$ columns in $B$. We know that each row in $A$ contains at least one bronze cell, and each column in $B$ contains at least one amber cell. Thus, there are at least $a$ bronze cells in the $a$ rows, and at least $a$ amber cells in the $a$ columns.

We will now prove that it is possible to choose $a$ rows and $a$ columns such that the $a^2$ cells at their intersection are all distinct. Suppose not, and let $C$ be a set of $k$ rows and columns such that the intersection of any two of them contains a repeated cell. Note that $k \geq a+1$, since if $k \leq a$, then we can simply choose those $k$ rows and columns.

Consider the $k$ rows in $C$. Since there are only $a$ columns in $B$, there must be at least one column in $Problem 2. Let$b \geq 2$and$w \geq 2$be fixed integers, and$n=b+w$. Given are$2 b$identical black rods and$2 w$identical white rods, each of side length 1 . We assemble a regular$2 n$-gon using these rods so that parallel sides are the same color. Then, a convex$2 b$-gon$B$is formed by translating the black rods, and a convex$2 w$-gon$W$is formed by translating the white rods. An example of one way of doing the assembly when$b=3$and$w=2$is shown below, as well as the resulting polygons$B$and$W$. Prove that the difference of the areas of$B$and$W$depends only on the numbers$b$and$w$, and not on how the$2 n$-gon was assembled. First notice that the black rods and the white rods form polygons iff in the original$2 n$-gon, if a side is a color$x$, then the side that is parallel to that side in the original$2 n$-gon is also the color$x$. We can prove that the difference in areas is only affected by the values of$b$and$w$by showing that for any valid arrangement of$2 b$rods and$2 w$rods, we may switch any two adjacent black and white rods(and their “parallel pairs”), and end up with the same area difference. In the figure above (click to expand), after the switch, we can see that after removing the mutually congruent parts, we are left with two parallelograms from each color. Let$x, \alpha, y$, and$\beta$be defined as shown. Notice that if we angle chase, the sides of the other parallelogram are the same, but if the angles of the original$2 n$-gon all have measure$2 k$, the angles of the new parallelograms are$\alpha+180-2 k$and$\beta+180-2 k$, as shown. We must prove that the differences between the areas are the same. Using area formulas, the change in the difference of areas is$x \sin \alpha-y \sin \beta+y \sin (2 k-\beta)-x \sin (2 k-\alpha)$, which is equal to$x\left(\sin k\left(2 \cos ^2 k\right)-2 \sin k \cos k \cos \alpha\right)-y\left(\sin k\left(2 \cos ^2 k\right)\right)+y(\sin k \cos k \cos \beta)$, or$2 \cos k(x \sin (\alpha-k)+y \sin (k-\beta))$. Since$\cos k$is not 0 because$n \geq 3$, we are left with proving that$x \sin (\alpha-k)+y \sin (k-\beta)=0$. Now we rotate the polygon so that the vertex between the two sides that we switched is at the point$(0,0)$, the angle bisector of that vertex is$y=0$, and the black side is in the positive$y$-direction. Now think of all the sides as vectors, all pointing in the clockwise direction of the$2 n$-gon. Notice the part labeled$a$in the black polygons. We have that the vector labeled$x$is really just the sum of all of the vectors in the part labeled$a$or all the vectors in the$2 n$-gon that are in the positive$y$-direction excluding the one that was interchanged. Also notice that the angle of this vector$x$has a signed angle of$\alpha-k$with$y=0$and has length$x$-meaning that the vertical displacement of the vector$x$from$y=0$is equal to$x \sin (\alpha-k)$! Similarly, we get that the vertical displacement of the vector$y$is equivalent to$y \sin (k-\beta)$. Adding these two together, we get that$x \sin (\alpha-k)+y \sin (k-\beta)$is simply the vertical displacement of the sum of the vectors$x$and$y$. Since the sum of the vectors$x$and$y$is equivalent to the sum of the vectors in the positive half of the polygon minus the sum of the black vector that would be switched with the white vector(the leftmost vector in the positive half of the polygon) and the rightmost vector in the positive half(which is the parallel pair of the white vector that would be interchanged later), and we know that this sum happens to have a vertical displacement of 0 , along with the fact that the positive half of the polygon summed together also has a vertical displacement of 0 , we get that the total vertical displacement is 0 , meaning that$x \sin (\alpha-k)+y \sin (k-\beta)=0$, and we are done. Problem 3. Let$\mathbb{R}{>0}$be the set of all positive real numbers. Find all functions$f: \mathbb{R}{>0} \rightarrow \mathbb{R}{>0}$such that for all$x, y \in \mathbb{R}{>0}$we have $$f(x)=f(f(f(x))+y)+f(x f(y)) f(x+y) .$$ Let$P(x,y)$be the assertion$f(x)=f(f(f(x))+y)+f(xf(y))f(x+y)$. Assume$f(a)=f(b)$for some$a,b>0$. Comparing$P(a,x)$and$P(b,x)$, we get$f(f(f(a))+x)+f(ax)f(a+x)=f(f(f(b))+x)+f(bx)f(b+x)$for all$x>0$. Since$f(f(f(a)))=f(f(f(b)))$and$f(ax)f(a+x)=f(bx)f(b+x)$for all$x>0$, we get$f(f(f(a))+x)=f(f(f(b))+x)$for all$x>0$. Hence,$f(f(f(a)))=f(f(f(b)))$and$f(a)=f(b)$imply$f(x)$is periodic for all$x>M$for some$M>0$. Therefore, there exists a positive$T$such that$f(x+T)=f(x)$for all$x>0$. Moreover,$T>0$is a period of$f(x)$. From$P(x,y)$, we have$f(x)=f(f(f(x))+y)+f(xf(y))f(x+y)$for all$x,y>0$. By substituting$x\to x+T$and using$f(x+T)=f(x)$, we get $$f(x+T)=f(f(f(x+T))+y)+f((x+T)f(y))f(x+y+T)$$ Hence,$f(x)=f(f(f(x))+y)+f(xf(y))f(x+y)$and$f(x+T)=f(f(f(x))+y)+f((x+T)f(y))f(x+y)$imply that$f(x)$is periodic with period$T$. Therefore,$f(x)$is periodic for all$x>0$with a period$T$. Now, let$u$and$v$be positive numbers such that$f(u)=v$. Comparing$P(u,y)$and$P(u,y+T)$, we get $$f(v)=f(f(f(u))+y)+f(uf(y))f(u+y)=f(f(f(u))+y+T)+f(uf(y+T))f(u+y+T)=f(v)+f(uf(y+T))f(u+y+T)$$ Hence,$f(uf(y+T))f(u+y+T)=0$for all$y>0$. Since$f$is positive, we get$f(u+y+T)=0$for all$y>0$. Hence,$f(x+T)=0$for all$x>u$. But we have$f(x+T)=f(x)$for all$x>0$. Hence,$f(x)=0$for all$x>u$. Since$u$is arbitrary, we get$f(x)=0$for all$x>0$. Therefore, the only solution to the functional equation is$f(x)=0$for all$x>0\$.