Consider a sequence of equilateral triangles $T_{n}$ as represented below: [asy][asy] defaultpen(linewidth(0.8));size(350); real r=sqrt(3); path p=origin--(2,0)--(1,sqrt(3))--cycle; int i,j,k; for(i=1; i<5; i=i+1) { for(j=0; j<i; j=j+1) { for(k=0; k<j; k=k+1) { draw(shift(5*i-5+(i-2)*(i-1)*1,0)*shift(2(j-k)+k, k*r)*p); }}}[/asy][/asy] The length of the side of the smallest triangles is $1$. A triangle is called a delta if its vertex is at the top; for example, there are $10$ deltas in $T_{3}$. A delta is said to be perfect if the length of its side is even. How many perfect deltas are there in $T_{20}$?
Problem
Source: 2011 LMO Problem #3
Tags: combinatorics unsolved, combinatorics
22.09.2011 20:05
bluecarneal wrote: Consider a sequence of equilateral triangles $T_{n}$ as represented below: [asy][asy] defaultpen(linewidth(0.8));size(350); real r=sqrt(3); path p=origin--(2,0)--(1,sqrt(3))--cycle; int i,j,k; for(i=1; i<5; i=i+1) { for(j=0; j<i; j=j+1) { for(k=0; k<j; k=k+1) { draw(shift(5*i-5+(i-2)*(i-1)*1,0)*shift(2(j-k)+k, k*r)*p); }}}[/asy][/asy] The length of the side of the smallest triangles is $1$. A triangle is called a delta if its vertex is at the top; for example, there are $10$ deltas in $T_{3}$. A delta is said to be perfect if the length of its side is even. How many perfect deltas are there in $T_{20}$? Let $s_n$ denote the number of perfect deltas in $T_{n}$. I've found that \[s_n=\sum_{i=1}^{+\infty}(n+1-2i)d_{2i}(n)+s_{n-1},\] where, $d_i(n)=1$ if $n\ge i$, and $=0$ if $n< i$.
23.09.2011 10:59
Note that there are n-s+2 C 2 deltas of size s in T_n. By hockeystick, this leads to the general formula n+2 C 3. Hence there are 22 C 3 = 1540 perfect deltas.