Solution au problème de mai 2012

Le problème:

Une permutation arbitraire $\sigma$ des entiers de 1 à 2012 peut être représentée dans le plan par un ensemble de 2012 points de la forme $(k,\sigma(k))$, $k$ allant de 1 à 2012. Le plus petit carré qui contient tout ces points et a ses côtés parallèles aux axes a au moins 2 et au plus 4 des points de l'ensemble sur sa frontière. Déterminer le nombre de permutations qui ont exactement $m$ points de l'ensemble sur la frontière, pour $m = 2, 3, 4$. Par exemple, Le graphe de la permutation $(5,3,6,1,7,2,4)$ des entiers de 1 à 7 est l'ensemble $(1,5), (2,3), \ldots, (7,4)$ représenté dans la figure suivante. Le plus petit carré avec côtés parallèles aux axes qui contient tous ces points a exactement quatre des points sur sa frontière.

Nous avons re�u les solutions correctes de

Notre probl�me de ce mois est un cas particulier du Probl�me 1862 de Mathematics Magazine, propos� par Emeric Deutsch. On trouve la. solution � ce probl�me dans le volume 85, No. 1 (f�vriere 2012) � la page 63 : Les graphes des $n!$ permutations des entiers de 1 � $n$ comportent

Dans le cas $n = 2012$, nos correspondants nous fournissent les arguments suivants.

2 points sur la fronti�re. Voici l'argument de Collignon:

"Il faut dans ce cas que les deux points soient situ�s sur deux sommets oppos�s du carr�, ce qui correspond aux deux familles de permutations telles que :

$\sigma(1) = 1$ et $\sigma(2012) = 2012$ et donc aux sommets $(1,1)$ et $(2012,2012)$

ou bien $\sigma(1) = 2012$ et $\sigma(2012) = 1$ et donc aux sommets $(1,2012)$ et $(2012,1)$.

Il reste donc 2010 points � placer � l�int�rieur du carr�, ce qui correspond � $2 \times 2010!$ permutations au total.

3 points sur la fronti�re.Voici l'argument de Humbert :

"Il y a quatre coins possibles, puis 2010 positions possibles pour le point du c�t� vertical oppos�, puis $2010!$ permutations possibles des nombres restants. Au final, il y a $4 \times 2010 \times 2010!$ permutations pour lesquelles le carré contient trois points.

4 points sur la fronti�re. Voici l'argument de Notarantonio :

"Cela correspond aux graphes de permutations suivants :

$$\sigma : (a, ...., b)$$

avec $a \neq1$ et $a \neq2012$, et $b \neq 1$ et $b \neq 2012$. Il y a 2010 emplacements diff�rents pour l'entier 1 (puisqu'il ne peut pas �tre � l'emplacement 1 ou � l'emplacement 2012), et ensuite 2009 emplacements diff�rents pour l'entier 2012 (puisqu'il ne peut pas �tre � l'emplacement 1 ou � l'emplacement 2012 ou � l'emplacement o� 1 a �t� plac�). Il reste 2010 entiers � placer dans les 2010 emplacements restant: cela correspond � $2010!$ permutations diff�rentes.

On a donc $2009\times 2010 \times 2010!$ permutations qui ont exactement 4 points de l'ensemble sur la fronti�re.''

On peut aditionner ces valeurs pour v�rifier qu'elles sont consistantes:

$$\begin{eqnarray*} 2&\times& 2010! + 4 \times 2010 \times 2010! + 2010 \times 2009 \times 2010! \\&=& (2+2013\cdot 2010) \times 2010!\\ &=& (2012\times 2011) \times 2010! = 2012!, \end{eqnarray*}$$

tel qu'il se doit.