Le lemme des bergers

Qui n’a jamais tenté de compter des moutons lors d’une longue nuit d’insomnie ? Toutes ces minutes passées, parfois sans succès, à énumérer ces ovins gambadant dans une verte prairie dans le seul espoir de provoquer la libération des hormones du sommeil… Mais trêve de digression et revenons aux mathématiques.

Il existe en mathématiques un énoncé de combinatoire (c’est-à-dire la branche des mathématiques qui s’intéresse aux questions de dénombrements) communément appelé « Lemme des bergers ». Donnons l’énoncé précis de ce lemme (rappelons que le cardinal d’un ensemble est le nombre d’éléments qu’il contient).

Soit E un ensemble fini, et E_1, ..., E_p, p sous-ensembles de E qui forment une partition de E. On suppose de plus que ces p sous-ensembles sont tous de même cardinal, noté r. Alors: Card(E)=p \times r.

Derrière cet énoncé mathématique se cache un principe d’une évidence enfantine: pour compter le nombre de ses moutons, il suffit à un berger de compter le nombre de pattes et de diviser par 4. Bien qu’évident, ce principe se démontre (de manière simple certes). Il pose la question, pour ceux qui ne sont pas habitués à faire des mathématiques, de savoir ce qu’on doit tenir pour acquis, et ce qu’on doit démontrer.

Un corollaire à ce lemme est l’énoncé suivant:

Soit X et Y deux ensembles finis, et f :X \rightarrow Y  une application surjective. On suppose que tout élément de Y a exactement r antécédents. Alors: Card(X)=r \times Card(Y).

La démonstration est la suivante: si y \in Y, on note E_y l’ensemble des antécédents de y (qui est par hypothèse un ensemble à r éléments. Il est facile de voir que les E_y forment une partition de X. Par le lemme des Bergers, on en déduit la formule attendue.

En fait, cette dernière proposition est même équivalente au lemme des Bergers.

Advertisements
Cet article, publié dans Arithmétique, est tagué , , . Ajoutez ce permalien à vos favoris.

2 commentaires pour Le lemme des bergers

  1. Bruckert dit :

    Une légère erreur dans le corollaire au lemme final : r au lieu de n

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s