Principe des Bergers

Guy0 · February 2006

Bonjour,

Je me demandais pourquoi dans ce théorème on précise que $f$ doit être surjective, car pour moi dire que $\forall y \in Y, f^-1(y) \subset X $ est un ensemble à $p$ éléments implique déjà que $f$ soit surjective?

Et d'où vient ce nom de principe des Bergers?

Guy

GERARD5 · February 2006

Je ne saisis pas de quel théorème tu parles, mais le principe des bergers est une vieille blague : Pour compter les moutons, on peut compter ... les moutons, ou bien compter les pattes ... et diviser par 4.

Cordialement

MMu · February 2006

Compter les pattes et diviser par 4 est un mauvais algorithme, puisque rien n'interdit des moutons à 3 ou 5 pattes !!.

Guimauve0 · February 2006

Soit $f : A \longrightarrow B$, alors
\[ Card A = \sum_{y \in B} Card (f^{-1}(y)) \]

Effectivement, il n'est pas nécessaire que f soit surjective. Si y n'est pas atteint, $Card f^{-1}(y)=0$.

Guimauve0 · February 2006

Le principe des tiroirs de Dirichlet est une conséquence du principe des bergers (et du bon sens, certes ...).

Guy8 · February 2006

Ah l'origine du nom je comprends alors....

Le théorème c'est :

Soit $f$ une application d'un ensemble $X$ dans un ensemble $Y$. On suppose que $Y$ est un ensemble à $q$ éléments, que pour tout $y \in Y$ l'ensemble $f^{-1}(y) \subset X$ est à p éléments, et que $f$ est surjective. Alors $X$ est un ensemble à $pq$ éléments.

C'est tiré de Algèbre de Godement (entre autres) et j'y suis encore pour longtemps sur cet ouvrage..... moi qui pensait être depuis toujours imperméable à l'Algèbre! .... j'avoue que cette branche des maths m'impressionne et m'émerveille ..... ma dernière stupeur: $Q$ est dénombrable et n'a pas plus d'éléments que $N$, bravo Cantor ....ouais mais bon allez démontrer celà à un élève de seconde, il va vous dire qu'on &quotbricole" sur la notion d'infini....

Guy

GERARD5 · February 2006

Pour Guy : Si c'est du Godement, je comprends. Godement, contrairement au style "bourbakiste" à la mode, ne prend pas toujours des hypothèses minimales, mais souvent des hypothèses efficaces (entre autres pour la compréhension).

Pour Mmu : Mes étudiants me disent souvent la même chose ... Mais ils ne sont pas bergers. Les bergers, eux, connaissent le nombre de pattes des moutons qu'ils gardent.

Cordialement à tous deux

Eric · February 2006

Un simple raisonnement par l'absurde démontre le principe de Dirichlet en deux lignes. Pas besoin de faire appel à je ne sais quel berger.

Guy0 · February 2006

Oh là l'ami, j'ai peut être encore le droit de ne pas connaître le principe de Dirichlet et simplement d'essayer de comprendre ce que m'expose l'ouvrage que j'ai sous les yeux ... et de toute façon je n'ai rien contre la gente paysanne!

Guimauve0 · February 2006

> Un simple raisonnement par l'absurde démontre le principe de Dirichlet en deux lignes. Pas besoin de faire appel à je ne sais quel berger.

Corollaire ça sonne mieux que théorème.

GERARD5 · February 2006

Sauf erreur de ma part, le principe de Dirichlet, dit "des tiroirs" dit qu'une application d'un ensemble fini dans un ensemble ayant moins d'éléments n'est pas injective. Cela n'a rien à voir avec le principe des bergers qui est un simple comptage par paquets (et se pratique dès l'école primaire).

Cordialement

Guy0 · February 2006

A merci Gérard, je ne connaissais pas, et en plus celà semble logique.

Guy

GG7 · February 2006

bonjour,
pour ceux qui auraient conservé la curiosité du sens des mots et des images verbales (on ne sait jamais

, la formulation originelle était : "lorsque des objets en nombre supérieur à n sont disposés dans n tiroirs, l'un de ceux-ci contient nécessairement plus d'un objet".

Gillian Seed0 · February 2006

$\forall y \in Y, f^-1(\{y\}) \subset X$ ne dit pas que $f$ est surjective, car $f^-1(\{y\})$ pourrait bien être vide.

Guimauve0 · February 2006

GERARD,

voici le principe des bergers :

Soit $f : A \longrightarrow B$ une application avec A et B finis.

Alors

\[ Card(A) = \sum_{y \in B} Card(f^{-1}(y)) \]

En notant $(A_i)_{i=1...n} = (f^{-1}(y))_{y \in B}$ (on remarque que c'est une partition de $A$) ceci s'écrit

\[ Card(A) = \sum_{i=1}^n Card(A_i) \]

Et voici le principe de Dirichlet :

Soit $A$ un ensemble fini et $(A_i)_{i=1...n}$ une partition de $A$, alors il existe $i \in \{1, ..., n\}$ tel que $Card(A_i) \geq \left \lceil \dfrac{Card A}{n} \right \rceil$.

On peut bien le prouver en utilisant le principe des bergers :

\[ Card A = \sum_{i=1}^n Card(A_i) \leq n \max_{i=1...n} Card(A_i) \]
\[ \frac{Card A}{n} \leq \max_{i=1...n} Card(A_i) \]
\[ \exists i \in \{1,...,n\} \quad Card(A_i) \geq \left \lceil \dfrac{Card A}{n} \right \rceil \]

GERARD5 · February 2006

Pour Gillian : dans le post de départ on dit que l'ensemble a p éléments . En dehors du cas bizaroïde p=0 (je n'ai pas le contexte, mais je suppose que p>0), un ensemble à p éléments n'est pas vide.

Pour Guimauve : Tout à fait d'accord, à condition d'étendre la définition des principes. Mais ton principe des bergers n'a plus rien à voir avec la définition d'origine.

Cordialement

Principe des Bergers

Réponses

Bonjour!

Catégories

In this Discussion