099 Parallélogrammes

 

Réponse 1 : 

Bien que ça nécessite une démonstration, je vais supposer comme admis le fait intuitif qui dit que le "pavage" du grand triangle équilatéral ABC (côté
"n") avec des petits triangles (côté "1") s'obtient comme suit :
- On divise chaque grand côté en "n" segments, chacun de longueur "1"
- On trace toutes les droites qui passent par 2 points de division et sont parallèles aux côtés du grand triangle 

Considérons un système de coordonnées "obliques" tel que : A = origine, AB =axe_X, AC = Axe_Y
(P=(x,y) est intérieur à ABC) <===> (0 =< x , 0 =< y , x+y =< n)

Je note : - Na = le nombre de parallélogrammes, formés avec les "petits triangles"dans ABC, et ayant les côtés parallèles à AB et AC 
- Nb = le nombre de parallélogrammes dans ABC, avec les côtés parallèles à BC et BA
- Nc = le nombre de parallélogrammes dans ABC, avec les côtés parallèles à CA et CB
A cause de la symétrie on a Na = Nb = Nc.

Soit un parallélogramme PQRS formés avec des "petits triangles" dans ABC, et tel que :
PQ || RS || AB et QR || PS || AC .
Ses sommets ont les coordonnées suivantes :
P = (X,Y) , Q = (X+U,Y) , R = (X+U,Y+V) , S = (X,Y+U), avec :
X,Y,U,V = entiers , 0 =< X , 0 =< Y , 1 =< U , 1 =< V , X+U+Y+V =< n

Le nombre de tels parallélogrammes PQRS est :
Na = SOMME(0=<X,0=<Y , 1=<U,1=<V , X+Y+U+V=<n){1} = 
= SOMME(1=<U,1=<V, 0 =< n-U-V){SOMME(0=<X,0=<Y, X+Y =< n-U-V){1}} = 
= SOMME(1=<U,1=<V, 0 =< n-U-V){SOMME(0 =< k =< n-U-V){k+1}}
= SOMME(1=<U,1=<V, 0 =< n-U-V){(n-U-V+1)*(n-U-V+2)/2}
= SOMME(2 =< k =< n){(k-1)(n-k+1)*(n-k+2)/2}= SOMME(1 =< k =<n-1){k*(n-k)*(n-k+1)/2} = 
= n*(n^2 -1)*(n+2)/24 = C(4,n+2) (combinaisons de 4 parmi n+2 : est ce un hasard ?!)

Le nombre total de parallélogrammes sera donc : Nt = Na + Nb + Nc = 3*Na = n*(n^2 -1)*(n+2)/8 

Réponse 2 :
Quelques dessins pour le cas où n=4 : 
- les parallélogrammes engendrés par /_ sont à chercher dans 
/_ 
/_/_ 
/_/_/_ 
/_/_/_/_ 
- les parallélogrammes engendrés par \_ sont à chercher dans 
_\ 
_\_\ 
_\_\_\ 
_\_\_\_\ 
- les parallélogrammes engendrés par /\ sont à chercher dans 
/\ 
/\/\ 
/\/\/\ 
/\/\/\/\ 
=> dans les trois cas la figure est un quadrillage triangulaire semblable à : 

|_|_ 
|_|_|_ 
|_|_|_| 
Il suffit donc de dénombrer les parallélogrammes dans cette figure et de multiplier le résultat par 3 pour répondre au problème initial.
Soit un parallélogramme fixé de i traits horizontaux et j traits verticaux, que nous noterons (i;j). 
La condition d'existence d'un tel parallélogramme est que 1 <= i,j <= n-1 et que i+j <= n 
Combien de parallélogrammes (i;j) y a-t-il sur la figure ? 
Si i+j=n, il y en a 1. 
Si i+j=n-1, il y en a 2+1. 
... 
Dans le cas général, il y en a n+1-i-j + ... + 1 (c'est assez facile à voir sur la figure) 
Ainsi le nombre de parallélogrammes de la figure vaut : 
somme(i=1;n-1) somme(j=1;n-i) somme(k=1;n+1-i-j) 1 
= somme(i=1;n-1) somme(j=1;n-i) (n+1-i-j)(n+2-i-j)/2 
= somme(i=1;n-1) somme(j=1;n-i) j(j+1)/2 
= somme(i=1;n-1) somme(j=1;n-i;C(j+1;2)) 
= somme(i=1;n-1) somme(j=2;n+1-i;C(j;2)) 
= somme(i=1;n-1;C(n+2-i;3)) 
= somme(i=3;n+1;C(i;3)) 
= C(n+2;4) 
= (n+2)(n+1)n(n-1)/24 
D'où le nombre initial de parallélogramme : (n+2)(n+1)n(n-1)/8 
En particulier pour n = 10, cela donne 1485 parallélogrammes (bon courage pour le dénombrement à la main...) 

Ci-dessus, on a utilisé plusieurs fois le résultat suivant : 
S = somme(n=k;l;C(n;k)) = C(l+1;k+1) 
(en notant le coefficient binomial C(n;k) = n! / k!(n-k)!) 
Preuve :
Rappelons que C(n;k) = C(n+1;k+1) - C(n;k+1) 
Alors le résultat s'obtient par une somme télescopique 
S = C(k;k) + somme(n=k+1;l;C(n+1;k+1) - C(n;k+1)) 
= 1 + somme(n=k+2;l+1;C(n;k+1)) - somme(n=k+1;l;C(n;k+1)) 
= 1 + C(l+1;k+1) - C(k+1;k+1) 
= C(l+1;k+1)