Combinatoire élémentaire

Olympiades mathématiques, énigmes et défis
MMu
Membre Relatif
Messages: 356
Enregistré le: 12 Déc 2011, 00:43

Combinatoire élémentaire

par MMu » 02 Nov 2017, 14:52

Soit une fonction .
Montrer qu'il existe et tels que ( il est permis )
:frime:



Matt_01
Habitué(e)
Messages: 609
Enregistré le: 30 Avr 2008, 19:25

Re: Combinatoire élémentaire

par Matt_01 » 03 Nov 2017, 10:04

D'après le lemme des tiroirs il y a un des 6 ensembles qui contient au moins 337 éléments.
Sans perte de généralités, supposons que c'est f-1({1}).
On ordonne cet ensemble selon (a_i) croissante et on regarde les (au moins) 336 éléments (a_i-a_1).
S'ils sont dans f-1({1}) alors on a terminé. Sinon c'est que, d'après le lemme des tiroirs, un des 5 autres ensembles contient au moins 68 de ces éléments. De la même manière, on trie selon (b_i) croissante et on regarde les (b_i-b_1) (il faut bien voir que ces termes là sont aussi des différences d'éléments de f-1({1}), et donc on suppose qu'ils ne sont pas dans f-1({1})). Ce sont au moins 67 éléments et donc le lemme des tiroirs nous donne un nouvel ensemble a au moins 17 éléments. Etc etc ... jusqu'à tomber sur un ensemble qui est obligé de boucler sur un précédent ou sur lui même.

MMu
Membre Relatif
Messages: 356
Enregistré le: 12 Déc 2011, 00:43

Re: Combinatoire élémentaire

par MMu » 04 Nov 2017, 02:11

C'est un cas particulier d'un lemme connu (Schurr) ... :mrgreen: :frime:

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : caillou1 et 6 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite