AoPS - Problem

Source: Iran 3rd round 2014 - Combinatorics exam problem 5

Tags: geometry, geometric transformation, rotation, combinatorics unsolved, combinatorics

TheOverlord

27.09.2014 19:48

An $n$-mino is a connected figure made by connecting $n$ $1 \times 1 $ squares. Two polyminos are the same if moving the first we can reach the second. For a polymino $P$ ,let $|P|$ be the number of $1 \times 1$ squares in it and $\partial P$ be number of squares out of $P$ such that each of the squares have at least on edge in common with a square from $P$. (a) Prove that for every $x \in (0,1)$:\[\sum_P x^{|P|}(1-x)^{\partial P}=1\] The sum is on all different polyminos. (b) Prove that for every polymino $P$, $\partial P \leq 2|P|+2$ (c) Prove that the number of $n$-minos is less than $6.75^n$. Proposed by Kasra Alishahi

There's an error in the problem (a). Pick one cell and denote it $A$ on the infinite square grid. For each cell, we will color it red with probability $0<x<1$. Except for probability zero, $A$ is contained in some red polymino or $A$ is not colored. When A is contained in polymino $P$ and the probability for that is precisely $x^{|P|}(1-x)^{\partial P}$. Therefore it must be strictly less than 1. To correct this, I recommend you to solve (a) Prove that for every $x \in (0,1)$:\[\sum_P |P| \times x^{|P|-1}(1-x)^{\partial P}=1\](The sum is on all different polyminos.) or (a) Prove that for every $x \in (0,1)$:\[\sum_P x^{|P|}(1-x)^{\partial P}=x\](The sum is on all polynimo containing $A$) The prove is direct from the situation I gave you above. (b) is just an result of Pick’s theorem since $\partial P$ is less than the number of point on the boundary and the area is exactly $|P|$.