Combinatoire élémentaire
Olympiades mathématiques, énigmes et défis
-
MMu
- Membre Relatif
- Messages: 356
- Enregistré le: 12 Déc 2011, 00:43
-
par MMu » 02 Nov 2017, 14:52
Soit une fonction
.
Montrer qu'il existe
et
tels que
( il est permis
)
-
Matt_01
- Habitué(e)
- Messages: 609
- Enregistré le: 30 Avr 2008, 19:25
-
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
-
par MMu » 04 Nov 2017, 02:11
C'est un cas particulier d'un lemme connu (Schurr) ...
Utilisateurs parcourant ce forum : caillou1 et 6 invités