Salut,

Dans une classe, deux élèves quelconques ont toujours exactement une option en commun et au moins une de différente. Montrez qu'il y a nécessairement plus d'options que d'élèves.

Version maths (généralisée) :
On considère m parties distinctes d'un ensemble à n éléments dont les intersections deux à deux sont toutes de même cardinal (non nul), alors m <= n.

Trop simple? Trop dur?

Bah déjà si ils ont tous au moins une option différente alors si il y a n élèves il y a au moins n options en effet s'il y en a moins d'après le principe des tiroirs on peut en trouver 2 qui ont la même option.

Vistiche, ça méritait précision : Par "au moins une de différente" on sous-entend qu'au moins un des deux élève en fait une différente de l'autre. (autrement dit que leurs ensembles d'options sont distincts). Je t'accorde que ce n'est pas la même chose que de dire qu'il existe au moins un élément dans chaque ensemble qui n'est pas dans l'autre.

A ce moment là, on ne peut plus en déduire qu'il y a au moins n options.

Exemple avec deux options :
Elève 1 : {latin}
Elève 2 : {chinois}
Elève 3: {latin, chinois}

Alors pour chaque paire d'élève quelconque il y en a au moins un qui fait une option différente de l'autre, pourtant il y a moins d'options que d'élève.

Le 08 février 2016 à 17:50:13 El_Bug a écrit :
A moi la médaille Fields

Non elle sera à Bounty

Bon personnellement je n'ai rien et vu l'aspect assez sophistiqué des preuves proposées, je jette l'éponge.

Voici le cheminement de la preuve du bouquin (pour info, c'est un oral de Polytechnique) :
1) On pose M la matrice (aij) où aij = 1 si aj est dans la i-ème partie considérée dans l'énoncé, 0 sinon.
2) On montre que Ker(M.transposée(M)) = {0}
3) On conclut que rang(M) <= n et donc que le nombre de parties est inférieur à n.

(apparemment c'est du raisonnement classique en théorie des graphes, M étant une matrice d'incidence mais comme j'y connais rien, je considère ça comme sophistiqué)

Voici la preuve la plus "élémentaire" que j'ai pu trouvée sur le net (faut l'écrire sur un exemple pour comprendre....) : http://ac.els-cdn.com/0012365X9390179W/1-s2.0-0012365X9390179W-main.pdf?_tid=898d0d78-cf4d-11e5-b8bd-00000aab0f01&acdnat=1455036943_356c8f934f00fa35a3e9c3a014825a9e

On a du mal à voir comment les mecs arrivent à pondre des trucs pareils, à la fois très simple mais dont on ne comprend pas du tout d'où c'est venu (dans l'article ils disent s'inspirer d'autres articles de combinatoire, mais quand même...)

Euh bah t'auras pas pu me le dire plus tôt que je pouvais pas trouver?

J'avais posté dans l'espoir qu'on trouve ensemble une preuve purement combinatoire (Dont j'ai légitimement supposé l'existence vu la simplicité de l'énoncé), je ne pouvais pas prévoir qu'on allait se casser la tête!

Et vous, vous avez des exercices un peu sympa à proposer? (Moins casse gueule que celui-ci du coup...)