A square $ABCD$ is divided into $n^2$ equal small (fundamental) squares by drawing lines parallel to its sides.The vertices of the fundamental squares are called vertices of the grid.A rhombus is called nice when: $\bullet$ It is not a square $\bullet$ Its vertices are points of the grid $\bullet$ Its diagonals are parallel to the sides of the square $ABCD$ Find (as a function of $n$) the number of the nice rhombuses ($n$ is a positive integer greater than $2$).
Problem
Source: Greek MO 2016,Problem 4
Tags: counting, combinatorics
04.03.2016 00:15
Let's first introduce a couple of terms: We will call length of rhombus the length of diagonal parallel to $AB$ and height the length of diagonal parallel to $BC$. Let $XYZT$ be one of rhombuses. Now it is obvious that length and height of $XYZT$ are different because of $1^{st}$ condition, and that both length and height are even numbers. Now denote length and height of $XYZT$ by $2d_1$ and $2h_1$ respectively. Notice that $d_1$ and $h_1$ can be any numbers from $\{1,2,...,\left[\frac{n}{2}\right]\}$. Next notice that because $ABCD$ is n, we can place exactly $n-2d_1+1$ rhoumbuses with length $2d_1$ and given height $h$ on given line parallel to side $AB$(of course if $h$ is not too big). So now it is easily deduced that the number of nice rhombuses is given by following double sum: $$f(n)=\sum_{i=1}^{\left[\frac{n}{2}\right]}\sum_{j=1, j\not=i}^{\left[\frac{n}{2}\right]}(n-2i+1)(n-2j+1)=$$$$\sum_{i=1}^{\left[\frac{n}{2}\right]}\sum_{j=1}^{\left[\frac{n}{2}\right]}(n-2i+1)(n-2j+1)-\sum_{i=1}^{\left[\frac{n}{2}\right]}(n-2i+1)^2\ \ \ \ \ (*)$$. where $f(n)$ is number of nice rhombuses. Now, to calculate this double sum in second row, first fix some $i$ and we will calculate: $$\sum_{j=1}^{\left[\frac{n}{2}\right]}(n-2i+1)(n-2j+1)=$$$$(n-2i+1)\sum_{j=1}^{\left[\frac{n}{2}\right]}(n-2j+1)=$$$$(n-2i+1)((n-1)+(n-3)+\cdots+(n-2\left[\frac{n}{2}\right]+1))\ \ \ \ (1)$$Consider 2 cases in $(1)$: $1)$ $n=2k$ Now the sum in second paranthesis is the sum of odd numbers from $1$ to $2k-1$ which is $k^2=\left[\frac{n}{2}\right]^2=\left[\frac{n}{2}\right]\left(n-\left[\frac{n}{2}\right]\right)$ $2)$ $n=2k+1$ Now the sum in second paranthesis is the sum of even numbers from $2$ to $2k$ which is $2\frac{k(k+1)}{2}=k(k+1)=\left[\frac{n}{2}\right]\left(\left[\frac{n}{2}\right]+1\right)=\left[\frac{n}{2}\right]\left(n-\left[\frac{n}{2}\right]\right)$ Now summing this result for $i$ we get that double sum is equal to $\left[\frac{n}{2}\right]^2\left(n-\left[\frac{n}{2}\right]\right)^2$. Lets work a little bit on right sum now. Again casework on parity of n: $1)$ $n=2k$ The sum is nothing but sum of squares of odd numbers from $1$ to $2k-1$ which is $\frac{1}{3}k(2k+1)(2k-1)=\frac{1}{3}\left[\frac{n}{2}\right](n+1)(n-1)=\frac{1}{3}\left[\frac{n}{2}\right](n+1)(2\left[\frac{n+1}{2}\right]-1)$ $2)$ $n=2k+1$ This sum is now sum of squares of even numbers from $2$ to $2k$ which is $\frac{2}{3}k(2k+1)(k+1)=\frac{1}{3}\left[\frac{n}{2}\right]n(n+1)=\frac{1}{3}\left[\frac{n}{2}\right](n+1)(2\left[\frac{n+1}{2}\right]-1)$ So now plugging in $(*)$ we get the following(although nasty expression): $$f(n)=\left[\frac{n}{2}\right]^2\left(n-\left[\frac{n}{2}\right]\right)^2-\frac{1}{3}\left[\frac{n}{2}\right](n+1)(2\left[\frac{n+1}{2}\right]-1)$$I checked it for $n=3$ and $n=4$ and it works but i am not really sure if this was the expression they were looking on the competition, so if someone could confirm my solution i would be grateful (and of course $[r]$ is floor function)
14.06.2016 20:56
DrUki wrote: So now plugging in $(*)$ we get the following(although nasty expression): $$f(n)=\left[\frac{n}{2}\right]^2\left(n-\left[\frac{n}{2}\right]\right)^2-\frac{1}{3}\left[\frac{n}{2}\right](n+1)(2\left[\frac{n+1}{2}\right]-1)$$I checked it for $n=3$ and $n=4$ and it works but i am not really sure if this was the expression they were looking on the competition, so if someone could confirm my solution i would be grateful (and of course $[r]$ is floor function) Uh..... i think it doesn't work if $n=5$ i got $\left[\frac{n^{2}}{4}\right]^{2}$
13.11.2016 08:53
Umm well this is my idea (plss check). Every good rhombus is uniquely placed in a rectangle having even length and even breadth.We just consider midpoints of all sides and it gives us a nice rhombus .So we just have to count such rectangles with even length and breadth which are not squares.....
14.11.2016 02:03
Fix any two line segments in the grid such that one is perpendicular to one side(say AB) of the square and other is perpendicular to other side of the square and both have their endpoints on the so called 'vertices' of the grid.Also they must bisect each other. If the length of both these line segments are not of equal length, then their endpoints consistute the vertices of a unique nice rhombus.For every pair of such line segments there exists a unique rectangle having these line segments as the segments joining the midpoints of its sides. As the midpoint of the side of such a square is a vertex of the grid , such a square must have even length and breadth but must itself not be a square. So i think saurav you are right.